Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results.
Please always quote using this URN: urn:nbn:de:0297-zib-792
- In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper SC 92-8 and meant to turn this theory into an algorithmic tool for the solution of practical problems.
Download full text files
Additional Services
| Author: | Martin Grötschel, Alexander Martin, Robert Weismantel |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1992/04/09 |
| Series (Serial Number): | ZIB-Report (SC-92-09) |
| ZIB-Reportnumber: | SC-92-09 |
| Published in: | Appeared in: Mathematical Programming 72 (1996) 125-145 |
