Optimization Online


Exact Approaches for the Knapsack Problem with Setups

Fabio Furini (fabio.furini***at***dauphine.fr)
Michele Monaci (michele.monaci***at***unibo.it)
Emiliano Traversi (emiliano.traversi***at***lipn.univ-paris13.fr)

Abstract: 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 efficiently compute an optimal solution of the problem. 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.

Keywords: knapsack problem, Integer Linear Programming, relaxations, exact algorithms, computational experiments

Category 1: Integer Programming

Category 2: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 07/12/2016
Entry Accepted: 07/12/2016
Entry Last Modified: 02/01/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society