Global solution of non-convex quadratically constrained quadratic programs
Global solution of non-convex quadratically constrained quadratic programs
复制标题
DOI：
10.1080/10556788.2017.1350675
复制
发表时间：
2019-01-02
影响因子：
2.2
通讯作者：
Lambert, Amelie
中科院分区：
文献类型：
--
作者：
Elloumi, Sourour;Lambert, Amelie
混合整数二次约束二次规划 (QCQP) 类包括在二次约束下最小化二次函数，其中变量可以是整数或连续。在之前的论文中，我们介绍了一种名为 MIQCR 的方法来求解 QCQP，但具有以下限制：纯连续变量的所有二次子函数都已经是凸函数。在本文中，我们提出了适用于任何 QCQP 的 MIQCR 扩展。让我们成为一名 QCQP。我们的解决方法是首先构建一个等效的混合整数二次问题。该等价问题具有二次凸目标函数、线性约束和用于满足附加二次约束 的附加变量 y ，其中 x 是问题 的初始变量 。然后，我们建议通过基于附加二次约束和完整性约束的松弛的分支定界算法来求解。这种类型的分支称为空间分支定界。计算经验总共在325个实例上进行。结果表明，与最近实施的 QuadProgBB 以及求解器 Cplex、Couenne、Scip、BARON 和 GloMIQO 相比，我们的方法改进了大多数考虑实例的求解时间。
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let be a QCQP. Our approach to solve is first to build an equivalent mixed-integer quadratic problem . This equivalent problem has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints , where x are the initial variables of problem . We then propose to solve by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON andGloMIQO.