Branch and Bound

Branch and Bound er en systematisk eksakt algoritme til kombinatoriske og heltalsoptimeringsproblemer, introduceret af Ailsa Land og Alison Doig i 1960. Den organiserer søgerummet som et træ af delproblemer, bruger afslapningsafledte øvre grænser til at beskære grene, der ikke kan forbedre den bedst kendte løsning, og garanterer at finde en globalt optimal heltalsløsning. Den er rygraden i moderne mixed-integer programming-løsere, der anvendes inden for operationsanalyse, logistik, planlægning og ingeniørdesign.