Packing Steiner Trees: A Cutting Plane Algorithm and Computational Results

Beitrag in einer Fachzeitschrift


Details zur Publikation

Autorinnen und Autoren: Grötschel M, Martin A, Weismantel R
Zeitschrift: Mathematical Programming
Jahr der Veröffentlichung: 1996
Band: 72
Seitenbereich: 125 - 145
ISSN: 1436-4646
Sprache: Englisch


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-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Martin, Alexander Prof. Dr.
Lehrstuhl für Angewandte Mathematik (Gemischt-ganzzahlige lineare und nichtlineare Optimierung)


Einrichtungen weiterer Autorinnen und Autoren

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


Zitierweisen

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: 

Zuletzt aktualisiert 2018-07-08 um 16:08