Packing Steiner Trees: Separation Algorithms.
Please always quote using this URN: urn:nbn:de:0297-zib-984
- In this paper we investigate separation problems for classes of inequalities valid for the polytope associated with the Steiner tree packing problem, a problem that arises, e.~g., in VLSI routing. The separation problem for Steiner partition inequalities is ${\cal N}\hskip-2pt{\cal P}$-hard in general. We show that it can be solved in polynomial time for those instances that come up in switchbox routing. Our algorithm uses dynamic programming techniques. These techniques are also applied to the much more complicated separation problem for alternating cycle inequalities. In this case we can compute in polynomial time, given some point $y$, a lower bound for the gap $\alpha-a^Ty$ over all alternating cycle inequalities $a^Tx\ge\alpha$. This gives rise to a very effective separation heuristic. A by-product of our algorithm is the solution of a combinatorial optimization problem that is interesting in its own right: Find a shortest path in a graph where the ``length'' of a path is its usual length minus the length of its longest edge.
Author: | Martin Grötschel, Alexander Martin, Robert Weismantel |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1992/12/02 |
Series (Serial Number): | ZIB-Report (SC-93-02) |
ZIB-Reportnumber: | SC-93-02 |
Published in: | Appeared in: SIAM J. Discrete Math. 9 (1996) pp. 233-257 |
DOI: | https://doi.org/10.1137/S0895480193258716 |