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},
pages = {53--73},
publisher = {EDP-Sciences},
volume = {40},
number = {1},
year = {2006},
doi = {10.1051/ro:2006010},
mrnumber = {2248422},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2006010/}
}
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 - Recherche Opérationnelle PY - 2006 SP - 53 EP - 73 VL - 40 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2006010/ DO - 10.1051/ro:2006010 LA - en ID - RO_2006__40_1_53_0 ER -
%0 Journal Article %A Barahona, Francisco %A Ladányi, László %T Branch and cut based on the volume algorithm : Steiner trees in graphs and max-cut %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 53-73 %V 40 %N 1 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2006010/ %R 10.1051/ro:2006010 %G en %F 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, Tome 40 (2006) no. 1, pp. 53-73. doi : 10.1051/ro:2006010. http://www.numdam.org/articles/10.1051/ro:2006010/
[1] , An integer linear programming approach to the Steiner problem in graphs. Networks 20 (1980) 167-178. | Zbl
[2] ,, and, On the solution of traveling salesman problems, in Proc. of the International Congress of Mathematicians III (1998) 645-656. | EuDML | Zbl
[3] , and, Solving Steiner tree problems in graphs with Lagrangian relaxation. J. Comb. Optim. 7 (2003) 259-282. | Zbl
[4] , and, The volume algorithm revisited: relation with bundle methods. Math. Program. 94 (2002) 41-69. | Zbl
[5] , Ground state magnetization of Ising spin glasses. Phys. Rev. B 49 (1994) 2864-2867.
[6] and, The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87 (2000) 385-399. | Zbl
[7] and, 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
[8] ,, and. An application of combinatorial optimization to statistical physics and circuit layout design, Oper. Res. 36 (1988) 493-513. | Zbl
[9] , and, Experiments in quadratic 0-1 programming. Math. Program. 44 (1989) 127-137. | Zbl
[10] and, On the cut polytope. Math. Program. 36 (1986) 157-173. | Zbl
[11] and, 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
[12] , and, Solving the Steiner tree problem in graphs using branch-and-cut. ORSA J. Comput. 4 (1992) 320-335. | Zbl
[13] COIN-OR, http:www.coin-or.org.
[14] ,,,, and, Exact ground states of Ising spin glasses: New experimental results with a branch and cut algorithm. J. Stat. Phys. 80 (1995) 487-496. | Zbl
[15] ,,,, and, Exact ground states of two-dimensional +-J Ising spin glasses. J. Stat. Phys. (1996).
[16] and, A cutting plane algorithm for the max-cut problem. Optim. Method. Softw. 3 (1994) 195-214.
[17] , Optimum branchings. J. Res. Natl. Bur. Stand. 71B (1967) 233-240. | Zbl
[18] , and, A Lagrangean relax-and-cut approach for the sequential ordering problem with precedence relations. Ann. Oper. Res. 50 (1994) 219-237. | Zbl
[19] , The COIN-OR Linear Program Solver (CLP), INFORMS Atlanta, (2003).
[20] , and, Optimizing over semimetric polytopes, in Integer programming and combinatorial optimization, Springer, Berlin Lect. Notes Comput. Sci. 3064 (2004) 431-443. | Zbl
[21] and, A catalog of Steiner tree formulations, Networks 23 (1993), pp. 19-28. | Zbl
[22] , Efficient cuts in lagrangean “Relax-and-Cut” schemes. Eur. J. Oper. Res. 105 (1998) 216-223. | Zbl
[23] and, The travelling salesman problem and minimum spanning trees. Oper. Res. 18 (1970) 1138-1162. | Zbl
[24] and, The travelling salesman problem and minimum spanning trees: Part II. Math. Program. 1 (1971) 6-25. | Zbl
[25] , and, Validation of subgradient optimization. Math. Program. 6 (1974) 62-88. | Zbl
[26] and, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. 82 (1998) 291-315. | Zbl
[27] and, Steinlib, http://elib.zib.de/steinlib/steinlib.php.
[28] and, Solving Steiner tree problems in graphs to optimality, Networks 32 (1998) 207-232. | Zbl
[29] , 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] , Steiner problem in graphs: Lagrangian relaxation and cutting-planes, COAL Bull. 21 (1992) 2-7.
[31] , Tight bounds for the Steiner problem in graphs, in Proc. Netflow 93 (1993) 147-154.
[32] . and J. Beasley, A branch-and-cut algorithm for the Steiner problem in graphs. Networks 31 (1998), pp. 39-59. | Zbl
[33] , Computational experience with an interior point cutting plane algorithm. SIAM J. Optim. 10 (2000) 1212-1227. | Zbl
[34] and, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33 (1991) 60-100. | Zbl
[35] and, Improved algorithms for the Steiner problem in networks. Discrete Appl. Math. 112 (2001) 263-300. Combinatorial Optimization Symposium (Brussels, 1998). | Zbl
[36] and, An approximated solution for the Steiner tree problem in graphs, Math. Japonica 254 (1980) 573-577. | Zbl
[37] , and, Preprocessing Steiner problems from VLSI layout, Networks 40 (2002) 38-50. | Zbl
[38] , A method of conjugate subgradients for minimizing nondifferentiable functions. Math. Program. Study 3 (1975) 145-173. | Zbl
Cité par Sources :
