Параллельная реализация субградиентного алгоритма для максимизации двойственной функции Лагранжа в задаче о p-медиане

Авторы

  • И.Л. Васильев
  • А.В. Ушаков

Ключевые слова:

задача о p-медиане
параллельное программирование
релаксация Лагранжа
субградиентный метод
MPI

Аннотация

Рассматривается алгоритм поиска нижних оценок для оптимального значения в задаче о p-медиане, основанный на построении релаксации Лагранжа, а также максимизации двойственной функции с помощью субградиентного метода. Предлагается эффективная схема распараллеливания такого алгоритма, включающая в себя процедуру каскадной сборки данных между процессами. Разработанный алгоритм тестируется на широком наборе модельных примеров большой размерности, в том числе на задачах, размерность которых превосходит известную до настоящего времени из литературы. Полученные результаты подтверждают эффективность предложенной модели распараллеливания. Работа выполнена при частичной финансовой поддержке РФФИ (проекты 12-07-33045-мол_а_вед и 12-01-31198-мол_а), а также СО РАН (интеграционный проект 21).

Новые вычислительные технологии

Загрузки

Опубликован

2013-01-14

Выпуск

Том 14 (2013): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

И.Л. Васильев

Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН)
ул. Лермонтова, 134, 664033, Иркутск
• доцент, ведущий научный сотрудник

А.В. Ушаков

Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН)
ул. Лермонтова, 134, 664033, Иркутск
• программист

Библиографические ссылки

  1. Васильев И.Л., Ушаков А.В. Релаксации Лагранжа для нелинейной задачи о p-медиане // Известия ИГУ. Серия «Математика». 2011. 4, № 2. 45-60.
  2. Avella P., Boccia M., Salerno S., Vasilyev I. An aggregation heuristic for large scale p-median problem // Computers &; Operations Research. 2012. 39, N 7. 1625-1632.
  3. Crainic T.G., Gendreau M., Hansen P., Mladenovi’c N. Cooperative parallel variable neighborhood search for the p-median // Journal of Heuristics. 2004. 10, N 3. 293-314.
  4. Garciá-L’opez F. Parallelization of the scatter search for the p-median problem // Parallel Computing. 2003. 29, N 3. 575-589.
  5. Garc’ia S., Labbé M., Mar’in A. Solving large p-median problems with a radius formulation // INFORMS Journal on Computing. 2011. 23, N 4. 546-556.
  6. Hakimi S.L. Optimum distribution of switching centers in a communication network and some related graph theoretic problems // Operations Research. 1964. 13, N 3. 462-475.
  7. Hanafi S., Salerno S., Ushakov A., Vasilyev I. A parallel subgradient algorithm for Lagrangean dual function of the p-median problem // Studia Informatica Universalis. 2011. 9, N 3. 105-124.
  8. Hansen P., Brimberg J., Urosevi’c D., Mladenovi’c N. Solving large p-median clustering problems by primal-dual variable neighborhood search // Data Mining and Knowledge Discovery. 2009. 19, N 3. 351-375.
  9. Kariv O., Hakimi S.L. An algorithmic approach to network location problems; part 2. The p-medians // SIAM Journal on Applied Mathematics. 1979. 37, N 3. 539-560.
  10. Ma L., Lim G. GPU-based parallel computational algorithms for solving p-median problem // Proc. of the IIE Annual Conference. Reno (Nevada, USA), 2011. ID: 1110.
  11. Mladenovi’c N., Brimberg J., Hansen P., Moreno-Pérez J.A. The p-median problem: A survey of metaheuristic approaches // EJOR. 2007. 179, N 3. 927-939.
  12. Moreno-Vega J.M. The parallel variable neighborhood search for the p-median problem // Journal of Heuristics. 2002. 8, N 3. 375-388.
  13. Reese J. Solution methods for the p-median problem: An annotated bibliography // Networks. 2006. 28, N 3. 125-142.
  14. Zhang T., Ramakrishnan R., Livny M. BIRCH: an efficient data clustering method for very large databases // Journal of the American Statistical Association. 1996. 98, N 463. 103-114.
  15. Вычислительный кластер Blackford [Электронный ресурс] // Иркутский суперкомпьютерный центр СО РАНlinebreak (http://hpc.icc.ru/hardware/blackford.php).
  16. Gropp W., Thakur R., Lusk E. Using MPI-2: advanced features of the message passing interface. Cambridge: MIT Press, 1999.
  17. Васильев И.Л., Климентова К.Б., Орлов А.В. Параллельный глобальный поиск равновесных ситуаций в биматричных играх // Вычислительные методы и программирование. 2007. 8, № 1. 233-243.
  18. Lim G.J., Ma L. GPU-based parallel vertex substitution algorithm for the p-median problem // Computers &; Industrial Engineering. 2013. 64, № 1. 381-388.