Abstract
We consider the weight-constrained minimum spanning tree problem which has important applications in telecommunication networks design. We discuss and compare several formulations. In order to strengthen these formulations, new classes of valid inequalities are introduced. They adapt the well-known cover, extended cover and lifted cover inequalities. They incorporate information from the two subsets: the set of spanning trees and the knapsack set. We report computational experiments where the best performance of a standard optimization package was obtained when using a formulation based on the well-known Miller-Tucker-Zemlin variables combined with separation of cut-set inequalities.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, V., Aneja, Y.P., Nair, K.P.K.: Minimal spanning tree subject to a side constraint. Computers and Operations Research 9, 287–296 (1982)
Gouveia, L.: Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints. Computers and Operations Research 22(9), 959–970 (1995)
Hassin, R., Levin, A.: An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection. SIAM Journal on Computing 33(2), 261–268 (2004)
Hong, S.P., Chung, S.J., Park, B.H.: A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. Operations Research Letters 32, 233–239 (2004)
Kaparis, K., Letchford, A.: Separation algorithms for 0-1 knapsack polytopes. Mathematical Programming 124(1–2), 69–91 (2010)
Magnanti, T., Wolsey, L.: Optimal trees. In: Ball, M., Magnanti, T., Monma, C., Nemhauser, G. (eds.) Network Models. Handbooks in Operations Research and Management Science, vol. 7, pp. 503–615. Elsevier Science Publishers, North-Holland, Amsterdam (1995)
Miller, C., Tucker, A., Zemlin, R.: Integer programming formulations and travelling salesman problems. Journal of the Association for Computing Machinery 7, 326–329 (1960)
Pisinger, D.: Where are the hard knapsack problems? Technical Report 2003/08, DIKU, University of Copenhagen, Denmark (2003)
Ravi, R., Goemans, M.: The constrained minimum spanning tree problem. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 66–75. Springer, Heidelberg (1996)
Shogan, A.: Constructing a minimal-cost spanning tree subject to resource constraints and flow requirements. Networks 13, 169–190 (1983)
Yamada, T., Watanabe, K., Kataoka, S.: Algorithms to solve the knapsack constrained maximum spanning tree problem. International Journal of Computer Mathematics 82, 23–34 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agra, A., Cerveira, A., Requejo, C., Santos, E. (2011). On the Weight-Constrained Minimum Spanning Tree Problem. In: Pahl, J., Reiners, T., Voß, S. (eds) Network Optimization. INOC 2011. Lecture Notes in Computer Science, vol 6701. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21527-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-21527-8_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21526-1
Online ISBN: 978-3-642-21527-8
eBook Packages: Computer ScienceComputer Science (R0)