Режущие плоскости и Branch-and-Cut

Идея: «срезаем» дробные углы

ЛП-релаксация может давать дробные оптимумы (x₁ = 1.5, x₂ = 0.7...). Можно ли добавить «умные» линейные ограничения, которые «срежут» эти дробные решения, не убирая при этом ни одного целочисленного? Именно это делают режущие плоскости (cutting planes). Вместо того чтобы сразу ветвиться, добавляем такие плоскости, «подтягивая» ЛП-оптимум к целочисленному. Комбинация режущих плоскостей и B&B — это Branch-and-Cut — стандарт современных ЦЛП-решателей.

Что такое режущая плоскость?

Определение: неравенство aᵀx ≤ b называется режущей плоскостью для ЦЛП, если:

1. Оно выполнено для всех целочисленных допустимых точек x ∈ {0,1}ⁿ
2. Оно нарушено для текущего ЛП-оптимума x* (дробного)

Добавляя такое неравенство, мы «отрезаем» дробный x*, но не теряем ни одного целочисленного решения. Новая ЛП-релаксация даёт лучшую (более высокую) нижнюю оценку.

Отсечения Гомори

Идея Ральфа Гомори (1958): взять строку симплекс-таблицы для дробной переменной и сгенерировать режущую плоскость.

Процедура: пусть xᵢ = a₀ + Σⱼ aⱼ sⱼ (строка симплекс-таблицы, sⱼ — небазисные переменные). Пишем xᵢ = ⌊a₀⌋ + f₀ + Σⱼ (⌊aⱼ⌋ + fⱼ) sⱼ, где fⱼ = aⱼ − ⌊aⱼ⌋ ∈ [0,1).

Так как xᵢ целочисленна: Σⱼ fⱼ sⱼ − f₀ ∈ ℤ. Поскольку sⱼ ≥ 0: Σⱼ fⱼ sⱼ ≥ f₀ > 0.

Отсечение Гомори: Σⱼ fⱼ sⱼ ≥ f₀. Это нарушается для текущего решения (sⱼ = 0 → 0 ≥ f₀ > 0), но выполняется для целочисленных.

Теорема Гомори: за конечное число итераций с отсечениями Гомори любое ограниченное ЦЛП решается оптимально.

Отсечения для TSP: неравенства подтуров

TSP — «испытательный полигон» режущих плоскостей. Ключевые отсечения:

Неравенства исключения подтуров: для любого подмножества городов S ⊊ V, |S| ≥ 2:

Σ_{(i,j) ∈ E, i∈S, j∈S} xᵢⱼ ≤ |S| − 1

Смысл: в подмножестве S из k городов не может быть k или более рёбер маршрута (иначе образуется замкнутый подмаршрут).

Число таких неравенств: 2^n — экспоненциально! Не добавляем их все сразу. Вместо этого: задача разделения — для данного дробного x* найти нарушенное неравенство. Для подтурных — минимальный разрез в сети за O(n²).

Comb inequalities (более сильные): отсечения вида «ручка + зубья». Теоретически лучше, практически сложнее генерировать.

Branch-and-Cut: алгоритм

1. Корневой узел: решаем ЛП-релаксацию
2. Cutting plane loop: пока есть нарушенные режущие плоскости:
   • Найти нарушенное неравенство (задача разделения)
   • Добавить его в ЛП
   • Пересчитать ЛП
3. Если решение целочисленное → обновляем incumbent, отсекаем
4. Если дробное → ветвимся (B&B)
5. В каждом узле дерева снова применяем шаги 2-3

Почему это мощнее чистого B&B: режущие плоскости «подтягивают» ЛП-оценки к целочисленным, делая отсечение более агрессивным. Меньше узлов нужно исследовать.

Типы отсечений в современных решателях

Gurobi/CPLEX автоматически генерируют разные типы отсечений:

• Gomory cuts: общие для любого ЦЛП
• Cover cuts: специально для задач о рюкзаке (неравенства на покрытия)
• Clique cuts: для задач с ограничениями кликов
• Flow cuts: для задач с сетевой структурой
• MIR cuts (Mixed Integer Rounding): обобщение Гомори

Полный разбор: подтурные отсечения для TSP

Данные: 4 города, матрица расстояний d = [[0,2,9,10],[1,0,6,4],[15,7,0,8],[6,3,12,0]].

ЛП-оптимум (без отсечений): дробное решение, например x₁₂ = x₂₁ = 0.5, x₃₄ = x₄₃ = 0.5, x₁₃ = x₁₄ = 0.5 — «двойной» подмаршрут.

Нарушенное подтурное неравенство: для S = {1,2}: x₁₂ + x₂₁ ≤ 1. Текущее значение: 0.5 + 0.5 = 1. Не нарушено строго — ищем другое.

Для S = {3,4}: x₃₄ + x₄₃ ≤ 1. Также = 1. Добавляем оба ограничения.

После добавления: ЛП перерешается, дробность уменьшается. Через несколько итераций ЛП-оптимум становится целочисленным или B&B завершает задачу.

Виды отсекающих плоскостей

Помимо классических разрезов Гомори (Gomory cuts) на основе симплексной таблицы, в Branch-and-Cut применяются:

• MIR-разрезы (Mixed Integer Rounding): обобщение Гомори на смешанные задачи
• Cover cuts: для задач рюкзака — если подмножество предметов перевешивает W, то не все его элементы можно взять
• Clique cuts: для конфликтного графа переменных — если в клике K переменных не более одной может быть 1, добавляем Σxᵢ ≤ 1
• Flow cover cuts: для сетевых задач
• Lift-and-project cuts (Балас, Сересса, Корнюэжолс): сильные разрезы из 0-1-ограничений

Branch-and-Cut workflow

Современный решатель сочетает ветвление с агрессивной генерацией разрезов:

1. На каждом узле решается ЛП-релаксация
2. Если решение не целочисленное — пробуется добавить разрезы для усиления оценки
3. Если разрезы помогают — продолжаем их добавлять (cut loop)
4. Если разрезы перестали улучшать — ветвимся

Этот подход совместно с эвристиками превратил ЦЛП из «теоретически интересной» в практически решаемую задачу — за 25 лет (1990-2015) скорость решателей выросла в миллион раз.

Применения

Branch-and-Cut решает крупнейшие в мире задачи маршрутизации (TSP до 85 900 городов решён точно — Pla85900), календарного планирования атомных электростанций (EDF, Франция), оптимизации поставок газа (E.ON).