×

Improving linear programming approaches for the Steiner tree problem. (English) Zbl 1023.90529

Jansen, Klaus (ed.) et al., Experimental and efficient algorithms. Second international workshop, WEA 2003, Ascona, Switzerland, May 26-28, 2003. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2647, 1-14 (2003).
Summary: 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.
For the entire collection see [Zbl 1019.00014].

MSC:

90C27 Combinatorial optimization
90C05 Linear programming
68R10 Graph theory (including graph drawing) in computer science

Software:

GeoSteiner; TSPLIB
PDFBibTeX XMLCite
Full Text: Link