# 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

top## Abstract

top## How 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. Zbl1091.90040
- 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. Zbl0623.90054
- W.P. Adams and H.D. Sherali, Mixed-integer bilinear programming problems. Math. Program.59 (1993) 279–305. Zbl0801.90085
- 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. Zbl1278.90263
- 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). Zbl1169.90405URIhttp://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). Zbl1169.90405URIhttp://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. Zbl1239.90075
- M.W. Carter, The indefinite zero-one quadratic problem. Discrete Appl. Math.7 (1984) 23–44. Zbl0524.90061
- 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. Zbl0093.32704
- 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. Zbl0989.90072
- S. Gueye and P. Michelon, Miniaturized linearizations for quadratic 0/1 problems. Ann. Oper. Res.140 (2005) 235–261. Zbl1091.90043
- P.L. Hammer and A.A. Rubin, Some remarks on quadratic programming with 0-1 variables. RAIRO3 (1970) 67–79. Zbl0211.52104
- P.L. Hammer, P. Hansen and B. Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization. Math. Program.28 (1984) 121–155. Zbl0574.90066
- 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. Zbl0698.90065
- B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal49 (1970) 291–307. Zbl0333.05001
- A. Lodi, K. Allemand and T.M. Liebling, An evolutionary heuristic for quadratic 0-1 programming. Eur. J. Oper. Res.119 (1999) 662–670. Zbl0938.90051
- L. Lovász and S. Schrijver, Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim.1 (1991) 166–190. Zbl0754.90039
- P. Merz and B. Freisleben, Greedy and local search heuristics for unconstrained quadratic programming. J. Heuristics8 (2002) 197–213. Zbl1013.90100
- 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). Zbl0926.90078
- H.D. Sherali and H. Tuncbilek, A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim.7 (1995) 1–31. Zbl0844.90064

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.