A Decomposition Method for Quadratic Zero-One Programming
提出一种分解方法，用于计算无约束二次零一最小化问题的下界，通过将二次函数分解为特定函数之和，并用拉格朗日分解找到最优分解，算法效率优于现有方法，适用于最多100个变量的中等规模问题。
This paper proposes a decomposition method to compute a lower bound for unconstrained quadratic zero-one minimization. First, we show that any quadratic function can be expressed as a sum of particular quadratic functions whose minima can be computed by a simple branch and bound algorithm. Then, assuming some hypothesis, we prove that, among all possible decompositions, the best one can be found by a Lagrangian decomposition method. Moreover, we show that our algorithm gives at least the roof dual bound and should give better results in practice. Eventually, computational results and comparison with Pardalos and Rodgers' algorithm demonstrate the efficiency of our method for medium size problems (up to 100 variables).