×

zbMATH — the first resource for mathematics

Lagrangean duals and exact solution to the capacitated \(p\)-center problem. (English) Zbl 1177.90241
Summary: We address the capacitated \(p\)-center problem \((CpCP)\). We study two auxiliary problems, discuss their relation to \(CpCP\), and analyze the lower bounds obtained with two different Lagrangean duals based on each of these auxiliary problems. We also compare two different strategies for solving exactly \(CpCP\), based on binary search and sequential search, respectively. Various data sets from the literature have been used for evaluating the performance of the proposed algorithms.

MSC:
90B80 Discrete location and assignment
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agarwal, P.; Procopiuc, C.M., Exact and approximation algorithms for clustering, Algorithmica, 33, 201-226, (2002) · Zbl 0994.68178
[2] Bar-Ilan, J.; Kortsarz, G.; Peleg, D., How to allocate network centers, Journal of algorithms, 15, 385-415, (1993) · Zbl 0784.68012
[3] Ceselli, A.; Righini, G., A branch-and-price algorithm for the capacitated p-Median problem, Networks, 45, 125-142, (2005) · Zbl 1101.68722
[4] Díaz, J.A.; Fernández, E., Hybrid scatter search and path relinking for the capacitated p-Median problem, European journal of operational research, 169, 570-585, (2006) · Zbl 1079.90076
[5] Elloumi, S.; Labbé, M.; Pochet, Y., A new formulation and resolution method for the p-center problem, INFORMS journal on computing, 16, 84-94, (2004) · Zbl 1239.90103
[6] Fleszar, K.; Hindi, K.S., An effective VNS for the capacitated p-Median problem, European journal of operational research, 191, 612-622, (2008) · Zbl 1160.90496
[7] Galvaõ, R.D.; ReVelle, C., A Lagrangean heuristic for the maximum covering location problem, European journal of operational research, 88, 114-123, (1996) · Zbl 0913.90200
[8] Jaeger, M.; Goldberg, J., A polynomial algorithm for the equal capacity p-center problem on trees, Transportation science, 28, 167-175, (1994) · Zbl 0807.90076
[9] Khuller, S.; Sussmann, Y.J., The capacitated k-center problem, SIAM journal on discrete mathematics, 13, 403-418, (2000) · Zbl 0947.05073
[10] Lorena, L.A.N.; Senne, E.L.F., A column generation approach to capacitated p-Median problem, Computers and operations research, 31, 863-876, (2004) · Zbl 1048.90132
[11] Martello, S.; Toth, P., Knapsack problems, algorithms and computer implementations, (1990), Wiley Chichester · Zbl 0708.68002
[12] Osman, I.H.; Christofides, N., Capacitated clustering problems by hybrid simulated annealing and tabu search, International transactions in operational research, 1, 317-336, (1994) · Zbl 0857.90107
[13] Özsoy, F.A.; Pinar, M.Ç., An exact algorithm for the capacitated vertex p-center problem, Computers and operations research, 33, 1420-1436, (2006) · Zbl 1126.90039
[14] Scapparra, M.P.; Pallotino, S.; Scutellà, M.G., Large-scale local search heuristics for the capacitated vertex p-center problem, Networks, 43, 241-255, (2004) · Zbl 1053.90085
[15] Scheuerer, S.; Wendolsky, R., A scatter search heuristic for the capacitated clustering problem, European journal of operational research, 169, 533-547, (2006) · Zbl 1079.90180
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.