Solving Box-Constrained Nonconvex Quadratic Programs
Solving Box-Constrained Nonconvex Quadratic Programs
复制标题
求解框约束非凸二次规划
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Jeff T. Linderoth
中科院分区：
文献类型：
--
作者：
Pierre Bonami;O. Günlük;Jeff T. Linderoth
给出了求解带盒约束的非凸二次规划(BoxQP)的有效计算方法。我们首先观察到，从布尔二次多面体(BQP)得到的割平面在计算上是有效的，可以减小BoxQP的最优间隙。接下来，我们证明了BQP的Chvátal-Gomory闭包即使在基础图不完全的情况下也是由奇圈不等式给出的。通过在空间分支切割框架中使用这些割平面，结合基于完整性的分支技术和加强的凸二次松弛，我们开发了一个能够有效地求解一族著名测试实例的求解器。我们的大多数计算技术已经在最新版本的CPLEX中实现，并导致了非凸二次规划的显著性能改进
We present effective computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal-Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with an integrality-based branching technique and a strengthened convex quadratic relaxation, we develop a solver that can effectively solve a wellknown family of test instances. Most of our computational techniques have been implemented in the recent version of CPLEX and lead to significant performance improvements on nonconvex quadratic programs with
影响因子：
3.1
作者：
Burer S
通讯作者：
Burer S