Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques

Andreas M. Chwatal and Günther R. Raidl

Advances in Operations Research, 2011, vol. 2011, 1-38

Abstract:

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.

Date: 2011
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://downloads.hindawi.com/journals/AOR/2011/143732.pdf (application/pdf)
http://downloads.hindawi.com/journals/AOR/2011/143732.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlaor:143732

DOI: 10.1155/2011/143732

Access Statistics for this article

More articles in Advances in Operations Research from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().