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

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