22. Особенности задач целочисленного программирования методом ветвей и границ

Вычисление верхней (нижней) границы (оценки). Вычисляется верхняя (нижняя) граница (оценка) целевой функции на множестве допустимых планов D.

Разбиение на подмножества (ветвление). Данная процедура связана с разбиением множества планов D на дерево подмножеств.

Пересчет оценок (вычисление целевой функции на выделенных подмножествах). Если целочисленный оптимальный план не найден, то отбрасываются неперспективные варианты допустимых планов, а перспективные подмножества подлежат дальнейшему ветвлению.

Особенности метода ветвей и границ.

1. Алгоритмы, реализующие метод ветвей и границ, должны адаптироваться к конкретной задаче.

2. При построении алгоритмов ключевыми вопросами являются: нахождение оценок верхней (нижней) границы; определение правил выхода из тупиковых ветвей.