On solving large instances of the capacitated facility location problem. (English) Zbl 1163.90614

Summary: We present two sets of results pertaining to the solution of capacitated facility location problems that are large, especially with regard to the number of customers. One set of results relates to customer aggregation, while another set of results concerns the judicious selection of variable-upper-bounding (VUB) constraints to include in the initial integer-programming formulation.In many real-world instances of facility location problems, cities and towns define ‘customers’ and their ‘demands’. Such problems typically feature large metropolises that have numerous satellite townships whose total population is exceeded (often, greatly) by that of the associated metropolis. We argue that both sets of our results would be relevant in solving such problems. We discuss our computational experiences with reference to a real-world variant of the classical capacitated facility location problem that spurred the results reported here.


90B80 Discrete location and assignment
90C10 Integer programming


Full Text: DOI


[1] Aardal, K., Capacitated facility location: Separation algorithms and computational experience, Mathematical Programming, 81, 149-175 (1998) · Zbl 0919.90096
[2] Aardal, K.; Pochet, Y.; Wolsey, L. A., Capacitated facility location: Valid inequalities and facets, Mathematics of Operations Research, 20, 562-582 (1995) · Zbl 0846.90088
[3] Aardal, K.; Pochet, Y.; Wolsey, L. A., Erratum: Capacitated facility location: Valid inequalities and facets, Mathematics of Operations Research, 21, 253-256 (1996) · Zbl 0856.90063
[4] Chen, B.; Guignard, M., Polyhedral analysis and decompositions for capacitated plant location-type problems, Discrete Applied Mathematics, 82, 79-91 (1998) · Zbl 0897.90153
[6] Francis, R. L.; Lowe, T. J., On worst-case aggregation analysis for network location problems, Annals of Operations Research, 40, 229-246 (1992) · Zbl 0787.90046
[7] Francis, R. L.; Lowe, T. J.; Rayco, M. B., Row-column aggregation for rectilinear distance \(p\)-median problems, Transportation Science, 30, 160-174 (1996) · Zbl 0865.90087
[9] Hakimi, S. L., Optimal locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12, 450-459 (1964) · Zbl 0123.00305
[10] Hakimi, S. L., Optimum distribution of switching centers in a communications network and some related graph-theoretic problems, Operations Research, 13, 462-475 (1965) · Zbl 0135.20501
[11] Leung, J. M.Y.; Magnanti, T. L., Valid inequalities and facets of the capacitated plant location problem, Mathematical Programming, 44, 271-291 (1989) · Zbl 0686.90021
[12] Rayco, M. B.; Francis, R. L.; Lowe, T. J., Error-bound driven demand point aggregation for the rectilinear distance \(p\)-center model, Location Science, 4, 213-235 (1997) · Zbl 0929.90051
[14] Sankaran, J. K.; Raghavan, N. R.S., Locating and sizing plants for bottling propane in south India, Interfaces, 27, 1-15 (1997)
[15] Savelsbergh, M. W.P.; Sigismondi, G. C.; Nemhauser, G. L., Functional description of MINTO, a Mixed INTeger Optimizer, Operations Research Letters, 15, 47-58 (1994) · Zbl 0806.90095
[16] Schrage, L. S., Optimization Modelling with LINDO (1997), Duxbury Press: Duxbury Press Pacific Grove, CA
[17] Simchi-Levi, D.; Kaminsky, P.; Simchi-Levi, D., Designing and Managing the Supply Chain: Concepts, Strategies, and Case Studies (2003), Irwin/McGraw-Hill: Irwin/McGraw-Hill Burr Ridge, IL
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.