Skip to main content
SpringerLink
Log in

Solving quadratic (0,1)-problems by semidefinite programs and cutting planes

  • Published:
Mathematical Programming Submit manuscript

Abstract

We present computational experiments for solving quadratic (0, 1) problems. Our approach combines a semidefinite relaxation with a cutting plane technique, and is applied in a Branch and Bound setting. Our experiments indicate that this type of approach is very robust, and allows to solve many moderately sized problems, having say, less than 100 binary variables, in a routine manner. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. F. Barahona, The max-cut problem in graphs not contractible toK 5 , Operations Research Letters 2 (1983) 107–111.

    Google Scholar 

  2. F. Barahona, Ground-state magnetization of Ising spin glasses, Physical Reviews B 49 (18) (1994) 12864–12867.

    Google Scholar 

  3. F. Barahona, M. Jünger, G. Reinelt, Experiments in quadratic 0–1 programming, Mathematical Programming 44 (1989) 127–137.

    Google Scholar 

  4. F. Barahona, H. Titan, Max mean cuts and max cuts, Combinatorial Optimization in Science and Technology, 1991, pp. 30–45.

  5. E. Boros, Y. Crama, P.L. Hammer, Chvátal cuts and odd cycle inequalities in quadratic 0–1 optimization, SIAM Journal on Discrete Mathematics 5 (1992) 163–177.

    Google Scholar 

  6. E. Boros, P.L. Hammer, The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds, Annals of Operations Research 33 (1991) 151–180.

    Google Scholar 

  7. E. Boros, P.L. Hammer, cut polytopes, boolean quadric polytopes and nonnegative pseudo-boolean functions, Mathematics of Operations Research 18 (1993) 245–253.

    Google Scholar 

  8. E. Boros, P.L. Hammer, X. Sun, The DDT method for quadratic 0–1 minimization, Technical Report RRR 39-89, Rutgers Unversity, 1989.

  9. M. Burkard, An interior point algorithm for solving max-cut problems, Diploma Thesis, Technical University of Graz, 1994.

  10. M.W. Carter, The indefinite zero–one quadratic problem, Discrete Applied Mathematics 7 (1984) 23–44.

    Google Scholar 

  11. C. Delorme, S. Poljak, Complexity of a max cut approximation, European Journal of Combinatorics 14 (1993) 313–333.

    Google Scholar 

  12. C. Delorme, S. Poljak, Laplacian eigenvalues and the maximum cut problem, Mathematical Programming 62 (1993) 557–574.

    Google Scholar 

  13. C. De Simone, The cut polytope and the boolean quadric polytope, Discrete Applied Mathematics 79 (1989) 71–75.

    Google Scholar 

  14. C. De Simone, M. Diehl, M. Jünger, P. Mutzel, G. Reinelt, G. Rinaldi, Exact ground states of ising spin glasses: new experimental results with a branch-and-cut algorithm, Journal of Statistical Physics 80 (1/2) (1995) 487–496.

    Google Scholar 

  15. C. De Simone, G. Rinaldi, A cutting plane algorithm for the max-cut problem, Optimization Methods and Software 3 (1994) 195–214.

    Google Scholar 

  16. M. Deza, M. Grishuchin, M. Laurent, The hypermetric cone is polyhedral, Combinatorica 13 (1993) 397–411.

    Google Scholar 

  17. M. Deza, M. Laurent, Applications of cut polyhedra I, Journal of Computational and Applied Mathematics 55 (1994) 191–216.

    Google Scholar 

  18. M. Deza, M. Laurent, Applications of cut polyhedra II, Journal of Computational and Applied Mathematics 55 (1994) 217–247.

    Google Scholar 

  19. M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics, vol. 15, Springer, Berlin, 1997.

    Google Scholar 

  20. M.X. Goemans, D.P. Williamson, 0.878-Approximation algorithms for Max-Cut and Max 2SAT, Proceedings of 26th Annual ACM Symposium on Foundations of Computer Science, Computer Science Press, Rockville, MD, 1994, pp. 2–13; see also Journal ACM 42 (1995) 1115–1145.

    Google Scholar 

  21. P.L. Hammer, Some network flow problems solved with pseudo-boolean programming, Operations Research 13 (1965) 388–399.

    Google Scholar 

  22. P.L. Hammer, P. Hansen, B. Simeone, Roof duality, complementation and persistency in quadratic 0–1 optimization, Mathematical Programming 28 (1984) 121–155.

    Google Scholar 

  23. C. Helmberg, An interior point method for semidefinite programming and max-cut bounds, Doctoral Dissertation, University of Technology Graz, 1994.

  24. C. Helmberg, Fixing Variables in Semidefinite Relaxations, Preprint SC 96-43, Konrad-Zuse-Zentrum Berlin, Takustraße 7, D-14195 Berlin, Germany, 1996.

    Google Scholar 

  25. C. Helmberg, S. Poljak, F. Rendl, H. Wolkowicz, Combining semidefinite and polyhedral relaxations for integer programs, in: E. Balas, J. Clausen (Eds), Proceedings of IPCO 4, Lecture Notes in Computer Science 920, 1995, pp. 124–134.

    Google Scholar 

  26. C. Helmberg, F. Rendl, R.J. Vanderbei, H. Wolkowicz, An interior point method for semidefinite programming, SIAM Journal on Optimization 6 (1996) 342–361.

    Google Scholar 

  27. B. Kalantari, A. Bagchi, An algorithm for quadratic zero–one programs, Naval Research Logistics 37 (1990) 527–538.

    Google Scholar 

  28. F. Körner, An efficient branch and bound algorithm to solve quadratic integer programming problem, Computing 30 (1983) 253–260.

    Google Scholar 

  29. M. Laurent, S. Poljak, The metric polytope, in: E. Balas, G. Cornuejols, R. Kannan (Eds.), Proceedings of IPCO 1992, 1992, pp. 274–286.

  30. M. Laurent, S. Poljak, On a positive semidefinite relaxation of the cut polytope, Linear Algebra and Applications 223/224 (1995) 439–461.

    Google Scholar 

  31. M. Laurent, S. Poljak, On the facial structure of the set of correlation matrices, SIAM Journal on Matrix Analysis and Applications 17 (1996) 530–547.

    Google Scholar 

  32. M. Laurent, S. Poljak, F. Rendl, Connections between semidefinite relaxations of the max-cut and stable set problems, Mathematical Programming 77 (1997) 225–246.

    Google Scholar 

  33. T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, Wiley, Chichester, 1990.

    Google Scholar 

  34. B. Mohar, S. Poljak, Eigenvalues and the max-cut problem, Czechoslovak Mathematical Journal 40 (115) (1990) 343–352.

    Google Scholar 

  35. P.M. Pardalos, G.P. Rodgers, Computational aspects of a branch and bound algorithm for quadratic zero–one programming, Computing 45 (1990) 131–144.

    Google Scholar 

  36. P.M. Pardalos, G.P. Rodgers, Parallel branch and bound algorithms for quadratic zero–one programs on the hypercube architecture, Annals of Operations Research 22 (1990) 271–292.

    Google Scholar 

  37. S. Poljak, Polyhedral and eigenvalue approximations of the max-cut problem, in: D. Miklós, G.Halász, L. Lovász, T. Szönyi (Eds.), Sets, Graphs and Numbers, North-Holland, Amsterdam, 1992, pp. 568–581.

    Google Scholar 

  38. S. Poljak, Z. Tuza, On the expected relative error of the polyhedral approximation of the max-cut, Operations Research Letters 16 (1994) 191–198.

    Google Scholar 

  39. S. Poljak, Z. Tuza, Maximum cuts and large bipartite subgraphs, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 20 (1995) 181–244.

    Google Scholar 

  40. S. Poljak, F. Rendl, Node and edge relaxations of the max-cut problem, Computing 52 (1994) 123–137.

    Google Scholar 

  41. S. Poljak, F. Rendl, Nonpolyhedral relaxations of graph bisection problems, SIAM Journal on Optimization 5 (1995) 467–487.

    Google Scholar 

  42. S. Poljak, F. Rendl, Solving the max-cut problem using eigenvalues, Discrete Applied Mathematics 62 (1995) 249–278.

    Google Scholar 

  43. A. Schrijver, personal communication, 1992.

  44. A.C. Williams, Quadratic 0–1 programming using the roof dual with computational results, RUTCOR Research Report 8-85, Rutgers Unversity, 1985.

Download references

Author information

Authors and Affiliations

  1. Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustraβe 7, 14195, Berlin, Germany

    Christoph Helmberg

  2. Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010, Graz, Austria

    Franz Rendl

Authors
  1. Christoph Helmberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Franz Rendl
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Large parts of this paper were prepared while the author was working at the Christian Doppler Laboratory for Discrete Optimization at Technische Universität Graz.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Helmberg, C., Rendl, F. Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Mathematical Programming 82, 291–315 (1998). https://doi.org/10.1007/BF01580072

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01580072

Keywords

Search

Navigation