Packing Steiner Trees: A Cutting Plane Algorithm and Computational Results

Grötschel M, Martin A, Weismantel R (1996)


Publication Language: English

Publication Type: Journal article

Publication year: 1996

Journal

Book Volume: 72

Pages Range: 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 (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.

Authors with CRIS profile

Involved external institutions

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: Download