Abstract
We present two theoretically interesting and empirically successful techniques for improving the linear programming approaches, namely graph transformation and local cuts, in the context of the Steiner problem. We show the impact of these techniques on the solution of the largest benchmark instances ever solved.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E. Althaus, T. Polzin, and S. Vahdati Daneshmand. Improving linear programming approaches for the steiner tree problem. Research Report MPI-I-2003-1-004, Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany, February 2003.
Y. P. Aneja. An integer linear programming approach to the Steiner problem in graphs. Networks, 10:167–178, 1980.
D. Applegate, R. Bixby, V. Chvátal, and W. Cook. Finding cuts in the TSP (A preliminary report). Technical report, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, Piscataway, NJ, 1995.
D. Applegate, R. Bixby, V. Chvátal, and W. Cook. TSP cuts which do not conform to the template paradigm. In Michael Junger and Denis Naddef, editors, Computational Combinatorial Optimization, volume 2241 of Lecture Notes in Computer Science. Springer, 2001.
E. Balas and M. Padberg. On the set-covering problem: II. An algorithm for set partitioning. Operations Research, 23:74–90, 1975.
X. Cheng and D.-Z. Du, editors. Steiner Trees in Industry, volume 11 of Combinatorial Optimization. Kluwer Academic Publishers, Dordrecht, 2001.
S. Chopra and M. R. Rao. The Steiner tree problem I: Formulations, compositions and extension of facets. Mathematical Programming, pages 209–229, 1994.
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1990.
C. Gentile, U.-U. Haus, M. Köppe, G. Rinaldi, and R. Weismantel. A primal approach to the stable set problem. In R. Möhring and R. Raman, editors, Algorithms — ESA 2002, volume 2461 of Lecture Notes in Computer Science, pages 525–537, Rom, Italy, 2002. Springer.
U.-U. Haus, M. Köppe, and R. Weismantel. The integral basis method for integer programming. Mathematical Methods of Operations Research, 53(3):353–361, 2001.
F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem, volume 53 of Annals of Discrete Mathematics. North-Holland, Amsterdam, 1992.
R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, New York, 1972.
T. Koch and A. Martin. Solving Steiner tree problems in graphs to optimality. Networks, 32:207–232, 1998.
D. Naddef and S. Thienel. Efficient separation routines for the symmetric traveling salesman problem i: general tools and comb separation. Mathematical Programming, 92(2):237–255, 2002.
D. Naddef and S. Thienel. Efficient separation routines for the symmetric traveling salesman problem ii: separating multi handle inequalities. Mathematical Programming, 92(2):257–283, 2002.
T. Polzin and S. Vahdati Daneshmand. A comparison of Steiner tree relaxations. Discrete Applied Mathematics, 112:241–261, 2001.
T. Polzin and S. Vahdati Daneshmand. Improved algorithms for the Steiner problem in networks. Discrete Applied Mathematics, 112:263–300, 2001.
T. Polzin and S. Vahdati Daneshmand. Partitioning techniques for the Steiner problem. Research Report MPI-I-2001-1-006, Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany, 2001.
T. Polzin and S. Vahdati Daneshmand. Extending reduction techniques for the steiner tree problem. In R. Möhring and R. Raman, editors, Algorithms — ESA 2002, volume 2461 of Lecture Notes in Computer Science, pages 795–807, Rom, Italy, 2002. Springer
T. Polzin and S. Vahdati Daneshmand. On Steiner trees and minimum spanning trees in hypergraphs. Operations Research Letters, 31, 2003.
G. Reinelt. TSPLIB — a traveling salesman problem library. ORSA Journal on Computing, 3:376–384, 1991.
SteinLib. http://elib.zib.de/steinlib, 1997. T. Koch, A. Martin, and S. Voß.
D. M. Warme, P. Winter, and M. Zachariasen. Exact algorithms for plane Steiner tree problems: A computational study. In D-Z. Du, J. M. Smith, and J. H. Rubinstein, editors, Advances in Steiner Trees, pages 81–116. Kluwer Academic Publishers, 2000.
D. M. Warme, P. Winter, and M. Zachariasen. GeoSteiner 3.1. http://www.diku.dk/geosteiner/, 2001.
R. T. Wong. A dual ascent approach for Steiner tree problems on a directed graph. Mathematical Programming, 28:271–287, 1984.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Althaus, E., Polzin, T., Daneshmand, S.V. (2003). Improving Linear Programming Approaches for the Steiner Tree Problem. In: Jansen, K., Margraf, M., Mastrolilli, M., Rolim, J.D.P. (eds) Experimental and Efficient Algorithms. WEA 2003. Lecture Notes in Computer Science, vol 2647. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44867-5_1
Download citation
DOI: https://doi.org/10.1007/3-540-44867-5_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40205-3
Online ISBN: 978-3-540-44867-9
eBook Packages: Springer Book Archive