Режущий метод - Cutting-plane method

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

{ Displaystyle x_ {1} + x_ {2} + x_ {3} geq 2}

. В контексте задачи коммивояжера на трех узлах это (довольно слабое^{[Зачем? ]}) неравенство утверждает, что каждый тур должен иметь не менее двух ребер.

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

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

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

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

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

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

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

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

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

{ displaystyle x_ {i} + sum { bar {a}} _ {i, j} x_ {j} = { bar {b}} _ {i}}

где Икс_я - основная переменная, а Икс_j's - неосновные переменные. Перепишите это уравнение так, чтобы целые части были слева, а дробные части - справа:

{ 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}.}

Для любой целочисленной точки в допустимой области правая часть этого уравнения меньше 1, а левая часть - целое число, поэтому общее значение должно быть меньше или равно 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}

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

{ 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 .}

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

{ 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} { mbox {целое число}} .}

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

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

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

использованная литература

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

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

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