Оптимизация
Целочисленное программирование
2016 год. Deutsche Lufthansa планирует расписание для 400 самолётов и 10 000 рейсов. Без ILP потребовались бы сотни человеко-лет ручной работы. Gurobi решает эту задачу за несколько часов. Задача коммивояжёра, расписание больницы, отбор проектов в венчурном фонде - все эти задачи нельзя решить обычным LP. Нужны целые числа.
- **Авиация:** планирование экипажей (crew pairing) - крупнейшие ILP в мире, миллионы переменных, Gurobi/CPLEX решает за часы
- **ML-инженерия:** отбор признаков и выбор архитектуры нейросети как 0-1 ILP - находит оптимальный subset признаков по заданному бюджету
- **Логистика:** Amazon оптимизирует распределение товаров по складам через MIP, сокращая время доставки на 15-20%
Предварительные знания
Исторический контекст
В 1958 году Ральф Гомори, работая в IBM, разработал метод отсекающих плоскостей (Gomory cuts) для решения ILP. До этого не существовало систематического алгоритма для целочисленных задач. Метод ветвей и границ был независимо предложен Лэнд и Дойгом в 1960 году. Комбинация Branch & Bound с Gomory cuts стала основой всех современных ILP-солверов. Gurobi (2008) и CPLEX (1988) используют эти идеи, усиленные тысячами дополнительных cut-типов - Cover cuts, MIR cuts, Clique cuts.
Формулировка ILP
LP позволяет переменным принимать дробные значения - например, 2.7 самолёта. Но в реальных задачах нужны **целые числа**: нельзя нанять 3.5 сотрудника или поставить 0.8 завода. **Integer Linear Programming (ILP)** добавляет к LP ограничение xᵢ ∈ ℤ (или xᵢ ∈ {0,1} для двоичных задач). Это превращает задачу из полиномиальной в NP-сложную.
| Тип задачи | Переменные | Пример |
|---|---|---|
| LP (линейное) | Вещественные: x ∈ ℝⁿ | Смешение красок в нужной пропорции |
| ILP (целочисленное) | Целые: x ∈ ℤⁿ | Количество рейсов на маршруте |
| 0-1 ILP (двоичное) | Двоичные: x ∈ {0,1}ⁿ | Включить/выключить признак в модели |
| MIP (смешанное) | Часть вещественных, часть целых | Производственный план + транспорт |
**Отбор признаков как 0-1 ILP:** выбрать k признаков из n, максимизируя качество модели при бюджете k - классический Binary ILP. Переменная xᵢ = 1 означает «включить признак i». Ограничение: Σxᵢ ≤ k.
Компания хочет открыть максимум 3 склада из 10 возможных мест, минимизируя стоимость доставки. Какой тип задачи это описывает?
Ветви и границы
Наивный перебор для задачи с n двоичными переменными требует проверки 2ⁿ вариантов. **Branch and Bound** умнее: строит дерево подзадач, на каждом узле решает LP-релаксацию (убирает целочисленное ограничение) и «отрезает» ветви, которые не могут улучшить текущее лучшее решение.
Ключевая идея: LP-релаксация всегда даёт **верхнюю границу** (upper bound) для задачи максимизации. Если lp_relaxation(узел) ≤ текущее_лучшее_целое_решение - ветвь отсекаем, не разворачивая. Это сокращает дерево экспоненциально на практике.
Branch and Bound гарантирует нахождение **глобального оптимума**, но в худшем случае (патологические задачи) всё равно перебирает экспоненциальное число узлов. Хороший нижний bound (heuristic feasible solution) критически важен для эффективной работы.
В узле дерева Branch & Bound LP-релаксация даёт z=8.5. Текущее лучшее целое решение - z=9. Что делаем с этим узлом?
Метод отсекающих плоскостей
**Cutting planes** - альтернативный подход: вместо ветвления добавляем новые линейные ограничения (cuts), которые «срезают» дробные части LP-оптимума, не отрезая ни одного целого допустимого решения. Повторяем до тех пор, пока LP-оптимум не станет целым.
**Branch & Cut** - стандарт современных ILP-солверов (Gurobi, CPLEX, CBC). Комбинирует Branch & Bound с cutting planes: на каждом узле добавляет cuts для усиления LP-bound, затем ветвится. Это позволяет решать задачи с миллионами переменных.
| Метод | Идея | Когда применять |
|---|---|---|
| Pure Branch & Bound | Только ветвление и bounds | Маленькие задачи, простая структура |
| Cutting Planes | Только добавление cuts | Плотные задачи с сильной LP-релаксацией |
| Branch & Cut | B&B + cuts на каждом узле | Промышленный стандарт для MIP |
| Column Generation | Динамически добавляем переменные | Задачи с огромным числом переменных (routing) |
Зачем нужны отсекающие плоскости (cutting planes) в ILP, если Branch & Bound уже гарантирует оптимум?
MIP на практике: PuLP и CBC
Mixed-Integer Programs (MIP) - задачи, где часть переменных целая, часть вещественная. Это наиболее общая форма ILP. На практике используют специализированные солверы, которые реализуют Branch & Cut с большим числом эвристик, presolve и warm starts.
**Отбор признаков в ML как 0-1 ILP:** формулируем задачу выбора k из n признаков. Переменная xᵢ ∈ {0,1}. Цель: максимизировать качество модели (accuracy, AUC). Ограничение: Σxᵢ ≤ k и бюджет вычислений. PuLP + CBC справляется с n=100-500 признаками за секунды.
Если LP-релаксация даёт целое решение, то это оптимум ILP
LP-оптимум с целыми значениями - действительно оптимум ILP, но это бывает только для специальных матриц ограничений (total unimodular matrices). Для общего ILP LP-релаксация всегда даёт дробное решение.
Матрицы ограничений типа «задача о назначении» и «задача о максимальном потоке» тотально унимодулярны (TU). Для TU-задач LP-оптимум автоматически целый. Именно поэтому задача о назначении решается как LP без явного Branch & Bound.
MIP-солвер (Gurobi, CBC) изнутри использует комбинацию методов. Что входит в стандартный Branch & Cut?
Ключевые идеи
- **ILP** добавляет к LP ограничение целочисленности; задача становится NP-сложной, но реальные экземпляры решаются эффективно
- **Branch & Bound** строит дерево LP-подзадач, отсекая ветви по LP-bounds; гарантирует глобальный оптимум
- **Cutting planes (Gomory cuts)** усиляют LP-relaxation, добавляя линейные ограничения без отсечения целых решений
- **Branch & Cut** = B&B + cuts - промышленный стандарт (Gurobi, CPLEX, CBC); решает MIP с миллионами переменных
Вопросы для размышления
- Почему LP-релаксация даёт верхнюю границу (для максимизации) оптимума ILP? Как это связано с тем, что допустимое множество ILP - подмножество допустимого множества LP?