Quadratic Combinatorial Optimization Using Separable Underestimators
Quadratic Combinatorial Optimization Using Separable Underestimators
复制标题
DOI：
10.1287/ijoc.2017.0789
复制
发表时间：
2018-06-01
影响因子：
2.1
通讯作者：
Traversi, Emiliano
中科院分区：
文献类型：
--
作者：
Buchheim, Christoph;Traversi, Emiliano
具有二次目标函数的二元规划一般是NP难的，即使在同一可行集上的线性优化问题是易处理的。在本文中，我们通过计算可分离但不一定是凸的目标函数的二次全局低估来解决这些问题。利用二元约束的变量，一个极小的可行集上的可分离低估可以计算通过解决一个适当的线性最小化问题在同一可行集。将得到的下界嵌入到分枝定界框架中，我们得到了原二次二元规划的精确算法。主要的实际挑战是快速计算一个适当的低估，这在我们的方法减少到解决一系列的半定方案。我们利用所产生的问题的特殊结构，以获得一个量身定制的坐标下降法的解决方案。我们在各种二次组合优化问题上的广泛实验结果表明，我们的方法优于CPLEX和相关的QCR方法，以及基于SDP的软件BiqCrunch的二次最短路径问题和二次分配问题的实例。
Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a minimizer of the separable underestimator over the feasible set can be computed by solving an appropriate linear minimization problem over the same feasible set. Embedding the resulting lower bounds into a branch-and-bound framework, we obtain an exact algorithm for the original quadratic binary program. The main practical challenge is the fast computation of an appropriate underestimator, which in our approach reduces to solving a series of semidefinite programs. We exploit the special structure of the resulting problems to obtain a tailored coordinate-descent method for their solution. Our extensive experimental results on various quadratic combinatorial optimization problems show that our approach outperforms both CPLEX and the related QCR method as well as the SDP-based software BiqCrunch on instances of the quadratic shortest path problem and the quadratic assignment problem.