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 bou nds on the optimal objective function value to any unconstrained 0-1 q uadratic programming problem (maximization). In particular, we study t hree methods for obtaining upper bounds as presented in a recent paper by Hammer, Hansen, and Simeone: (1) generating two classes of upper-b ounding linear functions referred to as paved upper planes and roofs, (2) solving the continuous relaxation of a mixed-integer linear proble m by Rhys, and (3) the quadratic complementation of variables which re sults in a bound called the height. We show that all three methods dir ectly result from standard properties of a reformulation of the quadra tic problem as a mixed-integer linear program, with methods (1) and (3 ) resulting from a Lagrangian dual of this reformulation. Based on thi s reformulation, we expand upon the published results.