TY - GEN

T1 - On the hop constrained steiner tree problem with multiple root nodes

AU - Gouveia, Luis

AU - Leitner, Markus

AU - Ljubić, Ivana

PY - 2012/8/27

Y1 - 2012/8/27

N2 - We consider a new network design problem that generalizes the Hop and Diameter Constrained Minimum Spanning and Steiner Tree Problem as follows: given an edge-weighted undirected graph whose nodes are partitioned into a set of root nodes, a set of terminals and a set of potential Steiner nodes, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes. This paper presents theoretical and computational comparisons of flow-based vs. path-based mixed integer programming models for this problem. Disaggregation by roots is used to improve the quality of lower bounds of both models. To solve the problem to optimality, we implement branch-and-price algorithms for all proposed formulations. Our computational results show that the branch-and-price approaches based on path formulations outperform the flow formulations if the hop limit is not too loose.

AB - We consider a new network design problem that generalizes the Hop and Diameter Constrained Minimum Spanning and Steiner Tree Problem as follows: given an edge-weighted undirected graph whose nodes are partitioned into a set of root nodes, a set of terminals and a set of potential Steiner nodes, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes. This paper presents theoretical and computational comparisons of flow-based vs. path-based mixed integer programming models for this problem. Disaggregation by roots is used to improve the quality of lower bounds of both models. To solve the problem to optimality, we implement branch-and-price algorithms for all proposed formulations. Our computational results show that the branch-and-price approaches based on path formulations outperform the flow formulations if the hop limit is not too loose.

UR - http://www.scopus.com/inward/record.url?scp=84865240171&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865240171&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-32147-4_19

DO - 10.1007/978-3-642-32147-4_19

M3 - Conference contribution

AN - SCOPUS:84865240171

SN - 9783642321467

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 201

EP - 212

BT - Combinatorial Optimization - Second International Symposium, ISCO 2012, Revised Selected Papers

T2 - 2nd International Symposium on Combinatorial Optimization, ISCO 2012

Y2 - 19 April 2012 through 21 April 2012

ER -