Страница публикации

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

Авторы: Васильев И.Л., Ушаков А.В.

Журнал: Вычислительные методы и программирование: новые вычислительные технологии

Том: 14

Номер: 1

Год: 2013

Отчётный год: 2013

Издательство:

Местоположение издательства:

URL: http://num-meth.srcc.msu.ru/

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

Индексируется WOS: 0

Индексируется Scopus: 0

Индексируется РИНЦ: 1

Публикация в печати: 0

Добавил в систему: