Separable Non-convex Underestimators for Binary Quadratic Programming
Separable Non-convex Underestimators for Binary Quadratic Programming
复制标题
DOI：
10.1007/978-3-642-38527-8_22
复制
发表时间：
2013-06
影响因子：
2.7
通讯作者：
C. Buchheim;Emiliano Traversi
中科院分区：
文献类型：
--
作者：
C. Buchheim;Emiliano Traversi
我们提出了一种约束二次二元规划的新方法。通过选择目标函数的适当全局低估量来计算对偶界限，这些低估量是可分离的但不一定是凸的。使用变量上的二元约束，可以将该可分离低估量的最小化简化为同一组可行向量上的线性最小化问题。对于大多数组合优化问题，线性版本比二次版本要容易得多。我们解释了如何将这种方法嵌入到分支定界算法中并给出实验结果。
We present a new approach to constrained quadratic binary programming. Dual bounds are computed by choosing appropriate global underestimators of the objective function that are separable but not necessarily convex. Using the binary constraint on the variables, the minimization of this separable underestimator can be reduced to a linear minimization problem over the same set of feasible vectors. For most combinatorial optimization problems, the linear version is considerably easier than the quadratic version. We explain how to embed this approach into a branch-and-bound algorithm and present experimental results.