Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
Alain Billionnet; Sourour Elloumi; Marie-Christine Plateau
RAIRO - Operations Research (2008)
- Volume: 42, Issue: 2, page 103-121
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topBillionnet, Alain, Elloumi, Sourour, and Plateau, Marie-Christine. "Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations." RAIRO - Operations Research 42.2 (2008): 103-121. <http://eudml.org/doc/250384>.
@article{Billionnet2008,
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.
},
author = {Billionnet, Alain, Elloumi, Sourour, Plateau, Marie-Christine},
journal = {RAIRO - Operations Research},
keywords = {Combinatorial optimization; quadratic 0–1 programming; linear reformulation; quadratic convex reformulation.; combinatorial optimization; quadratic 0-1 programming; quadratic convex reformulation},
language = {eng},
month = {5},
number = {2},
pages = {103-121},
publisher = {EDP Sciences},
title = {Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations},
url = {http://eudml.org/doc/250384},
volume = {42},
year = {2008},
}
TY - JOUR
AU - Billionnet, Alain
AU - Elloumi, Sourour
AU - Plateau, Marie-Christine
TI - Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
JO - RAIRO - Operations Research
DA - 2008/5//
PB - EDP Sciences
VL - 42
IS - 2
SP - 103
EP - 121
AB -
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.
LA - eng
KW - Combinatorial optimization; quadratic 0–1 programming; linear reformulation; quadratic convex reformulation.; combinatorial optimization; quadratic 0-1 programming; quadratic convex reformulation
UR - http://eudml.org/doc/250384
ER -
References
top- W.P. Adams, R. Forrester and F. Glover, Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs. Discrete Optim.1(2) (2004) 99–120.
- W.P. Adams and H.D. Sherali, A tight linearization and an algorithm for 0–1 quadratic programming problems. Manage. Sci.32 (1986) 1274–1290.
- W.P. Adams and H.D. Sherali, Mixed-integer bilinear programming problems. Math. Program.59 (1993) 279–305.
- J.E. Beasley, Heuristic algorithms for the unconstrained binary quadratic programming problem. Technical report, Department of Mathematics, Imperial College of Science and Technology, London, England (1998).
- A. Billionnet and S. Elloumi, Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem. Math. Program.109 (2007) 55–68.
- A. Billionnet, S. Elloumi and M.C. Plateau, Improving the performance of standard solvers for quadratic 0-1 programs by a toight convex reformulation: the QCR method. Discrete Appl. Math., (to appear). URIhttp://dx.doi.org/10.1016/j.dam.2007.007
- A. Billionnet, S. Elloumi and M.C. Plateau, Quadratic convex reformulation: a computational study of the graph bisection problem. Technical Report CEDRIC, (2005). URIhttp://cedric.cnam.fr/PUBLIS/RC1003.pdf
- A. Billionnet and E. Soutif, Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem. INFORMS J. Comput.16 (2004) 188–197.
- M.W. Carter, The indefinite zero-one quadratic problem. Discrete Appl. Math.7 (1984) 23–44.
- S. Elloumi, Linear programming versus convex quadratic programming for the module allocation problem. Technical Report CEDRIC 1100, (2005). URIhttp://cedric.cnam.fr/PUBLIS/RC1100.pdf
- R. Fortet, Applications de l'algèbre de boole en recherche opérationnelle. Rev. Fr. d'Automatique d'Informatique et de Recherche Opérationnelle4 (1959) 5–36.
- R. Fortet, L'algèbre de boole et ses applications en recherche opérationnelle. Cahiers du Centre d'Etudes de Recherche Opérationnelle4 (1960) 17–26.
- M. Garey and D. Johnson, Computers and intractibility: a guide to the theroy of np-completeness. W.H. freeman & Co. (1979).
- F. Glover, Improved linear integer programming formulation of non linear integer problems. Manage. Sci.22 (1975) 445–460.
- F. Glover, G.A. Kochenberger and B. Alidaee, Adaptative memory tabu search for binary quadratic programs. Manage. Sci.44 (1998) 336–345.
- S. Gueye and P. Michelon, Miniaturized linearizations for quadratic 0/1 problems. Ann. Oper. Res.140 (2005) 235–261.
- P.L. Hammer and A.A. Rubin, Some remarks on quadratic programming with 0-1 variables. RAIRO3 (1970) 67–79.
- P.L. Hammer, P. Hansen and B. Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization. Math. Program.28 (1984) 121–155.
- D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: an experimental evaluation; part1, graph partitioning. Oper. Res.37 (1989) 865–892.
- B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal49 (1970) 291–307.
- A. Lodi, K. Allemand and T.M. Liebling, An evolutionary heuristic for quadratic 0-1 programming. Eur. J. Oper. Res.119 (1999) 662–670.
- L. Lovász and S. Schrijver, Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim.1 (1991) 166–190.
- P. Merz and B. Freisleben, Greedy and local search heuristics for unconstrained quadratic programming. J. Heuristics8 (2002) 197–213.
- M.C. Plateau, A. Billionnet and S. Elloumi, Eigenvalue methods for linearly constrained quadratic 0-1 problems with application to the densest k-subgraph problem. In 6e congrès ROADEF, Tours, 14–16 février, Presses Universitaires Francois Rabelais, (2005) 55–66. URIhttp://cedric.cnam.fr/PUBLIS/RC723.pdf
- H.D. Sherali and W.P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publ., Norwell, MA (1999).
- H.D. Sherali and H. Tuncbilek, A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim.7 (1995) 1–31.
Citations in EuDML Documents
topNotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.