Параллельный метод деформируемых многогранников для решения задач комбинаторной оптимизации

Описывается алгоритм комбинаторной оптимизации (КО), основанный на идеях метода Нелдера–Мида, названный гибридным методом деформируемых многогранников (ГМДМ). Этот алгоритм обладает глобальным характером поиска в пространстве решений решаемой задачи КО, что позволяет находить варианты решений задач из разных классов с повышенной точностью. В работе предлагается параллельный алгоритм ГМДМ и обсуждаются вопросы его реализации на многопроцессорном суперкомпьютере СКИТ-1. Исследование эффективности предложенного алгоритма осуществлено на основе анализа результатов проведенного вычислительного эксперимента по решению известной оптимизационной модели – квадратичной задачи о назначении (КЗН).