论文标题
有效的不平等和全球解决方案算法，用于四二次二次程序
Valid inequalities and global solution algorithm for Quadratically Constrained Quadratic Programs
论文作者
论文摘要
我们考虑了问题$（QP）$的确切解决方案，该解决方案包括最小化受二次约束的二次函数。从使用McCormick信封的经典凸松弛开始，我们引入了12种不等式，这些不平等来自$（QP）$的变量范围。我们证明，这些一般三角不平等削弱了麦考密克信封的可行解决方案。然后，我们展示如何计算凸放松$（p^*）$，最佳价值等于“ Shor's Plus RLT Plus Triangle”的$（QP）$的半明确放松$（QP）$，其中包括新的不平等现象。我们还提出了一个启发式方法，用于解决这个巨大的半准计划，该程序用作分离算法。然后，我们将$（QP）$求解为全球最优性，并基于$（p^*）$的分支机构。此外，随着新的不等式涉及$（QP）$的原始变量的下限和上限，它们在分支和结合框架中的使用会加速整个过程。我们在单位箱实例上显示我们的方法优于比较求解器。
We consider the exact solution of problem $(QP)$ that consists in minimizing a quadratic function subject to quadratic constraints. Starting from the classical convex relaxation that uses the McCormick's envelopes, we introduce 12 inequalities that are derived from the ranges of the variables of $(QP)$. We prove that these general Triangle inequalities cut feasible solutions of the McCormick's envelopes. We then show how we can compute a convex relaxation $(P^*)$ which optimal value equals to the "Shor's plus RLT plus Triangle" semi-definite relaxation of $(QP)$ that includes the new inequalities. We also propose a heuristic for solving this huge semi-definite program that serves as a separation algorithm. We then solve $(QP)$ to global optimality with a branch-and-bound based on $(P^*)$. Moreover, as the new inequalities involved the lower and upper bounds on the original variables of $(QP)$, their use in a branch-and-bound framework accelerates the whole process. We show on the unitbox instances that our method outperforms the compared solvers.
