On the equivalence between roof duality and Lagrangean duality for unconstrained 0-1 quadratic programming problems

In this paper the authors are concerned with techniques for computing upper bounds on the optimal objective function value to any unconstrained 0-1 quadratic programming problem (maximization). In particular, they study three methods for obtaining upper bounds as presented in a recent paper by Hammer, Hansen, and Simeone: (1) generating two classes of upper-bounding linear functions referred to as paved upper planes and roofs, (2) solving the continuous relaxation of a mixed-integer linear problem by Rhys, and (3) the quadratic complementation of variables which results in a bound called the height. The authors show that all three methods directly result from standard properties of a reformulation of the quadratic problem as a mixed-integer linear program, with methods (1) and (3) resulting from a Lagrangean dual of this reformulation. Based on this reformulation, they expand upon the published results.