Метод ветвей и цены (Branch-and-Price): генерация столбцов в целочисленном программировании

Математическая концепция метода вырастает из алгоритма декомпозиции Данцига-Вулфа (Dantzig-Wolfe Decomposition). При моделировании расписаний экипажей естественной переменной $x_j$ является допустимый график работы одного экипажа на месяц (столбец). Поскольку таких комбинаций астрономически много (миллиарды), загрузить всю матрицу в симплекс-метод невозможно. Метод генерации столбцов решает усеченную главную задачу (Restricted Master Problem, RMP), содержащую лишь малую долю базовых столбцов. Для поиска новых, перспективных столбцов используется вспомогательная задача (Pricing Problem), которая, используя двойственные оценки (теневые цены) из RMP, ищет столбец с минимальной отрицательной приведенной стоимостью (Reduced Cost).

В задачах MILP решение, полученное генерацией столбцов, часто оказывается дробным. Для получения целочисленного решения необходимо применить ветвление. Однако классическое ветвление на переменных (например, принудительное установление дробной переменной $x_j = 0$) вступает в разрушительный конфликт с логикой генерации столбцов. Если мы запрещаем использование определенного столбца (маршрута), вспомогательная задача ценообразования (часто реализуемая как поиск кратчайшего пути с ограничениями на графе) с высокой вероятностью сгенерирует тот же самый маршрут на следующей итерации, нарушая логику дерева поиска.

Метод Branch-and-Price решает эту фундаментальную проблему через использование специализированных правил ветвления (Branching Rules), которые не ломают структуру задачи ценообразования. Классическим примером является правило Райана-Фостера (Ryan-Foster Branching). Вместо ветвления на конкретном маршруте, алгоритм ищет две задачи (например, два авиарейса), которые в дробном решении покрываются вместе. Дерево ветвится на два логических сценария: 1) эти два рейса обязательно должны выполняться одним и тем же экипажем (слияние узлов графа во вспомогательной задаче); 2) эти два рейса строго запрещено выполнять одному экипажу (удаление ребра во вспомогательной задаче). Такие ограничения легко встраиваются в алгоритмы динамического программирования на графах, сохраняя эффективность генерации новых столбцов в каждом узле дерева ветвления.

Вычислительная мощь метода Branch-and-Price опирается на сильную нижнюю границу (Lower Bound), которую дает релаксация Данцига-Вулфа. Эта граница часто оказывается существенно плотнее (жестче), чем граница стандартной полиэдральной релаксации, что позволяет алгоритму отсекать гигантские ветви дерева на ранних стадиях. Интеграция метода B&P с добавлением отсекающих плоскостей (Cut Generation) породила класс алгоритмов Branch-Price-and-Cut, которые сегодня лежат в основе самых мощных в мире оптимизационных движков для управления глобальными цепями поставок.

Список литературы:
1. Barnhart C., Johnson E.L., Nemhauser G.L. et al. Branch-and-Price: Column Generation for Solving Huge Integer Programs. — Operations Research, 1998.
2. Desaulniers G., Desrosiers J., Solomon M.M. Column Generation. — Springer, 2005.
3. Wolsey L.A. Integer Programming. — Wiley, 1998.