Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results.
Appeared in: Mathematical Programming 72 (1996) 125-145
| SC 92-09 | Martin Grötschel, Alexander Martin, Robert Weismantel
Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results. Appeared in: Mathematical Programming 72 (1996) 125-145 | |
Abstract: 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.