В чём заключается суть метода ветвей и границ?

Суть метода ветвей и границ (англ. branch and bound) — нахождение оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. 12

Метод основан на систематическом перечислении кандидатов решения с отсечением подмножеств, не содержащих оптимального решения. 3

Метод включает две ключевые операции: 3

1. Ветвление. 13 Множество решений разбивается на подмножества меньших размеров. 13 Полученные подобласти образуют дерево поиска или дерево ветвей и границ. 1
2. Оценка границ. 3 Вычисляются верхние и нижние оценки целевой функции для каждого подмножества. 3

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

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

Метод используется для решения некоторых NP-полных задач, в том числе задачи коммивояжёра и задачи о ранце. 12