Vertex-disjoint packing of two Steiner trees: polyhedra and branch-and-cut

Citation
E. Uchoa et Mp. De Aragao, Vertex-disjoint packing of two Steiner trees: polyhedra and branch-and-cut, MATH PROGR, 90(3), 2001, pp. 537-557
Citations number
14
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
90
Issue
3
Year of publication
2001
Pages
537 - 557
Database
ISI
SICI code
0025-5610(200105)90:3<537:VPOTST>2.0.ZU;2-S
Abstract
Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is give n by the vertex-disjoint packing of two Steiner trees (2VPST), which is kno wn to be NP-complete. This work presents an investigation on the 2VPST poly hedra. The main idea is to start from facet-defining inequalities for a ver tex-weighted Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others are lifted to derive new important families of inequalities, including proven facets. Se paration algorithms are provided. Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the perf ormance of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals in a few minut es.