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

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

История

Метод ветвей и границ был впервые предложен в 1960 году Алисой Лэнд и Алисон Дойг для решения задач целочисленного линейного программирования. В 1963 году Дж. Д. К. Литтл, К. Г. Мурти, Д. У. Суини и К. Карел развили метод для решения задачи коммивояжёра. В СССР метод активно развивался в 1960–1970-х годах в работах В. С. Михалевича, В. В. Шкурбы и других математиков.

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

Основные принципы

Метод ветвей и границ основан на двух ключевых процедурах: ветвление и вычисление границ.

Ветвление

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

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

Вычисление границ

Для каждого подмножества вычисляется нижняя граница (для задачи минимизации) или верхняя граница (для задачи максимизации). Граница — это оценка оптимального значения целевой функции на данном подмножестве. Она должна быть:

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

Если нижняя граница подмножества превышает текущее лучшее найденное решение (рекорд), то это подмножество отсекается — оно заведомо не содержит оптимального решения.

Отсечение

Подмножество может быть отсечено в трёх случаях:

1. По границе — нижняя граница подмножества не меньше текущего рекорда.
2. По недопустимости — подмножество не содержит допустимых решений.
3. По оптимальности — подмножество состоит из одного решения, которое становится новым рекордом.

Алгоритм

Общая схема метода ветвей и границ для задачи минимизации:

1. Инициализация: установить рекорд R = +∞. Создать корневое подмножество S0 — всё множество допустимых решений. Поместить S0 в список активных подмножеств.
2. Выбор подмножества: извлечь подмножество S из списка активных.
3. Вычисление границы: вычислить нижнюю границу LB(S).
4. Проверка отсечения: если LB(S) >= R, перейти к шагу 2.
5. Ветвление: разбить S на подмножества S1, S2, ..., Sk.
6. Обновление рекорда: для каждого подмножества, если оно состоит из одного решения, вычислить значение целевой функции f. Если f < R, установить R = f.
7. Добавление подмножеств: поместить все подмножества, не отсечённые на шаге 4, в список активных.
8. Проверка завершения: если список активных пуст, завершить алгоритм. Иначе перейти к шагу 2.

Результат — значение R и соответствующее ему решение.

Применение

Метод ветвей и границ применяется для решения широкого круга задач:

Задача коммивояжёра

Классическая задача нахождения кратчайшего маршрута, проходящего через все заданные города ровно один раз. Метод ветвей и границ (алгоритм Литтла) позволяет находить точное решение для задач с числом городов до 50–100.

Задача о рюкзаке

Задача выбора предметов с максимальной суммарной стоимостью при ограничении на общий вес. Метод ветвей и границ используется как для булевой (0-1), так и для ограниченной задачи о рюкзаке.

Целочисленное линейное программирование

Метод ветвей и границ является основой большинства коммерческих и открытых решателей (солверов) для задач целочисленного линейного программирования, таких как CPLEX, Gurobi, SCIP. В этом контексте метод сочетается с симплекс-методом для вычисления границ.

Задачи теории расписаний

Метод применяется для построения оптимальных расписаний выполнения работ на станках, в вычислительных системах и производственных линиях.

Задачи размещения и упаковки

В задачах размещения объектов (например, заводов или складов) и упаковки предметов в контейнеры метод ветвей и границ позволяет находить оптимальные конфигурации.

Модификации и улучшения

Метод ветвей и отсечений (Branch and Cut)

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

Метод ветвей и цен (Branch and Price)

Применяется для задач с большим числом переменных. Вместо явного перечисления всех переменных используется генерация столбцов — добавление новых переменных по мере необходимости.

Параллельная реализация

Дерево ветвления может быть распараллелено: разные подмножества обрабатываются на разных вычислительных узлах. Это позволяет решать задачи с большим числом переменных за приемлемое время.

Ограничения и критика

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

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

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

Примеры

Пример 1: Задача о рюкзаке

Дано: 4 предмета, веса [2, 3, 4, 5], стоимости [3, 4, 5, 6], вместимость рюкзака 8. Метод ветвей и границ строит дерево, где на каждом шаге решается, брать или не брать предмет. Нижняя граница вычисляется как сумма стоимостей уже взятых предметов плюс оценка оставшихся (например, дробное решение задачи о рюкзаке). Оптимальное решение: предметы 1, 2 и 4 (вес 10, стоимость 13) или предметы 3 и 4 (вес 9, стоимость 11) — первое недопустимо по весу, второе допустимо. Фактический оптимум: предметы 2 и 3 (вес 7, стоимость 9).

Пример 2: Задача коммивояжёра (3 города)

Даны расстояния: A-B = 10, A-C = 15, B-C = 20. Метод ветвей и границ (алгоритм Литтла) вычисляет нижнюю границу как сумму минимальных элементов строк и столбцов матрицы расстояний после приведения. Ветвление происходит по выбору ребра. Оптимальный маршрут: A-B-C-A (длина 45).

Источники

1. Лэнд А., Дойг А. — «An Automatic Method of Solving Discrete Programming Problems» (1960).
2. Литтл Дж. Д. К., Мурти К. Г., Суини Д. У., Карел К. — «An Algorithm for the Traveling Salesman Problem» (1963).
3. Михалевич В. С., Шкурба В. В. — «Последовательные схемы оптимизации» (1965).
4. Пападимитриу Х., Стайглиц К. — «Комбинаторная оптимизация: алгоритмы и сложность» (1982).
5. Вольфсон М. А. — «Методы ветвей и границ в задачах дискретной оптимизации» (2000).