Abstract
This paper is concerned with the connected facility location problem, which has been intensively studied in the literature. The underlying polytopes, however, have not been investigated. This work is devoted to the polytope associated with the asymmetric version of the problem. We first lift known facets of the related Steiner arborescence and of the facility location polytope. Then we describe other new families of facet-inducing inequalities. Finally, computational results are reported.
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
Similar content being viewed by others
References
Gollowitzer, S., Ljubić, I.: MIP models for connected facility location: a theoretical and computational study. Comput. Oper. Res. 38(2), 435–449 (2011)
Leitner, M., Raidl, G.R.: Branch-and-cut-and-price for capacitated connected facility location. J. Math. Model. Algorithms 10(3), 245–267 (2011)
Leitner, M., Ljubić, I., Salazar-González, J.J., Sinnl, M.: The connected facility location polytope: valid inequalities, facets and a computational study. Submitted (2014)
Fischetti, M.: Facets of two Steiner arborescence polyhedra. Math. Program. 51, 401–419 (1991)
Cornuejols, G., Thizy, J.M.: Some facets of the simple plant location polytope. Math. Program. 23(1), 50–74 (1982)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1999)
Guignard, M.: Fractional vertices, cuts and facets of the simple plant location problem. In: Padberg, M. (ed.) Combinatorial Optimization. Mathematical Programming Studies, vol. 12, pp. 150–162. Springer, Heidelberg (1980)
Bardossy, M.G., Raghavan, S.: Dual-based local search for the connected facility location and related problems. INFORMS J. Comput. 22(4), 584–602 (2010)
Cirasella, J., Johnson, D.S., McGeoch, L.A., Zhang, W.: The asymmetric traveling salesman problem: algorithms, instance generators, and tests. In: Buchsbaum, A.L., Snoeyink, J. (eds.) ALENEX 2001. LNCS, vol. 2153, pp. 32–59. Springer, Heidelberg (2001)
Acknowledgements
M. Leitner is supported by the Austrian Science Fund (FWF) under grant I892-N23.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Leitner, M., Ljubić, I., Salazar-González, JJ., Sinnl, M. (2014). On the Asymmetric Connected Facility Location Polytope. In: Fouilhoux, P., Gouveia, L., Mahjoub, A., Paschos, V. (eds) Combinatorial Optimization. ISCO 2014. Lecture Notes in Computer Science(), vol 8596. Springer, Cham. https://doi.org/10.1007/978-3-319-09174-7_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-09174-7_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09173-0
Online ISBN: 978-3-319-09174-7
eBook Packages: Computer ScienceComputer Science (R0)