Paper Info
Title
A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting
Abstract
In this paper, we study the polyhedral structure of the set of 0-1 integer solutions to a single knapsack constraint and multiple disjoint cardinality constraints (MCKP). This set is a generalization of the classical 0-1 knapsack polytope (KP) and the 0-1 knapsack polytope with generalized upper bounds (GUBKP). For MCKP, we extend the traditional concept of a cover to that of a generalized cover. We then introduce generalized cover inequalities and present a polynomial algorithm that can lift them into facet-defining inequalities of the convex hull of MCKP. For the case where the knapsack coefficients are non-negative, we derive strong bounds on the lifting coefficients and describe the maximal set of generalized cover inequalities. Finally, we show that the bound estimates we obtained strengthen or generalize the known results for KP and GUBKP.
Year
DOI
Venue
2011
10.1016/j.disopt.2010.09.005
Discrete Optimization
Keywords
Field
DocType
cardinality constraint,convex hull,generalized cover,knapsack polytope,single knapsack constraint,polyhedral study,facet,facet-defining inequality,knapsack,generalized cover inequality,knapsack problem,bound estimate,disjoint cardinality constraint,generalized upper bound,knapsack coefficient,maximal set,lifting,sequential lifting,integer solution,upper bound
Integer,Discrete mathematics,Mathematical optimization,Combinatorics,Maximal set,Disjoint sets,Cardinality,Convex hull,Continuous knapsack problem,Facet (geometry),Knapsack problem,Mathematics
Journal
Volume
Issue
ISSN
8
2
Discrete Optimization
Citations 
PageRank 
References 
7
0.49
19
Authors
2
Name
Order
Citations
PageRank
Bo Zeng17613.74
Jean-Philippe P. Richard221516.55