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

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

Тип публикации: Статья в журнале

Тип материала: Текст

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

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

Язык публикации: russian

Том: 14

Номера страниц: 9–16

Количество страниц: 8

Номер: 1

Год публикации: 2013

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

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

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

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

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

Индексируется УБС: Нет

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

Индексируется ВАК: Нет

Индексируется CORE: Нет