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

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

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

Название статьи, аннотация и ключевые слова на английском языке

Васильев И.Л., доцент, вед. науч. сотр., e-mail: vil@icc.ru;   Ушаков А.В., программист, e-mail: aushakov@icc.ru – Институт динамики систем и теории управления СО РАН, ул. Лермонтова, 134, 664033, Иркутск