Методы ветвей и границ

Метод ветвей и границ (англ. Branch and Bound, сокр. B&B или BnB) — это общая парадигма построения точных алгоритмов для решения задач дискретной и комбинаторной оптимизации, в частности NP-трудных задач. Метод представляет собой стратегию направленного перебора, в которой всё множество допустимых решений последовательно разбивается на подмножества (ветвление), и для каждого из них вычисляются оценки (границы) значения целевой функции. Эти оценки позволяют отбрасывать (отсекать) те подмножества, которые заведомо не содержат оптимальных решений, что существенно сокращает пространство поиска.

Метод был впервые предложен А. Лэнд и А. Дойг в 1960 году для решения задач целочисленного программирования. С тех пор он стал одним из наиболее фундаментальных подходов в исследовании операций и компьютерных науках. Ключевая особенность метода — его гибкость: он является не конкретным алгоритмом, а высокоуровневой стратегической схемой (фреймворком), адаптивной к структуре решаемой задачи.

Ключевые компоненты метода

В основе метода лежат три фундаментальные операции, которые применяются к подмножествам пространства решений, организованным в виде дерева поиска.

• Ветвление (англ. Branching) — это процесс рекурсивного разделения текущего множества допустимых решений $S_i$ на несколько меньших, как правило, непересекающихся подмножеств $S_{i1},S_{i2},\dots ,S_{ik}$. Каждое такое подмножество соответствует новой подзадаче и представляется в виде дочернего узла в дереве поиска. Например, в задачах целочисленного программирования ветвление часто производят по переменной, имеющей дробное значение в решении ЛП-релаксации.

• Оценка границ (англ. Bounding) — для каждого узла дерева поиска (т.е. для каждой подзадачи) вычисляется оценка значения целевой функции. Для задачи минимизации это нижняя граница (lower bound), которая является гарантированной оценкой снизу для любого решения в данном подмножестве. Чаще всего эта оценка получается путём решения релаксации исходной подзадачи — упрощённой версии, в которой некоторые сложные ограничения (например, целочисленности) временно игнорируются. Наиболее распространённой является ЛП-релаксация.

• Отсечение (англ. Pruning) — это процесс исключения из рассмотрения узлов (и соответствующих им целых поддеревьев), которые заведомо не могут содержать оптимального решения. Узел отсекается в одном из следующих случаев:

1. Отсечение по границе: Нижняя граница для данного узла оказывается не лучше (т.е. больше или равна для задачи минимизации), чем значение лучшего на данный момент найденного допустимого решения, называемого рекордом (incumbent).
2. Отсечение по допустимости: Решение релаксации узла является допустимым для исходной задачи (например, все переменные целочисленны). Это решение сравнивается с текущим рекордом и, если оно лучше, рекорд обновляется. Дальнейшее ветвление из этого узла не требуется.
3. Отсечение по неразрешимости: Подзадача, соответствующая узлу, не имеет допустимых решений.

Общий алгоритм

Обобщённый алгоритм метода ветвей и границ для задачи минимизации можно описать следующими шагами:

1. Инициализация: Найти начальное допустимое решение (например, с помощью эвристики) и установить его значение как начальную верхнюю границу (рекорд) $U$. Создать очередь активных узлов $Q$, содержащую корневой узел (исходную задачу).
2. Основной цикл: Пока очередь $Q$ не пуста:
   • Выбрать узел из $Q$ в соответствии со стратегией поиска (например, поиск в глубину или по наилучшей оценке).
   • Решить релаксацию для этого узла, получив нижнюю границу $L$.
   • Отсечь узел, если $L\ge U$.
   • Если решение релаксации допустимо для исходной задачи, обновить рекорд: $U\leftarrow L$.
   • Если узел не отсечён и решение не является допустимым, выполнить ветвление, разделив его на дочерние узлы, и добавить их в очередь $Q$.
3. Завершение: Когда очередь $Q$ становится пустой, алгоритм завершается. Найденное решение, соответствующее рекорду $U$, является глобально оптимальным.

Ключевые свойства и теоремы

• Корректность и сходимость: Алгоритм гарантированно находит глобально оптимальное решение за конечное число шагов, если множество допустимых решений конечно, а процедура ветвления является конвергентной (то есть, при рекурсивном разбиении подмножества «стягиваются» к точкам).
• Стратегия поиска: Эффективность алгоритма сильно зависит от стратегии выбора следующего узла для ветвления (например, поиск в глубину, поиск в ширину, поиск по наилучшей оценке) и от выбора переменной для ветвления. Современные решатели часто используют гибридные стратегии.

Примеры

• Задача целочисленного программирования: Классическое приложение метода. В качестве релаксации используется линейное программирование. Ветвление происходит по дробной переменной $x_j$, создавая две подзадачи с дополнительными ограничениями $x_j\le \lfloor x_j^{*}\rfloor$ и $x_j\ge \lceil x_j^{*}\rceil$.
• Задача коммивояжёра: Пространство решений — все возможные гамильтоновы циклы в графе. Ветвление может осуществляться по рёбрам (включить/исключить ребро из маршрута). В качестве нижних границ могут использоваться решения более простых задач, таких как задача о назначениях или построение минимального остовного дерева.

Связанные понятия и применения

• Метод ветвей и отсечений (Branch-and-Cut): Гибридный метод, объединяющий B&B с методом отсекающих плоскостей. На каждом узле дерева поиска, помимо решения релаксации, генерируются дополнительные неравенства (отсечения), которые усиливают нижнюю границу, что приводит к более эффективному отсечению ветвей.
• Поиск с возвратом (Backtracking): Метод ветвей и границ можно рассматривать как обобщение этого алгоритма для задач оптимизации.
• Альфа-бета-отсечение: Концептуальная аналогия, используемая в игровых деревьях для отсечения заведомо проигрышных ветвей.

См. также

• Целочисленное программирование
• Комбинаторная оптимизация
• Задача коммивояжёра
• NP-трудная задача
• Симплекс-метод