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

Декомпозиция Бендерса (или декомпозиция Бендерса ) — метод математического программирования , позволяющий решать очень большие задачи линейного программирования , имеющие специальную блочную структуру . Такая блочная структура часто встречается в таких приложениях, как стохастическое программирование , поскольку неопределенность обычно представляется сценариями. Методика названа в честь Жака Ф. Бендерса .

Стратегию декомпозиции Бендера можно резюмировать как « разделяй и властвуй» . То есть при разложении Бендерса переменные исходной задачи делятся на два подмножества, так что главная задача первого этапа решается по первому набору переменных, а значения для второго набора переменных определяются во втором. подзадача этапа для данного решения первого этапа. Если подзадача определяет, что фиксированные решения первого этапа на самом деле неосуществимы, то так называемые разрезы Бендера генерируются и добавляются к основной задаче, которая затем решается повторно до тех пор, пока разрезы не могут быть созданы. Поскольку декомпозиция Бендерса добавляет новые ограничения по мере продвижения к решению, этот подход называется « генерацией строк ». Напротив, разложение Данцига – Вольфа использует « столбцов генерацию ».

Методология

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

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

Разложение Бендерса применимо к задачам с преимущественно блочно-диагональной структурой.

Математическая формулировка

Предположим задачу следующей структуры:

${\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} \\&{\text{subject to}}&&A\mathbf {x} +B\mathbf {y} \geq \mathbf {b} \\&&&\mathbf {y} \in Y\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

Где $A,B$ представляют ограничения, общие для обеих стадий переменных и $Y$ представляет собой допустимый набор для $\mathbf {y}$. Обратите внимание, что для любого фиксированного $\mathbf {\bar {y}} \in Y$, остаточная проблема

${\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A\mathbf {x} \geq \mathbf {b} -B\mathbf {\bar {y}} \\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}$

Двойственной задаче остатка является

