Comparison of formulations and a heuristic for packing Steiner trees in a graph (Q1339122)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Comparison of formulations and a heuristic for packing Steiner trees in a graph |
scientific article |
Statements
Comparison of formulations and a heuristic for packing Steiner trees in a graph (English)
0 references
1 December 1994
0 references
This paper gives various integer linear programming formulations for the problem of packing Steiner trees in a graph that arises from circuit layout design, and ranks them according to the lower bounds provided by the corresponding LP-relaxations, and then a solution procedure is given to obtain both lower and upper bounds using an LP-relaxation. Finally, computational results for testing the effectiveness of the procedure are presented.
0 references
integer linear programming
0 references
packing Steiner trees in a graph
0 references
circuit layout design
0 references
LP-relaxation
0 references
