List of issues > Series «Mathematics». 2011. Vol. 2
Lagrangian relaxations for the nonlinear p-median problem
In this paper we study a modification of well-known p-median problem, in which the number of facilities is a non-fixed value. We consider the problem statement and propose a heuristic method to get lower bounds of the optimal values.
1. Avella P. Computational study of large-scale p-median problems / P. Avella, A. Sassano, I. Vasil’ev // Mathematical Programming. – 2007. – Vol. 109, N 1. – P. 89–114.
2. Beasley J. E. Lagrangean heuristics for location problems / J. E. Beasley // EJOR. – 1993. – Vol. 65, N 3. – P. 383–399.
3. Data clustering using large p-median models and primal-dual variable neighborhood search / P. Hansen, J. Brunberg, D. Urosevic, and N. Mladenovic // Technical Report. – Les Cahiers du GERAD, 2007. – ISSN: 07112440,
4. Hansen P. Cluster analysis and mathematical programming / P. Hansen, B. Jaumard. // Mathematical Programming. – 1997. – Vol. 79, N 1–3. – P. 191–215.
5. Hansen P. Variable neighbourhood decomposition search / P. Hansen, N. Mladenovic, D. Perez-Brito // Journal of Heuristics. – 2001. – Vol. 7, N 4. – P. 335–350.
6. Kariv O. An algorithmic approach to network location problems. II: the p-medians / O. Kariv, L. Hakimi. // Operations Research. – 1979. – Vol. 37, N 3. – P. 539–560.
7. Mirchandani P. Discrete facility location with nonlinear diseconomies in fixed costs / P. Mirchandani, R. Jagannathan. // Annals of Operations Research. – 1989. – Vol. 18, N 1. – P. 213–224.
8. The p-median problem: A survey of metaheuristic approaches / N. Mladenovic, J. Brimberg, P. Hansen, J. Moreno-Perez // EJOR. – 2007. – Vol. 179, N 3. – P. 927–939.
9. Resende M. G. C. A grasp with path-relinking for the p-median problem M.G.C. Resende, R.F. Werneck // Technical Report TD-5E53XL, AT&T;Labs;Research, 2002.