ON THE EQUIVALENCE BETWEEN ROOF DUALITY AND LAGRANGIAN-DUALITY FOR UNCONSTRAINED 0-1 QUADRATIC-PROGRAMMING PROBLEMS

We are concerned in this paper with techniques for computing upper bounds on the optimal objective function value to any unconstrained 0-1 quadratic programming problem (maximization). In particular, we 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. We 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 Lagrangian dual of this reformulation. Based on this reformulation, we expand upon the published results.