Разложение Бендерса

Разложение Бендерса — это полезный алгоритм для решения задач выпуклой оптимизации с большим числом переменных. Лучше всего оно работает, когда большую задачу можно разложить на две (или более) задачи меньшего размера, которые по отдельности решаются гораздо проще. В этом руководстве демонстрируется разложение Бендера на примере следующей частично целочисленной линейной программы:

где , , и  — это множество целых чисел.

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

Если целочисленных переменных относительно немного, а непрерывных гораздо больше, то может быть полезно разделить общую задачу на небольшую задачу только с целочисленными переменными и линейную программу только с непрерывными переменными. Скорее всего, такую линейную программу будет гораздо проще решить изолированно, чем в составе полной частично целочисленной линейной программы.

Например, если бы было известно допустимое решение для , решение для можно было бы получить так:

где  — двойственная переменная, связанная с ограничениями. Поскольку это линейная программа, ее легко решить.

Заменив компонент целевой функции в исходной задаче на , получим следующее.

Похоже, эту задачу решить гораздо проще, но сначала нужно еще кое-что сделать с .

Так как  — это константа, используемая в правой части ограничений,  — это выпуклая функция относительно , а двойственную переменную можно умножить на , чтобы получить субградиент относительно . Следовательно, если есть вариант решения , можно решить и получить допустимый двойственный вектор . Используя эти значения, можно построить аппроксимацию в виде ряда Тейлора первого порядка в окрестности точки :

Из выпуклости следует, что это неравенство верно для всех , и такие неравенства называются разрезами.

Разложение Бендерса — это итеративный метод, который заменяет новой переменной решения и аппроксимирует ее снизу с помощью разрезов:

Эта целочисленная программа называется подзадачей первой стадии.

Для генерирования разрезов мы решаем , чтобы получить вариант решения первой стадии , а затем используем это решение для решения . Затем, используя оптимальное целевое значение и двойственное решение из , мы добавляем новый разрез для формирования и повторяем процесс.

В качестве примера для этого руководства используются входные данные со страницы 139 книги Garfinkel, R. & Nemhauser, G. L. Integer programming (Wiley, 1972).

Начнем с формулирования подзадачи первой стадии.

Для следующего шага нам понадобится функция, которая принимает вариант решения первой стадии x и возвращает оптимальное решение подзадачи второй стадии:

Обратите внимание, что solve_subproblem возвращает кортеж NamedTuple целевого значения, оптимальное прямое решение для y и оптимальное двойственное решение для π.

Все почти готово к циклу оптимизации, но сначала вот полезная функция для ведения журнала:

Кроме того, необходимо установить ограничение на количество итераций до завершения:

И указать способ проверки приближения к нижней и верхней границам:

Теперь можно выполнить итерации разложения Бендерса:

Наконец, можно получить оптимальное решение:

В разделе Итеративный метод разложение Бендерса было реализовано посредством цикла. В каждой итерации повторно решалась подзадача первой стадии для получения варианта решения. Однако современные решатели MILP, такие как CPLEX, Gurobi и GLPK, предоставляют обратные вызовы отложенных ограничений, которые позволяют добавлять новые разрезы во время работы решателя. Это может быть эффективнее итеративного метода, так как позволяет избежать повторных действий, например нахождения решения для корневого узла программы MILP первой стадии в каждой итерации.

Создаем ту же подзадачу первой стадии, что и ранее:

Отличие в том, что мы пишем функцию обратного вызова, а не цикл:

Теперь при вызове optimize! выполняется обратный вызов:

Для этой модели алгоритм обратного вызова потребовал большего количества решений подзадачи:

Однако для более крупных задач можно ожидать, что алгоритм обратного вызова будет эффективнее итеративного.

Наконец, можно получить оптимальное решение:

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

Сначала, как обычно, создаем задачу первой стадии:

Затем вместо построения подзадачи в функции мы создаем ее один раз здесь:

Эта формулировка немного отличается. Мы включили копию переменных x, x_copy, и использовали x_copy в левой части ограничений.

Функция для решения подзадачи также немного отличается. Сначала нам нужно зафиксировать переменные x_copy в значении x из задачи первой стадии, а затем вычислить двойственное решение, используя reduced_cost для x_copy, а не двойственное решение для линейных ограничений:

Теперь можно выполнить итерации разложения Бендерса на месте, но на этот раз разрез вычисляется немного иначе. Так как мы использовали reduced_cost для переменных x_copy, значение π является допустимым субградиентом целевой функции subproblem относительно x. Поэтому двойственные решения не нужно умножать на -A_1, и для разреза используется ret.π' вместо -ret.π' * A_1:

Наконец, можно получить оптимальное решение:

Для более крупных задач преимущество повторного использования одной той же подзадачи и отсутствия необходимости умножать двойственные решения на A_1 в коэффициенте разреза обычно перевешивает затраты, связанные с необходимостью копировать переменные x в подзадаче.

Дополнительное преимущество заключается в том, что, поскольку в разрезе больше не требуется явное представление A_1, можно строить формулировки model и subproblem с использованием произвольного синтаксиса JuMP; они не обязательно должны быть в матричной форме.