Метод на разклонение и граница

Методът на разклонение и граница (Branch and Bound) е систематичен точен алгоритъм за комбинаторни и целочислени оптимизационни задачи, въведен от Ailsa Land и Alison Doig през 1960 г. Той организира пространството за търсене като дърво от подзадачи, използва горни граници, изведени чрез релаксация, за да отрязва клони, които не могат да подобрят най-доброто известно решение, и гарантира намирането на глобално оптимално целочислено решение. Той е гръбнакът на съвременните решаващи програми за смесено целочислено програмиране, използвани в изследването на операциите, логистиката, планирането и инженерния дизайн.