Packing Steiner trees: a cutting plane algorithm and computational results |
| |
Authors: | M Grötschel A Martin R Weismantel |
| |
Institution: | 1. Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustra?e 7, 14195, Berlin, Germany
|
| |
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 (this issue) and meant to turn this theory into an
algorithmic tool for the solution of practical problems. |
| |
Keywords: | Branch and cut Packing Routing Separation Steiner tree VLSI-design |
本文献已被 SpringerLink 等数据库收录! |