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

Abstract

top
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.

How to cite

top

Billionnet, 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
  1. 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.  
  2. 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.  
  3. W.P. Adams and H.D. Sherali, Mixed-integer bilinear programming problems. Math. Program.59 (1993) 279–305.  
  4. 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).  
  5. 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.  
  6. 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
  7. 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
  8. 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.  
  9. M.W. Carter, The indefinite zero-one quadratic problem. Discrete Appl. Math.7 (1984) 23–44.  
  10. 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
  11. 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.  
  12. 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.  
  13. M. Garey and D. Johnson, Computers and intractibility: a guide to the theroy of np-completeness. W.H. freeman & Co. (1979).  
  14. F. Glover, Improved linear integer programming formulation of non linear integer problems. Manage. Sci.22 (1975) 445–460.  
  15. F. Glover, G.A. Kochenberger and B. Alidaee, Adaptative memory tabu search for binary quadratic programs. Manage. Sci.44 (1998) 336–345.  
  16. S. Gueye and P. Michelon, Miniaturized linearizations for quadratic 0/1 problems. Ann. Oper. Res.140 (2005) 235–261.  
  17. P.L. Hammer and A.A. Rubin, Some remarks on quadratic programming with 0-1 variables. RAIRO3 (1970) 67–79.  
  18. P.L. Hammer, P. Hansen and B. Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization. Math. Program.28 (1984) 121–155.  
  19. 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.  
  20. B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal49 (1970) 291–307.  
  21. A. Lodi, K. Allemand and T.M. Liebling, An evolutionary heuristic for quadratic 0-1 programming. Eur. J. Oper. Res.119 (1999) 662–670.  
  22. L. Lovász and S. Schrijver, Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim.1 (1991) 166–190.  
  23. P. Merz and B. Freisleben, Greedy and local search heuristics for unconstrained quadratic programming. J. Heuristics8 (2002) 197–213.  
  24. 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
  25. H.D. Sherali and W.P. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publ., Norwell, MA (1999).  
  26. H.D. Sherali and H. Tuncbilek, A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim.7 (1995) 1–31.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.