Optimization Online


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

Bo Zeng (bzeng***at***ecn.purdue.edu)
Jean-Philippe Richard (jprichar***at*** 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 )


Download: [Postscript][PDF]

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

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 Programming Society