Exact approaches for the knapsack problem with setups
Furini, Fabio; Monaci, Michele; Traversi, Emiliano (2018), Exact approaches for the knapsack problem with setups, Computers & Operations Research, 90, p. 208-220. 10.1016/j.cor.2017.09.019
TypeArticle accepté pour publication ou publié
Journal nameComputers & Operations Research
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Laboratoire d'Informatique de Paris-Nord [LIPN]
Abstract (EN)We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We theoretically compare the strength of the relaxations and derive specific results for a relevant case arising in benchmark instances from the literature. Finally, we embed the algorithms above into a unified implicit enumeration scheme which is run in parallel with an improved Dynamic Programming algorithm to effectively solve the problem to proven optimality. An extensive computational analysis shows that our new exact algorithm is capable of efficiently solving all the instances of the literature and turns out to be the best algorithm for instances with a low number of classes.
Subjects / KeywordsKnapsack problems; Column generation; Relaxations; Branch-and-bound algorithms; Computational experiments
Showing items related by title and author.
Caprara, Alberto; Furini, Fabio; Malaguti, Enrico; Traversi, Emiliano (2016) Article accepté pour publication ou publié
Létocart, Lucas; Furini, Fabio; Liberti, Leo; Traversi, Emiliano; Bettiol, Enrico; Rinaldi, Francesco (2018) Article accepté pour publication ou publié