В статье рассматривается модификация хорошо известной задачи о p-медиане, в которой количество медиан является переменной величиной. Рассматривается постановка данной задачи, а также реализуется эвристический метод нахождения нижних оценок ее оптимального значения.

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.