论文标题
修复和绑定：一种解决大规模二次编程问题的有效方法
Fix and Bound: An efficient approach for solving large-scale quadratic programming problems with box constraints
论文作者
论文摘要
在本文中，我们提出了一种分支结合的算法，用于用盒子约束（BoxQP）求解非convex二次编程问题。我们的方法结合了现有工具，例如半决赛编程（SDP）通过有效的不平等增强的界限，以及基于最佳的新线性剪切，从而导致可变固定。修复某些变量值的最重要效果是沿分支和结合树的尺寸减小，从而可以通过求解较小尺寸的SDP来计算边界。大型计算实验（最多$ n = 200 $）的测试实例表明，我们的方法是大型BoxQPS上的最新求解器。此外，我们在二进制QP问题的类别中测试了提出的方法，在该类别中，它与最先进的求解器表现出竞争性能。
In this paper, we propose a branch-and-bound algorithm for solving nonconvex quadratic programming problems with box constraints (BoxQP). Our approach combines existing tools, such as semidefinite programming (SDP) bounds strengthened through valid inequalities, with a new class of optimality-based linear cuts which leads to variable fixing. The most important effect of fixing the value of some variables is the size reduction along the branch-and-bound tree, allowing to compute bounds by solving SDPs of smaller dimension. Extensive computational experiments over large dimensional (up to $n=200$) test instances show that our method is the state-of-the-art solver on large-scale BoxQPs. Furthermore, we test the proposed approach on the class of binary QP problems, where it exhibits competitive performance with state-of-the-art solvers.
