Invited talk at ISMP00, 17th International Symposium on Mathematical Programming, Atlanta, GA, August 7-11, 2000.

(The Abstract (text file):; the presentation (ps file))

This talk is based on several papers; principally, on the papers dealing with the strength of Lagrangian Relaxations: The paper
A RECIPE FOR BEST SEMIDEFINITE RELAXATION FOR (0,1)-QUADRATIC PROGRAMMING
and the two papers:
On Lagrangian Relaxation of Quadratic Matrix Constraints and
Strong Duality for a Trust-Region Type Relaxation of the Quadratic Assignment Problem
A summary of these results is presented in
Semidefinite and Lagrangian Relaxations for Hard Combinatorial Problems (in Proceedings of 19th IFIP TC7 CONFERENCE ON Semidefinite Programming), Kluwer Academic, 2000.