Article ID: | iaor1995708 |
Country: | Switzerland |
Volume: | 50 |
Issue: | 1 |
Start Page Number: | 143 |
End Page Number: | 171 |
Publication Date: | Sep 1994 |
Journal: | Annals of Operations Research |
Authors: | Chopra Sunil |
Keywords: | Steiner problem |
In this paper, the problem of packing Steiner trees in a graph is considered. This problem arises during the global routing phase of circuit layout design. Various integer programming formulations are considered and ranked according to lower bounds they provide as LP-relaxations. A solution procedure to obtain both lower and upper bounds using one of the LP-relaxations is discussed. Computational results to test the effectiveness of the present procedures are provided.