Метод секущей плоскости

редактировать

Метод оптимизации для решения (смешанных) целочисленных линейных программ

Пересечение единичный куб с секущей плоскостью

x 1 + x 2 + x 3 ≥ 2 {\ displaystyle x_ {1} + x_ {2} + x_ {3} \ geq 2}

{\ displaystyle x_ {1} + x_ {2} + x_ {3} \ geq 2}

. В контексте задачи коммивояжера на трех узлах это (довольно слабое) неравенство утверждает, что каждая поездка должна иметь как минимум два ребра.

В математической оптимизации, метод секущей плоскости представляет собой любой из множества методов оптимизации, которые итеративно уточняют допустимый набор или целевую функцию посредством линейных неравенств, называемых разрезами. Такие процедуры обычно используются для поиска целочисленных решений задач смешанного целочисленного линейного программирования (MILP), а также для решения общих, не обязательно дифференцируемых задач выпуклой оптимизации.. Использование секущих плоскостей для решения MILP было введено Ральфом Э. Гомори.

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

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

Содержание

1 Разрез Гомори
2 Выпуклая оптимизация
3 См. Также
4 Ссылки
5 Внешние ссылки

Разрез Гомори

Режущие плоскости были предложены Ральф Гомори в 1950-х годах как метод решения задач целочисленного и смешанно-целочисленного программирования. Однако большинство экспертов, включая самого Гомори, сочли их непрактичными из-за численной нестабильности, а также неэффективными, поскольку для продвижения к решению требовалось много раундов сокращений. Ситуация изменилась, когда в середине 1990-х годов Жерар Корнежоль и его коллеги показали, что они очень эффективны в сочетании с ветвями и связями (так называемыми ветвями и- вырез ) и способы преодоления числовой нестабильности. В настоящее время все коммерческие программы-решатели MILP так или иначе используют разрезы Гомори. Разрезы Гомори очень эффективно генерируются из симплексной таблицы, тогда как многие другие типы разрезов либо дороги, либо даже NP-трудны для разделения. Среди других общих сокращений для MILP наиболее заметно преобладают сокращения Гомори.

Пусть задача целочисленного программирования сформулирована (в Стандартной форме ) как:

Максимизировать c T x с учетом A x ≤ b, x ≥ 0, xi все целые числа. {\ displaystyle {\ begin {align} {\ text {Maximize}} c ^ {T} x \\ {\ text {Subject to}} Ax \ leq b, \\ x \ geq 0, \, x_ {i} {\ text {все целые числа}}. \ end {align}}}

{\ displaystyle {\ begin {align} {\ text {Maximize}} c ^ {T} x \\ {\ text {Subject to}} Ax \ leq b, \\ x \ geq 0, \, x_ {i} {\ text {все целые числа}}. \ end {align}}}

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

Использование симплекс-метода для решения линейной программы дает набор уравнений вида

xi + ∑ a ¯ i, jxj = b ¯ i {\ displaystyle x_ {i } + \ sum {\ bar {a}} _ {i, j} x_ {j} = {\ bar {b}} _ {i}}

x_i + \ sum \ bar a_ {i, j} x_j = \ bar b_i

где x i - базовая переменная и x j - это небазовые переменные. Перепишите это уравнение так, чтобы целые части были слева, а дробные части - справа:

xi + ∑ ⌊ a ¯ i, j ⌋ xj - ⌊ b ¯ i ⌋ = b ¯ i - ⌊ b ¯ i ⌋ - ∑ (a ¯ i, j - ⌊ a ¯ i, j ⌋) xj. {\ displaystyle x_ {i} + \ sum \ lfloor {\ bar {a}} _ {i, j} \ rfloor x_ {j} - \ lfloor {\ bar {b}} _ {i} \ rfloor = {\ бар {b}} _ {i} - \ lfloor {\ bar {b}} _ {i} \ rfloor - \ sum ({\ bar {a}} _ {i, j} - \ lfloor {\ bar {a }} _ {i, j} \ rfloor) x_ {j}.}

x_i + \ sum \ lfloor \ bar a_ {i, j} \ rfloor x_j - \ lfloor \ bar b_i \ rfloor = \ bar b_i - \ lfloor \ bar b_i \ rfloor - \ sum (\ bar a_ {i, j} - \ lfloor \ bar a_ {i, j} \ rfloor) x_j.

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

