论文标题
变量有限产物的凸壳表示
Convex Hull Representations for Bounded Products of Variables
论文作者
论文摘要
众所周知，$ \ {（x，y，xy）\} $的凸壳，其中$（x，y）$被限制在盒子里，由重新制定线性化技术（RLT）约束提供。 Belotti {\ em等人\，}（2010）和Miller {\ em等人\，}（2011）表明，如果产品上还有其他上限和/或下限$ z = xy $，则可以通过添加无限的无限型家族来代表一个无限的家族，需要添加一个分离的算法。 nguyen {\ em et al。\，}（2018）（2018年）在$ z $ $ z = x^{b_1} y^{b_2} $的更一般情况下，$ z $上的bongs hulls in bongs hulls，其中$ b_1 \ ge 1 $，$ b_1 $，$ b_2 \ ge 1 $。我们专注于最重要的情况，即$ b_1 = b_2 = 1 $，并表明产品上具有上限或下限的凸面船体由RLT约束给出，对$ z $和单个二阶锥体（SOC）约束给出。对于产品上的上限和下限，可以使用不超过三个SOC约束来表示凸船体，每个凸面都适用于$（x，y）$值的子集。除了凸面的特征外，还计算了$ z $上凸面或下限的凸壳的体积，并将其与仅施加RLT约束的放松相比。作为这些体积结果的应用，我们展示了如何将空间分支应用于产品变量，以最大程度地减少两个结果子问题的体积之和。
It is well known that the convex hull of $\{(x,y,xy)\}$, where $(x,y)$ is constrained to lie in a box, is given by the Reformulation-Linearization Technique (RLT) constraints. Belotti {\em et al.\,}(2010) and Miller {\em et al.\,}(2011) showed that if there are additional upper and/or lower bounds on the product $z=xy$, then the convex hull can be represented by adding an infinite family of inequalities, requiring a separation algorithm to implement. Nguyen {\em et al.\,}(2018) derived convex hulls with bounds on $z$ for the more general case of $z=x^{b_1} y^{b_2}$, where $b_1\ge 1$, $b_2\ge 1$. We focus on the most important case where $b_1=b_2=1$ and show that the convex hull with either an upper bound or lower bound on the product is given by RLT constraints, the bound on $z$ and a single Second-Order Cone (SOC) constraint. With both upper and lower bounds on the product, the convex hull can be represented using no more than three SOC constraints, each applicable on a subset of $(x,y)$ values. In addition to the convex hull characterizations, volumes of the convex hulls with either an upper or lower bound on $z$ are calculated and compared to the relaxation that imposes only the RLT constraints. As an application of these volume results, we show how spatial branching can be applied to the product variable so as to minimize the sum of the volumes for the two resulting subproblems.
