The Steiner Tree Packing Problem in VLSI-Design

Beitrag in einer Fachzeitschrift


Details zur Publikation

Autor(en): Grötschel M, Martin A, Weismantel R
Zeitschrift: Mathematical Programming
Jahr der Veröffentlichung: 1997
Band: 78
Seitenbereich: 265 - 281
ISSN: 0025-5610
Sprache: Englisch


Abstract


In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.



FAU-Autoren / FAU-Herausgeber

Martin, Alexander Prof. Dr.
Lehrstuhl für Wirtschaftsmathematik


Autor(en) der externen Einrichtung(en)
Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


Zitierweisen

APA:
Grötschel, M., Martin, A., & Weismantel, R. (1997). The Steiner Tree Packing Problem in VLSI-Design. Mathematical Programming, 78, 265 - 281.

MLA:
Grötschel, Martin, Alexander Martin, and Robert Weismantel. "The Steiner Tree Packing Problem in VLSI-Design." Mathematical Programming 78 (1997): 265 - 281.

BibTeX: 

Zuletzt aktualisiert 2018-10-08 um 05:25