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

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

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

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

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

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

${\displaystyle {\begin{aligned}{\text{Maximize }}&c^{T}x\\{\text{Subject to }}&Ax\leq b,\\&x\geq 0,\,x_{i}{\text{ all integers}}.\end{aligned}}}$

где A — матрица, а b, c — вектор. Вектор x неизвестен и должен быть найден для максимизации цели с учетом линейных ограничений.

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

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

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

где x _i — базисная переменная, а x j _— небазисные переменные (т. е. базисное решение, которое является оптимальным решением для расслабленной линейной программы, — это и ). Мы записываем коэффициенты и с чертой, чтобы обозначить последнюю таблицу, полученную симплексным методом. Эти коэффициенты отличаются от коэффициентов в матрице A и векторе b.${\displaystyle x_{i}={\bar {b}}_{i}}$${\displaystyle x_{j}=0}$${\displaystyle {\bar {b}}_{i}}$${\displaystyle {\bar {a}}_{i,j}}$

Рассмотрим теперь базовую переменную , которая не является целым числом. Перепишите приведенное выше уравнение так, чтобы целые части были добавлены в левой части, а дробные части — в правой части:${\displaystyle x_{i}}$

${\displaystyle x_{i}+\sum _{j}\lfloor {\bar {a}}_{i,j}\rfloor x_{j}-\lfloor {\bar {b}}_{i}\rfloor ={\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}.}$

Для любой целочисленной точки в допустимой области левая сторона является целым числом, поскольку все члены , , , являются целыми числами. Правая сторона этого уравнения строго меньше 1: действительно, строго меньше 1, а отрицательно. Поэтому общее значение должно быть меньше или равно 0. Поэтому неравенство${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle \lfloor {\bar {a}}_{i,j}\rfloor }$${\displaystyle \lfloor {\bar {b}}_{i}\rfloor }$${\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor }$${\displaystyle -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}}$

${\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}\leq 0}$

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

${\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\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 {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum _{j}({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}}$

${\displaystyle x_{k}+\sum _{j}(\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{ an integer}}.}$

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

• Разложение Бендерса
• Ветвь и разрез
• Ветви и границы
• Генерация столбцов
• Разложение Данцига–Вульфа

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

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