Том 19, номер 2, 2012 г., Стр. 19-40

УДК 510.53
Давыдов И. А. 
Локальный поиск с запретами для дискретной задачи о (r|p)–центроиде

Аннотация:
Для дискретной задачи о (r|p)-центроиде разработан вероятностный метод локального поиска с запретами. Получены ограничения на список запретов, при которых алгоритм обладает следующим свойством: с ростом числа итераций вероятность отыскания глобального оптимума стремится к единице. Для оценки значений целевой функции используется метод лагранжевых релаксаций. Показано, что такая оценка не уступает оценке линейной релаксации. Исследуются различные алгоритмы субградиентной оптимизации для поиска оптимальных множителей Лагранжа. Проведены экспериментальные исследования на тестовых примерах из электронной библиотеки «Дискретные задачи размещения». Результаты экспериментов свидетельствуют о высокой частоте получения глобального оптимума разработанным методом.
Ил. 4, табл. 5, библиогр. 21.

Ключевые слова: конкурентные размещения, игры Штаккельберга, двухуровневое программирование.

Давыдов Иван Александрович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: iadavydov@math.nsc.ru

Статья поступила 31 марта 2011 г.
Исправленный вариант — 26 декабря 2011 г.

Литература

[1] Алексеева Е. В., Кочетова Н. А. Верхние и нижние границы для конкурентной задачи о $p$-медиане // Тр. XIV-й Байкальской междунар. школы-семинара «Методы оптимизации и их приложения». Т. 1. — Иркутск: РИО ИДСТУ СО РАН, 2008. — С. 563–569.

[2] Гончаров Е. Н., Кочетов Ю. А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискрет. анализ и исслед. операций. Сер. 2. — 2002. — Т. 9, № 2. — С. 13–30.

[3] Кочетов Ю. А., Пащенко М. Г., Плясунов А. В. О сложности локального поиска в задаче о $p$-медиане // Дискрет. анализ и исслед. операций. Сер. 2. — 2005. — Т. 12, № 2. — С. 44–71.

[4] Alekseeva E., Kochetova N., Kochetov Yu., Plyasunov A. A hybrid memetic algorithm for the competitive $p$-median problem // Proc. INCOM (Moscow, Russia, June 3–5, 2009). — Moscow: ICS RAS Publ., 2009. — P. 1516–1520.

[5] Alekseeva E., Kochetov Yu., Plyasunov A. Complexity of local search for the $p$-median problem // Eur. J. Oper. Res. — 2008. — Vol. 191. — P. 736–752.

[6] Alekseeva E. V., Kochetova N. A., Kochetov Yu. A., Plyasunov A. V. A heuristic and exact methods for the discrete ($r|p$)-centroid problem // Evolutionary computation in combinatorial optimization. Proc. 10th Eur. Conf. EvoCOP 2010 (Istanbul, Turkey, April 7–9, 2010). — Berlin: Springer-Verl., 2010. — P. 11–22. (Lect. Notes Comp. Sci.; Vol. 6022.)

[7] Barahona F., Chudak F. A. Near-optimal solutions to large-scale facility location problems // Discrete Optimization. — 2005. —Vol. 2. — P. 35–50.

[8] Benati S., Laporte G. Tabu search algorithms for the ($r|X_p$)-medianoid and ($r|p$)-centroid problems // Locat. Sci. — 1994. — Vol. 2, N 2. — P. 193–204.

[9] Bhadury J., Eiselt Y., Jaramillo J. An alternating heuristic for medianoid and centroid problems in the plane // Comput. Oper. Res. — 2003. — Vol. 30. — P. 553–565.

[10] Drezner T., Eiselt H. A. Consumers in competitive location models // Facility location. Applications and theory. — Berlin: Springer-Verl., 2004. — P. 151–178.

[11] Frangeoni A. About Lagrangian methods in integer optimization // Ann. Oper. Res. — 2005. — Vol. 139. — P. 163–193.

[12] Geoffrion A. M. Lagrangian relaxation for integer programming // Math. Program. Study, Ser. —1974. — Vol. 2. — P. 82–114.

[13] Glover F., Laguna M. Tabu search. — Boston: Kluwer Acad. Publ., 1997. — 408 p.

[14] Guinard M. Lagrangian relaxation // TOP. — 2003. — Vol. 11. — P. 215–228.

[15] Hakimi S. L. Locations with spatial interactions: competitive locations and games // Discrete Locat. Theory. — New York: Wiley, 1990. — P. 439–478.

[16] Held M., Wolfe P., Crowder H. P. Validation of subgradient optimization // Math. Program. — 1974. — Vol. 6, N 1. — P. 62–88.

[17] Kochetov Yu., Kononov A., Plyasunov A. Competitive facility location models // Comput. Math. Math. Physics. — 2009. — Vol. 49, N 6. — P. 994–1009.

[18] Lemaréchal C. Lagrangian relaxation // Computational combinatorial optimization. — Heidelberg: Springer-Verl., 2001. — P. 115–160.

[19] Noltemeier H., Spoerhase J., Wirth H.-C. Multiple voting location and single voting location on trees // Eur. J. Oper. Res. — 2007. — Vol. 181.—P. 654–667.

[20] Poljak B. T. Subgradient methods: a survey of Soviet research // Nonsmooth optimization. IIASA Proc. Ser. — 1977. — Vol. 3. — P. 5–30.

[21] Shor N. Z. Minimization methods for non-differentiable functions. — New York: Springer-Verl., 1985. — 162 p.