Эффективное применение пакетов дискретной оптимизации в облачной инфраструктуре на основе эвристической декомпозиции исходной задачи в системе оптимизационного моделирования AMPL

Пусть процесс поиска решения в некоторой задаче дискретной оптимизации пакетом, реализующим алгоритм ветвей и границ, занимает определенное время. Можно ли ускорить решение той же задачи если нам доступна вычислительная среда, где можно запустить несколько одновременно работающих «экземпляров» того же пакета оптимизации? В докладе рассматривается способ получить заметное ускорение для пакетов с открытым кодом в виртуальной многопроцессорной вычислительной среде. В основе подхода:

• предварительная декомпозиция исходной задачи на несколько подзадач путем фиксации целочисленных (булевых) значений части дискретных переменных, выбираемых согласно некоторому эвристическому правилу, реализованному в форме программы на высокоуровневом языке оптимизационного моделирования AMPL;
• одновременное решение полученных подзадач экземплярами того же пакета, с добавленной возможностью обмена найденными рекордными значениями целевой функции.

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