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

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