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

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

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

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

История

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

Версия Гомори

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

{\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 неизвестен, и его необходимо найти, чтобы максимизировать цель при соблюдении линейных ограничений.

Общая идея

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

Шаг 1: решение расслабленной линейной программы

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

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

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

Шаг 2. Найдите линейное ограничение

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

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

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

{\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 ,

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

Заключение

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

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]

См. также

Ссылки

^ Гилмор, Пол С; Гомори, Ральф Э. (1961). «Подход к решению проблемы раскроя запасов с помощью линейного программирования». Исследование операций . 9 (6): 849–859. дои : 10.1287/опре.9.6.849 .
^ Гилмор, Пол С; Гомори, Ральф Э. (1963). «Подход к решению проблемы раскроя запасов с помощью линейного программирования. Часть II». Исследование операций . 11 (6): 863–888. дои : 10.1287/опре.11.6.863 .
^ Бойд, С.; Ванденберге, Л. (18 сентября 2003 г.). «Методы локализации и секущей плоскости» (конспект лекций курса) . Проверено 27 мая 2022 г.

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

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

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

[1] Гилмор, Пол С; Гомори, Ральф Э. (1961). «Подход к решению проблемы раскроя запасов с помощью линейного программирования». Исследование операций . 9 (6): 849–859. дои : 10.1287/опре.9.6.849 .

[2] Гилмор, Пол С; Гомори, Ральф Э. (1963). «Подход к решению проблемы раскроя запасов с помощью линейного программирования. Часть II». Исследование операций . 11 (6): 863–888. дои : 10.1287/опре.11.6.863 .

[3] Бойд, С.; Ванденберге, Л. (18 сентября 2003 г.). «Методы локализации и секущей плоскости» (конспект лекций курса) . Проверено 27 мая 2022 г.

[1]

[2]

[3]