${\begin{aligned}&{\text{maximize}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}$

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

$\min _{\mathbf {y} \in Y}\left[\mathbf {d} ^{\mathrm {T} }\mathbf {y} +\max _{\mathbf {u} \geq \mathbf {0} }\left\{(\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {u} \mid A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \right\}\right].$

Разложение Бендерса основано на итеративной процедуре, которая выбирает последовательные значения $\mathbf {y}$ без учета внутренней проблемы, за исключением набора ограничений сокращения, которые создаются с помощью механизма возврата из задачи максимизации. Хотя минимаксная формулировка записана в терминах $(\mathbf {u} ,\mathbf {y} )$, для оптимального $\mathbf {\bar {y}}$ соответствующий $\mathbf {\bar {x}}$ можно найти, решив исходную задачу с помощью $\mathbf {\bar {y}}$ зафиксированный.

Основная формулировка проблемы

Решения для задачи первого этапа можно описать меньшей задачей минимизации

${\begin{aligned}&{\text{minimize}}&&\mathbf {z} \\&{\text{subject to}}&&\{{\text{cuts}}\}\\&&&\mathbf {y} \in Y\\\end{aligned}}$

Изначально множество разрезов пусто. Решение этой основной проблемы будет представлять собой «первую догадку» об оптимальном решении общей проблемы со значением $\mathbf {z}$ неограниченный снизу и $\mathbf {y}$ принимая любое допустимое значение.

Набор разрезов будет заполнен в последовательности итераций путем решения внутренней задачи максимизации минимаксной формулировки. Оба эти сокращения ведут основную задачу к оптимальному решению. $\mathbf {y}$, если таковой существует, и убедитесь, что $\mathbf {y}$ вполне осуществимо для полной задачи. Набор разрезов определяет взаимосвязь между $\mathbf {y}$, $\mathbf {z}$, и неявно $\mathbf {x}$.

Поскольку значение $z$ начинается без ограничений, и мы добавляем ограничения только на каждой итерации, что означает, что допустимое пространство может только сокращаться, значение основной проблемы на любой итерации обеспечивает нижнюю границу решения общей проблемы. Если для некоторых $\mathbf {\bar {y}}$ объективное значение главной проблемы равно значению оптимального значения внутренней проблемы, тогда согласно теории двойственности решение будет оптимальным.

Формулировка подзадачи

Подзадача рассматривает предложенное решение $\mathbf {\bar {y}}$ к основной задаче и решает внутреннюю задачу максимизации из минимаксной формулировки. Внутренняя задача формулируется с использованием двойственного представления

${\begin{aligned}&{\text{maximize}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}$

В то время как основная задача дает нижнюю границу значения проблемы, подзадача используется для получения верхней границы. Результат решения подзадачи для любого заданного $\mathbf {\bar {y}}$ может быть либо конечным оптимальным значением, для которого экстремальная точка $\mathbf {\bar {u}}$ можно найти неограниченное решение, для которого крайний луч $\mathbf {\bar {u}}$ в конусе рецессии можно обнаружить или сделать вывод о том, что подзадача невыполнима.

Процедура

На высоком уровне процедура итеративно рассматривает основную проблему и подзадачу. Каждая итерация предоставляет обновленную верхнюю и нижнюю границу оптимального целевого значения. Результат подзадачи либо предоставляет новое ограничение для добавления к основной задаче, либо подтверждает, что для этой проблемы не существует конечного оптимального решения. Процедура завершается, когда показано, что конечного оптимального решения не существует или когда разрыв между верхней и нижней границей достаточно мал. В таком случае значение $\mathbf {\bar {x}}$ определяется путем решения первичной задачи невязки $\mathbf {\bar {y}}$.

Формально процедура начинается с установки нижней границы равной $-\inf$, верхняя граница установлена ​​на $\inf$, а вырезы в мастер-задаче пустые. Начальное решение получается путем выбора любого $\mathbf {\bar {y}} \in Y$. Затем начинается итерационная процедура, которая продолжается до тех пор, пока разрыв между верхней и нижней границей не станет не более $\epsilon$ или показано, что конечного оптимального решения не существует.

Первый шаг каждой итерации начинается с обновления верхней границы путем решения подзадачи с учетом самого последнего значения $\mathbf {\bar {y}}$. Есть три возможных результата решения подзадачи.

В первом случае объективное значение подзадачи не ограничено сверху. Согласно теории двойственности , когда двойственная задача имеет неограниченную цель, соответствующая основная задача невозможна. Это означает, что выбор $\mathbf {\bar {y}}$ не удовлетворяет $A\mathbf {x} +B\mathbf {\bar {y}} \geq \mathbf {b}$ для любого $\mathbf {x} \geq \mathbf {0}$. Это решение можно удалить из основной задачи, взяв крайний луч $\mathbf {\bar {u}}$ который удостоверяет, что подзадача имеет неограниченную цель, и добавляет ограничение к мастеру, утверждающему, что $(\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} \leq \mathbf {0}$.

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

В третьем случае подзадача имеет конечное оптимальное решение. Согласно теории двойственности для линейных программ оптимальное значение подзадачи равно оптимальному значению исходной задачи, ограниченному выбором $\mathbf {\bar {y}}$. Это позволяет обновить верхнюю границу до значения оптимального решения подзадачи, если оно лучше текущей верхней границы. Учитывая оптимальную крайнюю точку $\mathbf {\bar {u}}$, это также дает новое ограничение, которое требует, чтобы основная задача учитывала целевое значение для этого конкретного решения, утверждая, что $z\geq (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} +\mathbf {d} ^{\mathrm {T} }\mathbf {y}$. Это резко увеличит ценность $z$ в решении $\mathbf {\bar {y}}$ в основной задаче, если выбор $\mathbf {\bar {y}}$ был неоптимальным.

Наконец, последняя часть каждой итерации — это создание нового решения основной проблемы путем решения основной проблемы с новым ограничением. Новое решение $(\mathbf {\bar {y}} ,z)$ используется для обновления нижней границы. Если разрыв между лучшей верхней и нижней границей меньше $\epsilon$ затем процедура завершается и значение $\mathbf {\bar {x}}$ определяется путем решения первичной задачи невязки $\mathbf {\bar {y}}$. В противном случае процедура переходит к следующей итерации.

См. также

• Решатель FortSP использует разложение Бендерса для решения задач стохастического программирования.

Ссылки

• Бендерс, Дж. Ф. (сентябрь 1962 г.), « Процедуры разделения для решения задач программирования со смешанными переменными », Numerische Mathematik 4 (3): 238–252.
• Ласдон, Леон С. (2002), Теория оптимизации для больших систем (переиздание издания Macmillan 1970 года), Минеола, Нью-Йорк: Dover Publications , стр. xiii+523, MR   1888251 .