Skip to content
Назад к результатам поиска

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

Автор метода
Ailsa Land & Alison Doig
Год
1960
Тип
Exact combinatorial optimization algorithm
Семейство
Mathematical programming

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Метод ветвей и границ — это систематический точный алгоритм для решения комбинаторных задач и задач целочисленного программирования, представленный Элисой Лэнд и Элисон Дуиг в 1960 году.

Он организует пространство поиска в виде дерева подзадач, использует верхние границы, полученные из релаксаций, для отсечения ветвей, которые не могут улучшить наилучшее известное решение, и гарантирует нахождение глобально оптимального целочисленного решения. Это основа современных решателей задач смешанного целочисленного программирования, используемых в исследовании операций, логистике, планировании и проектировании.

Интуиция метода

Представьте, что вы ищете предмет наивысшей ценности, спрятанный в огромном лабиринте комнат. Вместо того чтобы проверять каждую комнату, вы оцениваете максимальную возможную ценность, которую можно достичь из каждого коридора, прежде чем войти в него. Если этот потолок ниже лучшего предмета, который у вас уже есть, вы пропускаете весь коридор, не заглядывая внутрь. Метод ветвей и границ работает так же: он разбивает задачу на более мелкие части, вычисляет оптимистичные верхние границы для каждой части и немедленно отбрасывает любую часть, которая заведомо не может превзойти текущее лучшее решение.

История

Лэнд и Дуиг опубликовали основополагающую статью по методу ветвей и границ в журнале Econometrica в 1960 году, представив его как автоматический метод для дискретного программирования. Литтл и др. (1963) применили этот метод к задаче коммивояжера, укрепив его роль в комбинаторной оптимизации. Дакен (1965) представил ветвление на основе ЛП-релаксации, форму, наиболее часто используемую сегодня. В последующие десятилетия произошло внедрение разрезающих плоскостей (ветвей и плоскостей) и генерации столбцов (ветвей и генерации столбцов), что сделало метод ветвей и границ движущей силой всех основных коммерческих решателей задач целочисленного программирования.

Когда применять

Используйте метод ветвей и границ, когда вам необходимо найти доказуемо оптимальное решение для задачи смешанного или чисто целочисленного линейного программирования и вы не можете принять приближенный ответ. Он предполагает, что задачу можно сформулировать с линейными (или выпуклыми) релаксациями, которые дают полезные границы. Он менее подходит для очень больших экземпляров, где дерево перебора разрастается экспоненциально, для нелинейных целочисленных задач без точных релаксаций или для приложений реального времени, где время вычислений строго ограничено. В таких случаях могут быть предпочтительны эвристики или метаэвристики.

Ограничения и замечания

  • Сложность в худшем случае экспоненциальна; на плохо структурированных экземплярах дерево может вырасти до непомерно больших размеров.
  • Производительность сильно зависит от выбора переменной ветвления и стратегии выбора узла.
  • Требует разрешимой релаксации, которая дает значимые верхние границы; слабые границы приводят к минимальному отсечению.
  • Требования к памяти могут быть существенными, когда одновременно необходимо хранить много открытых узлов.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Гарантирует глобальную оптимальность для целочисленных и комбинаторных задач.
  • Драматически сокращает поиск за счет отсечения на основе границ — часто исследуется лишь крошечная доля полного дерева перебора.
  • Гибкость: может включать разрезающие плоскости (ветвей и плоскостей) или эвристические границы (ветвей и генерации столбцов) для дальнейшего повышения эффективности.
  • Широко реализован в зрелых коммерческих решателях (CPLEX, Gurobi) и инструментах с открытым исходным кодом (GLPK, CBC).

Применение

  • Планирование экипажей авиакомпаний и распределение парка воздушных судов в исследовании операций.
  • Проектирование сетей цепочек поставок и задачи размещения объектов.
  • Разводка печатных плат и распределение регистров в компьютерной инженерии.
  • Предсказание структуры белков и сборка генома в вычислительной биологии.
  • Оптимизация финансовых портфелей с ограничениями на количество активов.

Как это работает

Как это работает

1

Алгоритм начинается с решения релаксированной версии задачи — как правило, ЛП-релаксации — которая игнорирует ограничения целочисленности. Эта релаксация дает верхнюю границу истинного оптимального значения, поскольку каждое допустимое целочисленное решение также допустимо в релаксации. Если релаксированное решение случайно оказывается целочисленным, задача решается немедленно.

Формула
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}
2

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

Формула
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
3

Каждый активный узел получает свою собственную границу ЛП-релаксации. Узел, граница которого не превышает наилучшее найденное на данный момент целочисленное решение — называемое инкумбентом — не может содержать лучшего решения, поэтому он отсекается. Точные границы имеют решающее значение: чем точнее граница, тем меньше узлов необходимо исследовать.

Формула
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}
4

Узел считается исчерпанным (окончательно закрытым) при трех условиях: его релаксация недопустима, его граница не лучше инкумбента, или его релаксированное решение уже целочисленно допустимо. В последнем случае инкумбент обновляется, если новое решение его улучшает. Алгоритм завершается, когда все узлы исчерпаны, и в этот момент инкумбент является глобальным оптимумом.

Формула
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)

Частые ошибки

  • Неправильный выбор переменной ветвления (например, всегда ветвление по первой дробной переменной) часто приводит к глубоким, несбалансированным деревьям и медленной сходимости.
  • Игнорирование допустимых неравенств (разрезающих плоскостей) означает упущение возможности значительно уточнить границы релаксации.
  • Преждевременное завершение с зазором субоптимальности, который не сообщается как таковой, может ввести практиков в заблуждение, заставляя рассматривать почти оптимальное решение как точное.
  • Применение метода ветвей и границ к нелинейным или невыпуклым релаксациям без специализированной выпуклой аппроксимации может привести к недопустимым границам и неверным результатам.

Часто задаваемые вопросы

Чем метод ветвей и границ отличается от полного перебора?

Полный перебор явно оценивает каждое допустимое целочисленное решение, что вычислительно неосуществимо для больших задач. Метод ветвей и границ избегает этого, вычисляя верхние границы на основе релаксаций в каждом узле дерева поиска и отсекая целые поддеревья всякий раз, когда граница не может превысить лучшее уже найденное решение. На практике исследуется лишь небольшая часть дерева.

Какова роль ЛП-релаксации в методе ветвей и границ?

ЛП-релаксация отбрасывает ограничения целочисленности, делая задачу решаемой за полиномиальное время с помощью симплекс-метода или метода внутренних точек. Ее оптимальное значение служит верхней границей для соответствующей целочисленной подзадачи. Когда эта граница точна — близка к истинному целочисленному оптимуму — требуется исследовать меньше ветвей. Более точные релаксации, часто достигаемые путем добавления допустимых неравенств, значительно ускоряют общий алгоритм.

Когда следует использовать метод ветвей и границ вместо метаэвристик, таких как генетические алгоритмы?

Выбирайте метод ветвей и границ, когда вам требуется сертификат оптимальности и вы можете позволить себе время вычислений. Он идеально подходит для задач среднего размера с хорошо структурированными ЛП-релаксациями. Метаэвристики предпочтительнее, когда задача чрезвычайно велика, не имеет полезной релаксации или должна быть решена в сжатые сроки, когда допустимо почти оптимальное решение. Многие практики комбинируют оба подхода: используют метод ветвей и границ с допустимым зазором для раннего завершения.

Похожие методы

Источники

  1. Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.

    Открыть ссылку DOI
    Скопировано.