b ¯ i - ⌊ b ¯ i ⌋ - ∑ (a ¯ i, j - ⌊ a ¯ i, j ⌋) xj ≤ 0 {\ displaystyle {\ bar {b}} _ {i} - \ lfloor {\ bar {b}} _ {i} \ rfloor - \ sum ({\ bar {a}} _ {i, j} - \ lfloor {\ bar {a}) } _ {i, j} \ rfloor) x_ {j} \ leq 0}

\ bar b_i - \ lfloor \ bar b_i \ rfloor - \ sum (\ bar a_ {i, j} - \ lfloor \ bar a_ {i, j} \ rfloor) x_j \ le 0

должно выполняться для любой целочисленной точки в допустимой области. Кроме того, небазовые переменные равны 0 в любом базовом решении, и если x i не является целым числом для базового решения x,

b ¯ i - ⌊ b ¯ i ⌋ - ∑ (a ¯ i, j - ⌊ a ¯ i, j ⌋) xj = b ¯ i - ⌊ b ¯ i ⌋>0. {\ displaystyle {\ bar {b}} _ {i} - \ lfloor {\ bar {b}} _ {i} \ rfloor - \ sum ({\ bar {a}} _ {i, j} - \ lfloor {\ bar {a}} _ {i, j} \ rfloor) x_ {j} = {\ bar {b}} _ {i} - \ lfloor {\ bar {b}} _ {i} \ rfloor>0.}

\bar b_i - \lfloor \bar b_i \rfloor - \sum ( \bar a_{i,j} -\lfloor \bar a_{i,j} \rfloor) x_j = \bar b_i - \lfloor \bar b_i \rfloor>0.

Таким образом, приведенное выше неравенство исключает базовое допустимое решение и, таким образом, представляет собой разрез с желаемыми свойствами. Вводя новую переменную резерва x k для этого неравенства, в линейную программу добавляется новое ограничение, а именно

xk + ∑ (⌊ a ¯ i, j ⌋ - a ¯ i, j) xj = ⌊ b ¯ i ⌋ - b ¯ i, xk ≥ 0, xk целое число. {\ displaystyle x_ {k} + \ sum (\ lfloor {\ bar {a}} _ {i, j} \ rfloor - {\ bar {a}} _ {i, j}) x_ {j} = \ lfloor {\ bar {b}} _ {i} \ rfloor - {\ bar {b}} _ {i}, \, x_ {k} \ geq 0, \, x_ {k} {\ t_dv {целое число}}.}

x_k + \ sum (\ lfloor \ bar a_ {i, j} \ rfloor - \ bar a_ {i, j}) x_j = \ lfloor \ bar b_i \ rfloor - \ bar b_i, \, x_k \ ge 0, \, x_k \ t_dv { целое число}.

Выпуклая оптимизация

Методы секущей плоскости также применимы в нелинейном программировании. Основной принцип заключается в приближении допустимого r egion нелинейной (выпуклой) программы конечным набором замкнутых полупространств и решить последовательность аппроксимирующих линейных программ.

См. также

Ссылки

Marchand, Hugues; Мартин, Александр; Weismantel, Роберт; Уолси, Лоуренс (2002). «Режущие плоскости в целочисленном и смешанном целочисленном программировании». Дискретная прикладная математика. 123 (1–3): 387–446. doi : 10.1016 / s0166-218x (01) 00348-1.
Авриэль, Мордехай (2003). Нелинейное программирование: анализ и методы. Dover Publications. ISBN 0-486-43227-0
Корнежоль, Жерар (2008). Допустимые неравенства для смешанных целочисленных линейных программ. Математическое программирование Сер. В, (2008) 112: 3–44. [1]
Корнежоль, Жерар (2007). Возрождение Гоморских отрубов в 1990-е гг. Анналы исследований операций, Vol. 149 (2007), стр. 63–66. [2]

Внешние ссылки

«Целочисленное программирование» Раздел 9.8 Прикладное математическое программирование Глава 9 Целочисленное программирование (полный текст). Брэдли, Хакс и Маньянти (Аддисон-Уэсли, 1977)