Sequence independent lifting for 0-1 knapsack problems with disjoint cardinality constraints

Bo Zeng (bzengecn.purdue.edu)
Jean-Philippe Richard (jprichar ecn.purdue.edu)

Abstract: In this paper, we study the set of 0-1 integer solutions to a single knapsack constraint and a set of non-overlapping cardinality constraints (MCKP). This set is a generalization of the traditional 0-1 knapsack polytope and the 0-1 knapsack polytope with generalized upper bounds. We derive strong valid inequalities for the convex hull of its feasible solutions by lifting the generalized cover inequalities presented in Zeng and Richard [32]. For problems with a single cardinality constraint, we derive a set of multidimensional superadditive lifting functions and prove that they are maximal and non-dominated under some mild conditions. We then show that these functions can also be used to build strong valid inequalities for problems with multiple disjoint cardinality constraints.

Keywords: multidimensional sequence independent lifting, knapsack problem, polyhedral theory

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Integer Programming (0-1 Programming )

Citation:

Download: [Postscript][PDF]

Entry Submitted: 09/19/2006
Entry Accepted: 09/20/2006
Entry Last Modified: 09/19/2006

Modify/Update this entry