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, the authors 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, they prove that, among all possible decompositions, the best one can be found by a Lagrangian decomposition method. Moreover, the authors show that the algorithm gives at least the roof dual bound and should give better results in practice. Eventually, computational results and comparisons with Pardalos and Rodgers’ algorithm demonstrate the efficiency of the present method for medium size problems (up to 100 variables).