![](/images/graphics-bg.png)
Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques
Joint Authors
Raidl, Günther R.
Chwatal, Andreas M.
Source
Advances in Operations Research
Issue
Vol. 2011, Issue 2011 (31 Dec. 2011), pp.1-38, 38 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2011-06-22
Country of Publication
Egypt
No. of Pages
38
Main Subjects
Information Technology and Computer Science
Abstract EN
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.
American Psychological Association (APA)
Chwatal, Andreas M.& Raidl, Günther R.. 2011. Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques. Advances in Operations Research،Vol. 2011, no. 2011, pp.1-38.
https://search.emarefa.net/detail/BIM-449233
Modern Language Association (MLA)
Chwatal, Andreas M.& Raidl, Günther R.. Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques. Advances in Operations Research No. 2011 (2011), pp.1-38.
https://search.emarefa.net/detail/BIM-449233
American Medical Association (AMA)
Chwatal, Andreas M.& Raidl, Günther R.. Solving the Minimum Label Spanning Tree Problem by Mathematical Programming Techniques. Advances in Operations Research. 2011. Vol. 2011, no. 2011, pp.1-38.
https://search.emarefa.net/detail/BIM-449233
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-449233