Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations

Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations

0.00 Avg rating0 Votes
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: , ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.