Geodesic
Lagrangian relaxations for the nonlinear $p$-median problem
The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 2, pp. 45-59 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: the $p$-median problem, Lagrangian relaxation, lower bounds; subgradient algorithm. 
@article{IIGUM_2011_4_2_a3,
     author = {I. L. Vasiliev and A. V. Ushakov},
     title = {Lagrangian relaxations for the nonlinear $p$-median problem},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {45--59},
     year = {2011},
     volume = {4},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2011_4_2_a3/}
}
TY  - JOUR
AU  - I. L. Vasiliev
AU  - A. V. Ushakov
TI  - Lagrangian relaxations for the nonlinear $p$-median problem
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2011
SP  - 45
EP  - 59
VL  - 4
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2011_4_2_a3/
LA  - ru
ID  - IIGUM_2011_4_2_a3
ER  - 
%0 Journal Article
%A I. L. Vasiliev
%A A. V. Ushakov
%T Lagrangian relaxations for the nonlinear $p$-median problem
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2011
%P 45-59
%V 4
%N 2
%U http://geodesic.mathdoc.fr/item/IIGUM_2011_4_2_a3/
%G ru
%F IIGUM_2011_4_2_a3
I. L. Vasiliev; A. V. Ushakov. Lagrangian relaxations for the nonlinear $p$-median problem. The Bulletin of Irkutsk State University. Series Mathematics, Tome 4 (2011) no. 2, pp. 45-59. http://geodesic.mathdoc.fr/item/IIGUM_2011_4_2_a3/

[1] P. Avella, A. Sassano, I. Vasil'ev, “Computational study of large-scale $p$-median problems”, Mathematical Programming, 109:1 (2007), 89–114 | DOI | MR | Zbl

[2] J. E. Beasley, “Lagrangean heuristics for location problems”, EJOR, 65:3 (1993), 383–399 | DOI | MR | Zbl

[3] P. Hansen, J. Brunberg, D. Urosevic, N. Mladenovic, Data clustering using large $p$-median models and primal-dual variable neighborhood search, Technical Report, Les Cahiers du GERAD, 2007

[4] P. Hansen, B. Jaumard, “Cluster analysis and mathematical programming”, Mathematical Programming, 79:1–3 (1997), 191–215 | MR | Zbl

[5] P. Hansen, N. Mladenovic, D. Perez-Brito, “Variable neighbourhood decomposition search”, Journal of Heuristics, 7:4 (2001), 335–350 | DOI | Zbl

[6] O. Kariv, L. Hakimi, “An algorithmic approach to network location problems. II: the $p$-medians”, Operations Research, 37:3 (1979), 539–560 | MR | Zbl

[7] P. Mirchandani, R. Jagannathan, “Discrete facility location with nonlinear diseconomies in fixed costs”, Annals of Operations Research, 18:1 (1989), 213–224 | DOI | MR | Zbl

[8] N. Mladenovic, J. Brimberg, P. Hansen, J. Moreno-Perez, “The $p$-median problem: A survey of metaheuristic approaches”, EJOR, 179:3 (2007), 927–939 | DOI | MR | Zbl

[9] M. G. C. Resende, R. F. Werneck, A grasp with path-relinking for the $p$-median problem, Technical Report TD-5E53XL, AT Labs Research, 2002