Если оценка некоторого подмножества больше имеющегося рекорда, то среди точек данного подмножества нет оптимальных точек (решения задачи)
Это утверждение позволяет сформулировать основное правило сокращения перебора: если оценка множества больше рекордного значения, то такое множество вариантов выбрасывается из дальнейшего рассмотрения. Отметим, что множество может не подвергаться последующему ветвлению и по другим причинам:
- если при решении оценочной задачи на данном множестве была получена точка, являющаяся допустимой в исходной задаче;
- если допустимое множество оценочной задачи пусто.
5. Работа метода останавливается в соответствии с критерием оптимальности: оценки всех подмножеств не меньше имеющегося рекорда.
Таким образом,признаком останова является следующая ситуация: не осталось ни одного перспективного множества, которое может быть подвергнуто последующему ветвлению. Решением при этом является точка, в которой получено последнее рекордное значение.
В представленных выше пяти пунктах описаны основные модули, с помощью которых может быть составлена схема работы любого варианта метода ветвей и границ.
Каждый конкретный алгоритмический вариант требует индивидуального «наполнения» всех модулей применительно к решаемой задаче.
Алгоритмическая схема метода
Решается задача вида: 
.
Шаг 1. Инициализация.
Задать начальное рекордное значение R. Если отыскание начального рекорда затруднительно, положить 
Положить 
– множество номеров подмножеств, подлежащих ветвлению, 
— множество номеров подмножеств, для которых будут решаться оценочные задачи.
Шаг 2.Вычисление оценок.
Решить оценочные задачи для множеств 
где 
. Вычислить 
Шаг 3.Обновление рекорда.
Если на шаге 2 получены допустимые точки 
, то положить R= 
.
Шаг 4. Сокращение перебора.
Осуществить закрытие неперспективных множеств (включая те номера 
, для которых 
). Удалить их номера из множеств I и J. Положить 
, 
. Если , то перейти к шагу 7.
Шаг 5.Реализация стратегии.
Выбрать из множества I номер k – индекс подмножества 
, подлежащего ветвлению на данном этапе в соответствии с зафиксированным правилом.
Шаг 6.Ветвление.
Осуществить разбиение множества на подмножества 
. Положить 
. Перейти к шагу 2.
Шаг 7.Останов, 
.
Заметим, что такая последовательность шагов может быть не рациональной в случае, если при вычислении оценок заведомо не могут появиться допустимые точки (например, при решении задачи коммивояжера).
УПРАЖНЕНИЯ
1. Докажите свойство монотонности оценок в условиях, при которых ветвление и составление оценочных задач осуществляется по правилам, указанным в п.п. 1 и 2 описания основных модулей.
2. Предложите другие стратегии обхода дерева вариантов.
3. Докажите, что при использовании основного правила отбрасывания неперспективных множеств (п.4) не происходит потери решения.
4. В предложенной алгоритмической схеме отыскивается одно решение, даже если оно в задаче не единственно. Где происходит потеря других решений? Исправьте алгоритм таким образом, чтобы появилась возможность отыскания всех решений задачи.