Генерация столбца

Генерация столбцов или генерация столбцов с задержкой — эффективный алгоритм решения больших линейных программ .

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

Во многих случаях этот метод позволяет решать большие линейные программы, которые в противном случае были бы трудноразрешимы. Классическим примером задачи, в которой он успешно применяется, является задача о раскрое запасов . Одним из конкретных методов линейного программирования, использующих такой подход, является алгоритм декомпозиции Данцига – Вольфа . Кроме того, генерация столбцов применялась для решения многих задач, таких как планирование бригады , маршрутизация транспортных средств и проблема с емкостной p-медианой .

Алгоритм

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

Далее алгоритм действует следующим образом:

1. Инициализируйте основную проблему и подзадачу
2. Решите главную проблему
3. Поиск улучшающей переменной с помощью подзадачи
4. Если найдена улучшающая переменная: добавьте ее к основной проблеме, затем перейдите к шагу 2.
5. Иначе: Решение основной задачи оптимально. Останавливаться.

Поиск улучшающей переменной

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

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

Теперь мы подробно расскажем, как и почему вычислять приведенную стоимость переменных. Рассмотрим следующую линейную программу в стандартной форме:

${\begin{aligned}&\min _{x}c^{T}x\\&{\text{subjected to}}\\&Ax=b\\&x\in \mathbb {R} ^{+}\end{aligned}}$

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

${\begin{aligned}&\max _{u}u^{T}b\\&{\text{subjected to}}\\&u^{T}A\leq c\\&u\in \mathbb {R} \end{aligned}}$

Более того, пусть $x^{*}$ и $u^{*}$ быть оптимальными решениями для этих двух задач, которые могут быть предоставлены любым линейным решателем. Эти решения проверяют ограничения своей линейной программы и в силу двойственности имеют одинаковое значение целевой функции ( $c^{T}x^{*}=u^{*T}b$), который мы назовем $z^{*}$. Это оптимальное значение является функцией различных коэффициентов основной задачи: $z^{*}=z^{*}(c,A,b)$. Обратите внимание, что существует двойственная переменная $u_{i}^{*}$ для каждого ограничения основной линейной модели. Можно показать, что оптимальная двойственная переменная $u_{i}^{*}$ можно интерпретировать как частную производную оптимального значения $z^{*}$ целевой функции по коэффициенту $b_{i}$ правой части ограничений: $u_{i}^{*}={\frac {\partial z^{*}}{\partial b_{i}}}$ или иначе $u^{*}={\frac {\partial z^{*}}{\partial b}}$. Проще говоря, $u_{i}^{*}$ показывает, насколько локально увеличивается оптимальное значение целевой функции при коэффициенте $b_{i}$ увеличивается на одну единицу.

Предположим теперь, что переменная $y$ до сих пор не рассматривалась в основной задаче. Обратите внимание, что это эквивалентно тому, что переменная $y$ присутствовал в модели, но принимал нулевое значение. Теперь мы будем наблюдать влияние на основную проблему изменения стоимости $y$ от $0$ к ${\hat {y}}$. Если $c_{y}$ и $A_{y}$ соответственно коэффициенты, связанные с переменной $y$ в целевой функции и в ограничениях, то линейная программа модифицируется следующим образом:

${\begin{aligned}&\min _{x}c^{T}x+c_{y}{\hat {y}}\\&{\text{subjected to}}\\&Ax=b-A_{y}{\hat {y}}\\&x\in \mathbb {R} ^{+}\end{aligned}}$

Чтобы узнать, интересно ли добавить переменную $y$ к проблеме ( т.е. позволить ей принимать ненулевое значение), мы хотим знать, является ли значение $z_{\hat {y}}^{*}$ целевой функции этой новой задачи уменьшается по мере того, как значение ${\hat {y}}$ переменной $y$ увеличивается. Другими словами, мы хотим знать ${\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}$. Для этого обратите внимание, что $z_{\hat {y}}^{*}$ может быть выражено через значение целевой функции исходной основной задачи: $z_{\hat {y}}^{*}=c_{y}{\hat {y}}+z^{*}(c,A,b-A_{y}{\hat {y}})$. Затем мы можем вычислить интересующую нас производную:

${\begin{aligned}{\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial {\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial c}}{\frac {dc}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial A}}{\frac {dA}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+u^{*}(-A_{y})\\&~=~&&c_{y}-u^{*}A_{y}\end{aligned}}$

Другими словами, влияние изменения стоимости ${\hat {y}}$ по стоимости $z_{\hat {y}}^{*}$ переводится в два термина. Во-первых, это изменение напрямую влияет на целевую функцию, а во-вторых, изменяется правая часть ограничений, что влияет на оптимальные переменные. $x^{*}$ величина которого измеряется с использованием двойных переменных $u^{*}$. Производная ${\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}$ обычно называется приведенной стоимостью переменной $y$ и будет обозначаться $cr_{y}$ в следующем.