Advances in Operations Research
Volume 2011 (2011), Article ID 143732, 38 pages
Research Article

Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques

Institute of Computer Graphics and Algorithms, Vienna University of Technology, 1040 Vienna, Austria

Received 20 November 2010; Accepted 5 March 2011

Academic Editor: I. L. Averbakh

Copyright © 2011 Andreas M. Chwatal and Günther R. Raidl. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


We present exact mixed integer programming approaches including branch-and-cut and branch-and-cut-and-price for the minimum label spanning tree problem as well as a variant of it having multiple labels assigned to each edge. We compare formulations based on network flows and directed connectivity cuts. Further, we show how to use odd-hole inequalities and additional inequalities to strengthen the formulation. Label variables can be added dynamically to the model in the pricing step. Primal heuristics are incorporated into the framework to speed up the overall solution process. After a polyhedral comparison of the involved formulations, comprehensive computational experiments are presented in order to compare and evaluate the underlying formulations and the particular algorithmic building blocks of the overall branch-and-cut- (and-price) framework.