Article ID: | iaor19972040 |
Country: | Netherlands |
Volume: | 72 |
Issue: | 2 |
Start Page Number: | 125 |
End Page Number: | 145 |
Publication Date: | Feb 1996 |
Journal: | Mathematical Programming (Series A) |
Authors: | Grtschel M., Martin A., Weismantel R. |
Keywords: | Steiner problem |
In this paper the authors describe a cutting plane algorithm for the Steiner tree packing problem. They use our algorithm to solve some switchbox routing problems of VLSI-design and report on the present 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 and meant to turn this theory into an algorithmic tool for the solution of practical problems. (See also previous abstract)