Article ID: | iaor20091412 |
Country: | France |
Volume: | 42 |
Issue: | 2 |
Start Page Number: | 103 |
End Page Number: | 121 |
Publication Date: | Apr 2008 |
Journal: | RAIRO Operations Research |
Authors: | Billionnet Alain, Elloumi Sourour, Plateau Marie-Christine |
Many combinatorial optimization problems can be formulated as the minimization of a 0–1 quadratic function subject to linear constraints. In this paper, we are interested in the exact solution of this problem through a two-phase general scheme. The first phase consists in reformulating the initial problem either into a compact mixed integer linear program or into a 0–1 quadratic convex program. The second phase simply consists in submitting the reformulated problem to a standard solver. The efficiency of this scheme strongly depends on the quality of the reformulation obtained in phase 1. We show that a good compact linear reformulation can be obtained by solving a continuous linear relaxation of the initial problem. We also show that a good quadratic convex reformulation can be obtained by solving a semidefinite relaxation. In both cases, the obtained reformulation profits from the quality of the underlying relaxation. Hence, the proposed scheme gets around, in a sense, the difficulty to incorporate these costly relaxations in a branch-and-bound algorithm.