Метод ветвей и отсечений для смешанно-целочисленного программирования (MILP)

Алгоритмической базой метода является классический метод ветвей и границ (Branch-and-Bound). Решение начинается с "релаксации" — временного снятия требований целочисленности и решения обычной задачи линейного программирования симплекс-методом. Если полученное решение содержит дробные значения для целочисленных переменных, происходит ветвление пространства поиска на две подзадачи (например, $x \le 0$ и $x \ge 1$). Дерево поиска разрастается, однако нижние и верхние оценки позволяют "отсекать" неперспективные ветви, значительно сокращая перебор. Тем не менее, для масштабных задач одного лишь ветвления критически недостаточно.

Настоящая мощь современных солверов (Gurobi, CPLEX) кроется в добавлении "отсечений" (Cuts) в каждом узле дерева поиска. Отсекающие плоскости — это дополнительные линейные ограничения, которые отрезают часть области непрерывной релаксации, содержащую текущее дробное решение, но гарантированно не затрагивают ни одной допустимой целочисленной точки. Наиболее известными являются отсечения Гомори (Gomory fractional cuts), смешанные целочисленные отсечения с округлением (MIR cuts) и отсечения покрытий для задач о рюкзаке (Knapsack cover cuts).

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

Искусство моделирования в MILP заключается в правильной формулировке задачи. Применение ограничений типа Big-M для описания логических условий ("если-то") должно выполняться с осторожностью, так как чрезмерно большие значения M ухудшают качество непрерывной релаксации. Владение принципами работы метода Branch-and-Cut позволяет аналитикам писать "сильные" (strong) модели, которые коммерческие солверы решают в десятки раз быстрее, обеспечивая бесперебойную оптимизацию индустриальных систем в режиме реального времени.

Список литературы:
1. Немхаузер Дж., Уолси Л. Целочисленное и комбинаторная оптимизация. — Wiley, 1988.
2. Шрайвер А. Теория линейного и целочисленного программирования. — М.: Мир, 1991.
3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. — М.: Мир, 1985.