A Decomposition Method for Quadratic Zero-One Programming

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).