|
 
|
[BEP08] Quadratic 0-1 programming : tightening linear or quadratic convex reformulation by use of relaxations
Revue Internationale avec comité de lecture : Journal RAIRO, vol. 42(2), pp. 103-121, 2008, (doi:10.1051/ro:2008011)Mots clés: Combinatorial optimization; quadratic 0–1 programming; linear reformulation; quadratic convex reformulation.
Résumé:
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.
Equipe:
oc
BibTeX
| @article { | |||
| BEP08, | |||
| title | = | "{Quadratic 0-1 programming : tightening linear or quadratic convex reformulation by use of relaxations}", | |
| author | = | "A. Billionnet and S. Elloumi and M. Plateau", | |
| journal | = | "RAIRO", | |
| year | = | 2008, | |
| volume | = | 42, | |
| number | = | 2, | |
| pages | = | "103-121", | |
| doi | = | "10.1051/ro:2008011", | |
| } | |||
