Abstract
This paper considers a discrete location problem where the demand points are grouped. We propose a formulation, an enforcement for it, and an associated Lagrangian relaxation, and then we build feasible solutions to the problem from the optimal solutions to the relaxed subproblems. Valid inequalities for the formulation are also identified and added to the set of relaxed constraints. This method produces good feasible solutions and enables us to address large instances of the problem. Computational experiments have been performed with benchmark instances from the literature on related problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Avella P, Sassano A (2001) On the p-median polytope. Math Program 89:395–411
Barceló J, Hallefjord Ä, Fernández E, Jörnsten K (1990) Lagrangean relaxation and constraint generation procedures for capacitated plant location problems. Oper Res Spektrum 12:79–88
Cánovas L, Landete M, Marín A (2002) On the facets of the simple plant location packing polytope. Discrete Appl Math 124:27–53
Daskin M (1995) Network and discrete location: models, algorithms, and applications. Wiley, New York
De Vries S, Vohra RV (2003) Combinatorial auctions: a survey. INFORMS J Comput 15(3):284–309
Drezner Z, Hamacher H (2002) Facility location: applications and theory. Springer, Berlin
Cánovas L, García S, Labbé M, Marín A (2007) A strengthened formulation for the simple plant location problem with order. Oper Res Lett 35(2):141–150
Escudero L, Landete M, Marín A (2009) A branch-and-cut algorithm for the combinatorial auction problem. Decis Support Syst 46:649–659
Guignard M (2003) Lagrangean relaxation. Top 11:151–228
Marín A (2007) Lower bounds for the two-stage uncapacitated facility location problem. Eur J Oper Res 179:1126–1142
Melo M, Nickel S, Saldanha da Gama F (2006) Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning. Comput Oper Res 33:181–208
Mirchandani P, Francis R (1990) Discrete location theory. Wiley, New York
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been partially supported by Spanish Ministry of Education and Science grant number MTM2006-14961-C05-04, RDEF funds, and Fundación Séneca, grant number 02911/PI/05.
Rights and permissions
About this article
Cite this article
Marín, A. Discrete location for bundled demand points. TOP 18, 242–256 (2010). https://doi.org/10.1007/s11750-009-0097-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-009-0097-0