A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting
A polyhedral study on 0-1 knapsack problems with disjoint cardinality constraints: Facet-defining inequalities by sequential lifting
复制标题
具有不相交基数约束的 0-1 背包问题的多面体研究：通过顺序提升定义面不等式
DOI：
10.1016/j.disopt.2010.09.005
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Jean
中科院分区：
文献类型：
--
作者：
Bo Zeng;Jean
本文研究了单个背包约束和多个不相交基数约束的0-1整数解集的多面体结构。这个集合是经典的0-1背包多面体(KP)和具有广义上界的0-1背包多面体(GUBKP)的推广。对于MCKP，我们将传统的覆盖概念推广到广义覆盖。然后，我们引入了广义覆盖不等式，并给出了一个多项式算法，该算法可以将它们提升为MCKP凸壳的刻面定义的不等式。对于背包系数为非负的情形，我们得到了提升系数的强界，并刻画了广义覆盖不等式的最大集。最后，我们证明了我们得到的界估计加强或推广了关于KP和GUBKP的已知结果。
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.