论文标题
使用双线性盖不平等解决稀疏的可分离双线性程序
Solving sparse separable bilinear programs using lifted bilinear cover inequalities
论文作者
论文摘要
最近，我们提出了一类称为抬起双线性覆盖不平等的不平等现象，这些不平等是二阶锥形代表的凸不平等，并且对由可分离的双线性约束所描述的集合以及变量的边界有效。在本文中，我们研究了这些不平等的计算潜力对于可分离双线性优化问题。我们首先证明，半准编程放松对此类问题的放松没有任何好处。然后，我们设计了一个简单的随机分离启发式，以提起双线性覆盖不平等。在我们的计算实验中，我们将这些不平等的许多回合从麦考密克的放宽实例开始，因为每个约束都是可分离的双线性约束集。我们证明，在闭合差距方面，最先进的全球求解器的性能有了显着改善，而与没有的情况相比，在根节点上添加这些不平等现象时。
Recently, we proposed a class of inequalities called lifted bilinear cover inequalities, which are second-order cone representable convex inequalities, and are valid for a set described by a separable bilinear constraint together with bounds on variables. In this paper, we study the computational potential of these inequalities for separable bilinear optimization problems. We first prove that the semi-definite programming relaxation provides no benefit over the McCormick relaxation for such problems. We then design a simple randomized separation heuristic for lifted bilinear cover inequalities. In our computational experiments, we separate many rounds of these inequalities starting from McCormick's relaxation of instances where each constraint is a separable bilinear constraint set. We demonstrate that there is a significant improvement in the performance of a state-of-the-art global solver in terms of gap closed, when these inequalities are added at the root node compared to when they are not.
