Оценка производительности крупноблочного алгоритма метода ветвей и границ в вычислительной среде Everest

В работе исследовался т.н. крупноблочный подход к реализации параллельной работы метода ветвей и границ (МВГ). Исходная задача частично-целочисленного программирования разбивается на несколько подзадач посредством фиксации значений у части целочисленных переменных. Подзадачи решаются параллельно пулом МВГ-решателей. Если в ходе решения подзадач появляется допустимое решение, с наилучшим на данный момент значением целевой функции, то это число рассылается другим решателям. Такой обмен рекордными значениями критерия позволяет взаимно ускорить решение подзадач за счет сокращения перебора вершин дерева ветвлений алгоритма МВГ. Запуск подзадач и обмен данными обеспечивается средствами платформы Everest. В результате тестирования разработанной распределенный системы на случайным образом сгенерированных задачах линейного программирования с частично-булевыми переменными было обнаружено заметное ускорение.