Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut

Francisco Barahona; László Ladányi

RAIRO - Operations Research (2006)

  • Volume: 40, Issue: 1, page 53-73
  • ISSN: 0399-0559

Abstract

top
We present a Branch-and-Cut algorithm where the volume algorithm is applied instead of the traditionally used dual simplex algorithm to the linear programming relaxations in the root node of the search tree. This means that we use fast approximate solutions to these linear programs instead of exact but slower solutions. We present computational results with the Steiner tree and Max-Cut problems. We show evidence that one can solve these problems much faster with the volume algorithm based Branch-and-Cut code than with a dual simplex based one. We discuss when the volume based approach might be more efficient than the simplex based approach.

How to cite

top

Barahona, Francisco, and Ladányi, László. "Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut." RAIRO - Operations Research 40.1 (2006): 53-73. <http://eudml.org/doc/249757>.

@article{Barahona2006,
abstract = { We present a Branch-and-Cut algorithm where the volume algorithm is applied instead of the traditionally used dual simplex algorithm to the linear programming relaxations in the root node of the search tree. This means that we use fast approximate solutions to these linear programs instead of exact but slower solutions. We present computational results with the Steiner tree and Max-Cut problems. We show evidence that one can solve these problems much faster with the volume algorithm based Branch-and-Cut code than with a dual simplex based one. We discuss when the volume based approach might be more efficient than the simplex based approach. },
author = {Barahona, Francisco, Ladányi, László},
journal = {RAIRO - Operations Research},
keywords = {Volume algorithm; Steiner tree; Max-Cut},
language = {eng},
month = {7},
number = {1},
pages = {53-73},
publisher = {EDP Sciences},
title = {Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut},
url = {http://eudml.org/doc/249757},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Barahona, Francisco
AU - Ladányi, László
TI - Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
JO - RAIRO - Operations Research
DA - 2006/7//
PB - EDP Sciences
VL - 40
IS - 1
SP - 53
EP - 73
AB - We present a Branch-and-Cut algorithm where the volume algorithm is applied instead of the traditionally used dual simplex algorithm to the linear programming relaxations in the root node of the search tree. This means that we use fast approximate solutions to these linear programs instead of exact but slower solutions. We present computational results with the Steiner tree and Max-Cut problems. We show evidence that one can solve these problems much faster with the volume algorithm based Branch-and-Cut code than with a dual simplex based one. We discuss when the volume based approach might be more efficient than the simplex based approach.
LA - eng
KW - Volume algorithm; Steiner tree; Max-Cut
UR - http://eudml.org/doc/249757
ER -

References

top
  1. Y.P. Aneja, An integer linear programming approach to the Steiner problem in graphs. Networks20 (1980) 167–178.  Zbl0445.90087
  2. D. Applegate, R. Bixby, V. Chvátal and W. Cook, On the solution of traveling salesman problems, in Proc. of the International Congress of MathematiciansIII (1998) 645–656.  Zbl0904.90165
  3. L. Bahiense, F. Barahona and O. Porto, Solving Steiner tree problems in graphs with Lagrangian relaxation. J. Comb. Optim.7 (2003) 259–282.  Zbl1175.90393
  4. L. Bahiense, N. Maculan and C. Sagastizábal, The volume algorithm revisited: relation with bundle methods. Math. Program.94 (2002) 41–69.  Zbl1023.90038
  5. F. Barahona, Ground state magnetization of Ising spin glasses. Phys. Rev. B49 (1994) 2864–2867.  
  6. F. Barahona and R. Anbil, The volume algorithm: producing primal solutions with a subgradient method. Math. Program.87 (2000) 385–399.  Zbl0961.90058
  7. F. Barahona and R. Anbil, On some difficult linear programs coming from set partitioning. Discrete Appl. Math.118 (2002) 3–11. Third ALIO-EURO Meeting on Applied Combinatorial Optimization (Erice, 1999).  Zbl0995.90069
  8. F. Barahona, M. Grötschel, M. Jünger and G. Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design, Oper. Res.36 (1988) 493–513.  Zbl0646.90084
  9. F. Barahona, M. Jünger and G. Reinelt, Experiments in quadratic 0-1 programming. Math. Program.44 (1989) 127–137.  Zbl0677.90046
  10. F. Barahona and A. Mahjoub, On the cut polytope. Math. Program.36 (1986) 157–173.  Zbl0616.90058
  11. A. Caprara and M. Fischetti, Branch-and-cut algorithms, in Annotated Bibliographies in Combinatorial Optimization, edited by M.D. Amico, F. Maffioli and S. Martello, Wiley (1997) 45–63.  Zbl1068.90505
  12. S. Chopra, E.R. Gorres and M.R. Rao, Solving the Steiner tree problem in graphs using branch-and-cut. ORSA J. Comput.4 (1992) 320–335.  Zbl0759.90091
  13. COIN-OR, http:www.coin-or.org.  
  14. C. De Simone, M. Diehl, M. Jünger, P. Mutzel, G. Reinelt and G. Rinaldi, Exact ground states of Ising spin glasses: New experimental results with a branch and cut algorithm. J. Stat. Phys.80 (1995) 487–496.  Zbl1106.82323
  15. C. De Simone, M. Diehl, M. Jünger, P. Mutzel, G. Reinelt and G. Rinaldi, Exact ground states of two-dimensional +–J Ising spin glasses. J. Stat. Phys. (1996).  Zbl1260.82083
  16. C. De Simone and G. Rinaldi, A cutting plane algorithm for the max-cut problem. Optim. Method. Softw.3 (1994) 195–214.  
  17. J. Edmonds, Optimum branchings. J. Res. Natl. Bur. Stand.71B (1967) 233–240.  Zbl0155.51204
  18. L.F. Escudero, M. Guignard and K. Malik, A Lagrangean relax-and-cut approach for the sequential ordering problem with precedence relations. Ann. Oper. Res.50 (1994) 219–237.  Zbl0833.90068
  19. J.J. Forrest, The COIN-OR Linear Program Solver (CLP), INFORMS Atlanta, (2003).  
  20. A. Frangioni, A. Lodi and G. Rinaldi, Optimizing over semimetric polytopes, in Integer programming and combinatorial optimization, Springer, Berlin Lect. Notes Comput. Sci.3064 (2004) 431–443.  Zbl1131.90442
  21. M.X. Goemans and Y.S. Myung, A catalog of Steiner tree formulations, Networks23 (1993), pp. 19–28.  Zbl0794.90074
  22. M. Guignard, Efficient cuts in lagrangean “Relax-and-Cut" schemes. Eur. J. Oper. Res.105 (1998) 216–223.  Zbl0957.90091
  23. M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees. Oper. Res.18 (1970) 1138–1162.  Zbl0226.90047
  24. M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees: Part II. Math. Program.1 (1971) 6–25.  Zbl0232.90038
  25. M. Held, P. Wolfe and H.P. Crowder, Validation of subgradient optimization. Math. Program.6 (1974) 62–88.  Zbl0284.90057
  26. C. Helmberg and F. Rendl, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program.82 (1998) 291–315.  Zbl0919.90112
  27. T. Koch and A. Martin, Steinlib, .  URIhttp://elib.zib.de/steinlib/steinlib.php
  28. T. Koch and A. Martin, Solving Steiner tree problems in graphs to optimality, Networks 32 (1998) 207–232.  Zbl1002.90078
  29. C. Lemaréchal, Nondifferentiable optimization, in Optimization, Hanbooks Oper. Res., edited by G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, North Holland, 1989, pp. 529–572.  
  30. A. Lucena, Steiner problem in graphs: Lagrangian relaxation and cutting-planes, COAL Bull. 21 (1992) 2–7.  
  31. A. Lucena, Tight bounds for the Steiner problem in graphs, in Proc. Netflow93 (1993) 147–154.  
  32. A. Lucena. and J. Beasley, A branch-and-cut algorithm for the Steiner problem in graphs. Networks31 (1998), pp. 39–59.  Zbl0894.90155
  33. J.E. Mitchell, Computational experience with an interior point cutting plane algorithm. SIAM J. Optim.10 (2000) 1212–1227.  Zbl0999.90050
  34. M. Padberg and G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev.33 (1991) 60–100.  Zbl0734.90060
  35. T. Polzin and S.V. Daneshmand, Improved algorithms for the Steiner problem in networks. Discrete Appl. Math.112 (2001) 263–300. Combinatorial Optimization Symposium (Brussels, 1998).  Zbl0994.90135
  36. H. Takahashi and A. Matsuyama, An approximated solution for the Steiner tree problem in graphs, Math. Japonica254 (1980) 573–577.  Zbl0435.05036
  37. E. Uchoa, M. Poggi de Aragão and C.C. Ribeiro, Preprocessing Steiner problems from VLSI layout, Networks40 (2002) 38–50.  Zbl1064.68007
  38. P. Wolfe, A method of conjugate subgradients for minimizing nondifferentiable functions. Math. Program. Study3 (1975) 145–173.  Zbl0369.90093

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.