论文标题
互补性背包问题的新各个方面
New Classes of Facets for Complementarity Knapsack Problems
论文作者
论文摘要
互补性背包问题（CKP）是一个背包问题，其变量对之间具有实值变量和互补条件。我们扩展了De Farias等人的多面体研究。对于CKP，提出了三个新的切割平面家族，它们都是从称为包装的组合概念中获得的。还提供了足够的条件，这些不平等是根据最大开关包的概念而定义的。此外，我们对de Farias等人的猜想积极回答，内容涉及他们工作中引入的不平等的分离复杂性，并建议我们新定义的切割层的有效分离算法。
The complementarity knapsack problem (CKP) is a knapsack problem with real-valued variables and complementarity conditions between pairs of its variables. We extend the polyhedral studies of De Farias et al. for CKP, by proposing three new families of cutting-planes that are all obtained from a combinatorial concept known as a pack. Sufficient conditions for these inequalities to be facet-defining, based on the concept of a maximal switching pack, are also provided. Moreover, we answer positively a conjecture by de Farias et~al.~about the separation complexity of the inequalities introduced in their work, and propose efficient separation algorithms for our newly defined cutting-planes.
