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

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

Описание

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

minimize c'x
subject to Ax = b, x >= 0, x - integer. (1)

Для решения методом ЛП-релаксации

minimize c'x
subject to Ax = b, x >= 0. (2)

Основная идея метода секущих плоскостей — решение задачи целочисленного программирования путём решения последовательности задач линейного программирования. Сначала решается задача (2) и находится оптимальное решение x*. Если x* числовое, тогда оно является решением задачи (1) целочисленного программирования. Если нет, то производится поиск неравенства, которому все целочисленный решения задачи (1) удовлетворяют, а решение x* нет. Добавляя такое неравенство к задаче линейного программирования и решая его, выполняем шаг итерации метода секущих плоскостей.

Формальное описание

Более формальное описание метода секущих плоскостей может быть записано следующим образом.

1. Решить линейную задачу (2). Пусть x* - оптимальное решение.
2. Если x* числовое, то задача решена.
3. В противном случае добавляем неравенство к задаче (2), которому не удовлетворяет x*, но удовлетворяет любое другое целочисленное решение.

См. также

• Алгоритм Гомори

Литература

• Bertsimas В., Tsitsiklis J. N. Introduction to Linear Optimization, p480