Hostname: page-component-7b7567c8c-48dgx Total loading time: 0 Render date: 2026-11-18T03:22:04.763Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  17 May 2008

Alain Billionnet
Affiliation:
Laboratoire CEDRIC, ENSIIE, 18 allée Jean Rostand, 91025 Evry, France; billionnet@ensiie.fr
Sourour Elloumi
Affiliation:
Laboratoire CEDRIC, Conservatoire National des Arts et Métiers, 292 rue Saint Martin, 75141 Paris, France; e-mail:
Marie-Christine Plateau
Affiliation:
Laboratoire CEDRIC, Conservatoire National des Arts et Métiers, 292 rue Saint Martin, 75141 Paris, France; e-mail:
Get access

Abstract

Many combinatorial optimization problems can be formulated asthe minimization of a 0–1 quadratic function subject to linear constraints. Inthis paper, we are interested in the exact solution of this problem through atwo-phase general scheme. The first phase consists in reformulating theinitial problem either into a compact mixed integer linear program or into a0–1 quadratic convex program. The second phase simply consists insubmitting the reformulated problem to a standard solver. The efficiency ofthis scheme strongly depends on the quality of the reformulation obtained inphase 1. We show that a good compact linear reformulation can be obtained bysolving a continuous linear relaxation of the initial problem. We also showthat a good quadratic convex reformulation can be obtained by solving asemidefinite relaxation. In both cases, the obtained reformulation profitsfrom the quality of the underlying relaxation. Hence, the proposed scheme getsaround, in a sense, the difficulty to incorporate these costly relaxations ina branch-and-bound algorithm.

Information

Type
Research Article
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable