Branch and Bound

Branch and Bound là một thuật toán chính xác có hệ thống cho các bài toán tối ưu tổ hợp và nguyên, được giới thiệu bởi Ailsa Land và Alison Doig vào năm 1960. Thuật toán này tổ chức không gian tìm kiếm dưới dạng một cây các bài toán con, sử dụng các cận trên có nguồn gốc từ phép nới lỏng để cắt tỉa các nhánh không thể cải thiện giải pháp tốt nhất đã biết, và đảm bảo tìm thấy một nghiệm nguyên tối ưu toàn cục. Nó là xương sống của các bộ giải bài toán quy hoạch tuyến tính hỗn hợp nguyên hiện đại được sử dụng trong nghiên cứu vận hành, logistics, lập lịch và thiết kế kỹ thuật.