Метод ветвей и границ (Branch and Bound)

Принцип «умного перебора»

Полный перебор всех вариантов невозможен при больших n. Но можно быть умнее: если на каком-то шаге мы знаем, что «дальше ничего хорошего не будет» — отсечём целую ветвь дерева перебора. Метод ветвей и границ (Branch and Bound, B&B) систематизирует эту идею. Это основа всех промышленных ЦЛП-решателей. Когда Gurobi «решает» задачу с миллионом переменных — внутри работает B&B с множеством эвристик.

Структура алгоритма

Дерево поиска: каждый узел — это подзадача с дополнительными ограничениями. Корень — исходная задача без дополнительных ограничений.

Нижняя оценка (lower bound, LB) для узла: минимально возможное значение целевой функции в этом узле. Обычно — оптимум ЛП-релаксации подзадачи.

Лучшее найденное решение (incumbent): лучшее целочисленное решение, найденное на данный момент.

Правило отсечения: если LB(узел) ≥ incumbent, этот узел бесполезен — отсекаем его вместе со всеми потомками.

Алгоритм Branch and Bound

1. Инициализация: корневой узел = исходная ЛП-релаксация. incumbent = ∞.

2. Выбор узла: выбираем активный (не отсечённый) узел для обработки.

3. Вычисление нижней оценки: решаем ЛП-релаксацию в этом узле.

   • Если ЛП нет решения: отсекаем (задача нед допустима).
   • Если LB ≥ incumbent: отсекаем (не лучше текущего решения).
   • Если ЛП-оптимум целочисленный: обновляем incumbent.

4. Ветвление: берём дробную переменную xᵢ = α (α ∉ ℤ). Создаём две дочерние подзадачи:

   • Ветвь «вниз»: добавляем xᵢ ≤ ⌊α⌋
   • Ветвь «вверх»: добавляем xᵢ ≥ ⌈α⌉

5. Добавляем дочерние узлы в очередь активных. Повторяем с шага 2.

Стратегии ветвления

Выбор переменной для ветвления:

• Most Fractional: выбираем xᵢ ближайший к 0.5 (наиболее «дробный»)
• Strong Branching: решаем ЛП-релаксацию обеих ветвей для нескольких кандидатов, выбираем лучший. Дорого, но даёт меньше узлов.
• Pseudocost Branching: используем историю прошлых ветвлений для предсказания «полезности»

Стратегии обхода дерева:

• Best-First Search: выбираем узел с минимальной нижней оценкой. Быстро достигает оптимума, но требует много памяти.
• Depth-First Search: углубляемся по одной ветви. Быстро находим допустимые решения (обновляем incumbent), экономия памяти.
• Комбинация: depth-first до нахождения incumbent, потом best-first.

Нижние оценки: ЛП и Лагранжева релаксация

ЛП-оценка: решаем ЛП-релаксацию. Хорошая оценка, но вычислительно дорого.

Лагранжева релаксация: «смягчаем» часть ограничений, добавляя их в цель со штрафами λ.

Задача ЦЛП: min cᵀx при Ax ≥ b, Bx ≤ d, x ∈ {0,1}ⁿ.

Лагранжева подзадача: Lₗ(λ) = min_{x ∈ {0,1}ⁿ, Bx ≤ d} {cᵀx + λᵀ(b − Ax)}.

Если Bx ≤ d — «простая» структура (например, задача о назначении), Lₗ(λ) решается легко!

Lₗ(λ) — нижняя оценка для любого λ ≥ 0. Лучшая оценка: max_{λ ≥ 0} Lₗ(λ) — задача Лагранжевой двойственности, решается субградиентным методом.

Полный разбор: задача о рюкзаке через B&B

Задача: W=10, предметы (c,w): (6,4), (5,3), (4,2), (3,1).

Корневой узел: ЛП-релаксация. Жадное решение по соотношению c/w: берём 4 (c=3,w=1), 3 (c=4,w=2), 2 (c=5,w=3). Остаток 4 кг → берём 6/4 = 1.5 единицы предмета 1: x₁ = 1, x₂ = 1, x₃ = 1, x₄ = 1, ценность = 3+4+5+6=18. LB = 18 (целочисленное!).

incumbent = 18. Ответ найден в корне без ветвлений. Оптимум = 18!

(В более сложных примерах с нецелочисленным ЛП-оптимумом нужно ветвиться.)

Производительность на практике

Рекорд TSP: 85,900 городов (США) решено оптимально в 2006 году (Applegate, Bixby, Chvátal, Cook). Время: несколько месяцев на кластере компьютеров. Использованы: B&B + режущие плоскости + мощные эвристики.

Gurobi 10.0: задачи с 10⁶ переменных и 10⁵ ограничений решаются за секунды-минуты (для хорошо структурированных задач). Используется: Boeing (расписания), Google (оптимизация рекламы), банки (управление портфелем).

Эвристики поиска в B&B

Современные ЦЛП-решатели (Gurobi, CPLEX) ускоряют B&B десятками эвристик:

• Эвристики выбора переменной для ветвления: pseudocost branching, strong branching, reliability branching
• Эвристики выбора узла: best-first, depth-first, best-estimate
• Презолвинг (presolve): упрощение задачи до начала поиска (фиксирование переменных, агрегирование ограничений)
• Простейшие эвристики поиска целочисленного решения: feasibility pump, RINS, local branching — позволяют быстро найти incumbent для агрессивного отсечения

Параллелизация

B&B хорошо параллелизуется: разные узлы дерева могут обрабатываться независимыми потоками или машинами. Промышленные решатели поддерживают многопоточность с сотнями ядер. Сложности: балансировка нагрузки (некоторые ветви глубже других), синхронизация incumbent (чтобы все потоки использовали лучшее текущее решение).

Применения

B&B решает реальные задачи планирования авиаперевозок (American Airlines, более миллиона переменных), оптимизации сетей доставки (UPS, FedEx), составления школьных расписаний, портфельной оптимизации с дискретными решениями (число акций), задач VLSI-проектирования.