Разложение Бендеров - Benders decomposition

Разложение Бендеров (или же Разложение Бендерса) - техника в математическое программирование что позволяет решать очень большие линейное программирование проблемы, у которых есть особые блочная структура. Эта блочная структура часто встречается в таких приложениях, как стохастическое программирование поскольку неопределенность обычно представлена ​​сценариями. Техника названа в честь Жак Ф. Бендерс.

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

Методология

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

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

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

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

Свести к минимуму ${displaystyle cx+dy}$

При условии:

${displaystyle Ax+Byleq b_{1}}$

${displaystyle Cxleq b_{2}}$

${displaystyle Gyleq b_{3}}$

${displaystyle x,ygeq 0}$

Где ${displaystyle A,B}$ представляют ограничения, общие для обеих стадий переменных, ${displaystyle C}$ представляет переменные, уникальные для ${displaystyle x}$, и ${displaystyle G}$ представляет переменные, уникальные для ${displaystyle y}$.

Формулировка основной проблемы

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

Свести к минимуму ${displaystyle cx}$

При условии:

${displaystyle Cxleq b_{2}}$

${displaystyle xgeq 0}$

Решение этой основной задачи представляет собой «первое предположение» об оптимальном решении общей проблемы. Обратите внимание: поскольку решение этой проблемы может нарушить одно из ограничений ${displaystyle Ax+Byleq b_{1}}$ или же ${displaystyle Gyleq b_{3}}$, у нас нет гарантии, что эта основная задача выполнима в пространстве общей проблемы. Однако, в соответствии с методологией отложенного создания ограничений, возможное пространство проблемы может только сузиться. Это означает, что если оптимальное решение нашей основной задачи по-прежнему возможно в пространстве всей проблемы, оно будет оптимальным. [Нет, вы не можете этого гарантировать. Обратите внимание, что значение ${displaystyle x}$ может ограничить стоимость ${displaystyle y}$ из-за ограничений ${displaystyle Ax+Byleq b_{1}}$, и, следовательно, возможно, вы получите хороший ${displaystyle x}$ но надо выбирать бедных ${displaystyle y}$ так что общая целевая функция ${displaystyle cx+dy}$ НЕ свернута.].

Постановка подзадач

Мы возьмем предложенное решение основной проблемы и включим его в каждую из наших подзадач, чтобы оценить осуществимость предлагаемого решения. Позволять ${displaystyle x^{*}}$ быть текущим решением ${displaystyle x}$ переменные в соответствии с текущей итерацией основной задачи. С ${displaystyle Ax^{*}}$ это просто числовая матрица, мы можем использовать ее, чтобы перефразировать подзадачу, чтобы только ${displaystyle y}$ учитываются переменные.

Свести к минимуму: ${displaystyle dy}$

При условии:

${displaystyle Byleq b_{1}-Ax^{*}}$

${displaystyle Gyleq b_{3}}$

${displaystyle ygeq 0}$

В соответствии с теория двойственности, если двойственная к этой задаче оптимизации имеет конечное оптимальное решение, то же самое и прямое решение. Более того, если двойственная задача неограничена выше, то прямое не имеет решения. Таким образом, мы можем использовать двойственное, чтобы оценить выполнимость основной задачи, тем самым оценивая оптимальность основной задачи. Двойственная к этой проблеме, как она написана:

Максимизировать: ${displaystyle p_{1}(b_{1}-Ax^{*})+p_{2}b_{3}}$

При условии:

${displaystyle p_{1}'B+p_{2}'Gleq d}$

${displaystyle p_{1},p_{2}leq 0}$

Условия прекращения действия

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

Случай 1

Двойственная к подзадаче выше неограничена. В этом случае подзадача неосуществима, и двойственная подзадача образует обращенный вверх конус.

Обратите внимание, что это не означает, что подзадача невозможна для всех значений ${displaystyle x^{*}}$. Напомним, что изменение предложений основной задачи для ${displaystyle x^{*}}$ приведет к изменению вектора правой части (RHS) линейное программирование проблема, которая образует двойственное. Чтобы найти оптимальное решение в прямом, мы должны ограничить двойственное, сделав его оптимум конечным.

Обратите внимание, что согласно Анализ чувствительности, изменяя правую часть проблемы после некоторого порога, ${displaystyle delta }$, может изменить свой оптимум, изменив допустимое пространство.^[1] Это означает, что, несмотря на то, что примитив невозможен для этой подзадачи, он может стать выполнимым с другим предложением для ${displaystyle x^{*}}$. Теперь мы должны ограничить возможное пространство основной проблемы и найти новое предложение для ${displaystyle x^{*}}$.

Сокращение осуществимости: сокращение осуществимости - отличительный признак декомпозиции Бендера. Мы должны добавить новое ограничение к основной задаче: в этом случае мы хотим ограничить конус рецессии что мы нашли в двойственной подзадаче.

Случай 2

Двойственная подзадача невозможна. Как и в предыдущей задаче, это означает, что основная подзадача неосуществима. На этот раз, однако, это имеет совсем другие последствия: поскольку двойное допустимое пространство было пустым, мы знаем, что нет никаких изменений в векторе ${displaystyle x^{*}}$ это создаст возможную примитивную подзадачу. Это может означать, что проблема в целом невыполнима, или что общая проблема имеет неограниченную целевую функцию. В любом случае мы прекращаем работу.

Случай 3

Двойственная подзадача возвращает конечный оптимум. К теория двойственности, оптимум основной подзадачи тот же.

Смотрите также

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

Рекомендации

1. Берцимас, Димитрис (1997). Введение в линейную оптимизацию. Athena Scientific. п. 207. ISBN  1-886529-19-1.

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