Branch and cut based on the volume algorithm : Steiner trees in graphs and max-cut
RAIRO - Operations Research - Recherche Opérationnelle, Volume 40 (2006) no. 1, p. 53-73

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.

@article{RO_2006__40_1_53_0,
     author = {Barahona, Francisco and Lad\'anyi, L\'aszl\'o},
     title = {Branch and cut based on the volume algorithm : Steiner trees in graphs and max-cut},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {1},
     year = {2006},
     pages = {53-73},
     doi = {10.1051/ro:2006010},
     zbl = {pre05140666},
     mrnumber = {2248422},
     language = {en},
     url = {http://www.numdam.org/item/RO_2006__40_1_53_0}
}
Barahona, Francisco; Ladányi, László. Branch and cut based on the volume algorithm : Steiner trees in graphs and max-cut. RAIRO - Operations Research - Recherche Opérationnelle, Volume 40 (2006) no. 1, pp. 53-73. doi : 10.1051/ro:2006010. http://www.numdam.org/item/RO_2006__40_1_53_0/

[1] Y.P. Aneja, An integer linear programming approach to the Steiner problem in graphs. Networks 20 (1980) 167-178. | Zbl 0445.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 Mathematicians III (1998) 645-656. | Zbl 0904.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. | Zbl 1175.90393 | Zbl pre02021965

[4] L. Bahiense, N. Maculan and C. Sagastizábal, The volume algorithm revisited: relation with bundle methods. Math. Program. 94 (2002) 41-69. | Zbl 1023.90038

[5] F. Barahona, Ground state magnetization of Ising spin glasses. Phys. Rev. B 49 (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. | Zbl 0961.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). | Zbl 0995.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. | Zbl 0646.90084

[9] F. Barahona, M. Jünger and G. Reinelt, Experiments in quadratic 0-1 programming. Math. Program. 44 (1989) 127-137. | Zbl 0677.90046

[10] F. Barahona and A. Mahjoub, On the cut polytope. Math. Program. 36 (1986) 157-173. | Zbl 0616.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. | Zbl 1068.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. | Zbl 0759.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. | Zbl 1106.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).

[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. | Zbl 0155.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. | Zbl 0833.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. | Zbl 1131.90442

[21] M.X. Goemans and Y.S. Myung, A catalog of Steiner tree formulations, Networks 23 (1993), pp. 19-28. | Zbl 0794.90074

[22] M. Guignard, Efficient cuts in lagrangean “Relax-and-Cut” schemes. Eur. J. Oper. Res. 105 (1998) 216-223. | Zbl 0957.90091

[23] M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees. Oper. Res. 18 (1970) 1138-1162. | Zbl 0226.90047

[24] M. Held and R.M. Karp, The travelling salesman problem and minimum spanning trees: Part II. Math. Program. 1 (1971) 6-25. | Zbl 0232.90038

[25] M. Held, P. Wolfe and H.P. Crowder, Validation of subgradient optimization. Math. Program. 6 (1974) 62-88. | Zbl 0284.90057

[26] C. Helmberg and F. Rendl, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. 82 (1998) 291-315. | Zbl 0919.90112

[27] T. Koch and A. Martin, Steinlib, http://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. | Zbl 1002.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. Netflow 93 (1993) 147-154.

[32] A. Lucena. and J. Beasley, A branch-and-cut algorithm for the Steiner problem in graphs. Networks 31 (1998), pp. 39-59. | Zbl 0894.90155

[33] J.E. Mitchell, Computational experience with an interior point cutting plane algorithm. SIAM J. Optim. 10 (2000) 1212-1227. | Zbl 0999.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. | Zbl 0734.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). | Zbl 0994.90135

[36] H. Takahashi and A. Matsuyama, An approximated solution for the Steiner tree problem in graphs, Math. Japonica 254 (1980) 573-577. | Zbl 0435.05036

[37] E. Uchoa, M. Poggi De Aragão and C.C. Ribeiro, Preprocessing Steiner problems from VLSI layout, Networks 40 (2002) 38-50. | Zbl 1064.68007

[38] P. Wolfe, A method of conjugate subgradients for minimizing nondifferentiable functions. Math. Program. Study 3 (1975) 145-173. | Zbl 0369.90093