Branch and Bound

Branch and Bound er en systematisk eksakt algoritme for kombinatoriske og heltallige optimeringsproblemer, introdusert av Ailsa Land og Alison Doig i 1960. Den organiserer søkerommet som et tre av delproblemer, bruker øvre grenser utledet fra relaksasjoner for å beskjære grener som ikke kan forbedre den beste kjente løsningen, og garanterer å finne en globalt optimal heltallsløsning. Den er ryggraden i moderne mixed-integer programming-løsere brukt innen operasjonsanalyse, logistikk, planlegging og ingeniørdesign.