Решить задачу целочисленного программирования методом гомори

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

x1+x2+x32{\displaystyle x_{1}+x_{2}+x_{3}\geq 2}

. В контексте проблемы коммивояжера на трех узлах это (довольно слабое[почему?]) неравенство гласит. Что каждый тур должен иметь по крайней мере два ребра.

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

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

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

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

Методы плоскости резания для общей выпуклой непрерывной оптимизации и их варианты известны под различными названиями: метод Келли. Метод Келли–Чейни–Гольдштейна и методы

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

Генерация этих переменных по требованию посредством отложенной генерации столбцов идентична выполнению плоскости среза на соответствующей двойной задаче.

Отрезок Гомори

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

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

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

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

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

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

где xi-базовая переменная, а xjнеосновные переменные. Перепишите это уравнение так. Чтобы целые части находились слева. А дробные-справа:

xi+a¯i,jxjb¯i=b¯ib¯i(a¯i,ja¯i,j)xj.{\displaystyle 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¯ib¯i(a¯i,ja¯i,j)xj0{\displaystyle {\bar {b}}_{i}-\lfloor {\bar {b}}_{i}\rfloor -\sum ({\bar {a}}_{i,j}-\lfloor {\bar {a}}_{i,j}\rfloor )x_{j}\leq 0}

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

b¯ib¯i(a¯i,ja¯i,j)xj=b¯ib¯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.}

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

xk+(a¯i,ja¯i,j)xj=b¯ib¯i,xk0,xk an integer.{\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{ an integer}}.}

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

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

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