Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization

C. Lemarechal and F. Oustry

We show that it is fruitful to dualize the integrality constraints in a combinatorial optimization problem. First, this reproduces the known SDP relaxations of the max-cut and max-stable problems. Then we apply the approach to general combinatorial problems. We show that the resulting duality gap is smaller than with the classical Lagrangian relaxation; we also show that linear constraints need a special treatment. The aim of this paper is twofold: 1) to show that some of the well-known SDP relaxations of combinatorial problems (max-cut, max-stable) are particular instances of a general technique: Lagrangian duality; 2) to apply this latter technique to rather arbitrary combinatorial problems, thereby proposing relaxation schemes which turn out to be finer than the classical ones. A third aspect of this paper is clarification : we present Lagrangian and SDP duality in a common framework, as simple as possible, and we demonstrate how to apply the ``recipe'' of Poljak, Rendl and Wolkowicz.

RR-3710, INRIA Rhone-Alpes ZIRST - 655 avenue de l'Europe F-38330 Montbonnot Saint-Martin, June 1999