Packing Steiner Trees: A Cutting Plane Algorithm and Computational Results

Journal article


Publication Details

Author(s): Grötschel M, Martin A, Weismantel R
Journal: Mathematical Programming
Publication year: 1996
Volume: 72
Pages range: 125 - 145
ISSN: 1436-4646
Language: English


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.



FAU Authors / FAU Editors

Martin, Alexander Prof. Dr.
Economics - Discrete Optimization - Mathematics (EDOM)


External institutions with authors

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


How to cite

APA:
Grötschel, M., Martin, A., & Weismantel, R. (1996). Packing Steiner Trees: A Cutting Plane Algorithm and Computational Results. Mathematical Programming, 72, 125 - 145.

MLA:
Grötschel, Martin, Alexander Martin, and Robert Weismantel. "Packing Steiner Trees: A Cutting Plane Algorithm and Computational Results." Mathematical Programming 72 (1996): 125 - 145.

BibTeX: 

Last updated on 2018-07-08 at 16:08