论文标题
具有基数限制的凸多线性集：结构属性，嵌套案例和扩展
Convexifying Multilinear Sets with Cardinality Constraints: Structural Properties, Nested Case and Extensions
论文作者
论文摘要
最小化二进制变量的多线性功能的问题是一个充分研究的NP障碍问题。该问题的标准线性化解决方案集称为多线性集合。我们研究了非零变量数量上的上限和下限的IT的基数约束版本。我们称此问题的标准线性化解决方案集为具有基数约束的多线性集合。我们表征了这些多线性术语（称为适当性）的一组条件，并观察到在这些条件下，该集合的凸面描述是通过扩展的公式进行的。然后，当多线性项具有嵌套结构时，我们给出了凸面的显式多面体描述。我们的描述具有指数数的不平等数量，可以在多项式时间内分开。最后，我们概括了这些不平等，以获得一般案例的有效不平等。
The problem of minimizing a multilinear function of binary variables is a well-studied NP-hard problem. The set of solutions of the standard linearization of this problem is called the multilinear set. We study a cardinality constrained version of it with upper and lower bounds on the number of nonzero variables. We call the set of solutions of the standard linearization of this problem a multilinear set with cardinality constraints. We characterize a set of conditions on these multilinear terms (called properness) and observe that under these conditions the convex hull description of the set is tractable via an extended formulation. We then give an explicit polyhedral description of the convex hull when the multilinear terms have a nested structure. Our description has an exponential number of inequalities which can be separated in polynomial time. Finally, we generalize these inequalities to obtain valid inequalities for the general case.
