Cận LP relaxation cho branch-and-bound

Gọi $x \in \mathbb{Z}^n_{\ge 0}$ là tập khả thi nguyên và $x \in \mathbb{R}^n_{\ge 0}$ là tập khả thi (lớn hơn) của LP relaxation với cùng ràng buộc $Ax \le b$. Vì bỏ điều kiện nguyên chỉ loại bớt ràng buộc, mọi điểm khả thi nguyên cũng khả thi cho LP, nên tập khả thi nguyên là tập con của tập khả thi LP relaxation.

Vì cả hai bài toán tối đa hoá cùng một hàm mục tiêu tuyến tính $c^T x$ và tập khả thi của quy hoạch nguyên nằm trong tập khả thi của LP relaxation, giá trị tốt nhất đạt được trên tập con không thể vượt quá giá trị tốt nhất đạt được trên tập lớn hơn. Do đó giá trị tối ưu của LP relaxation là cận trên cho giá trị tối ưu của ILP.

Branch-and-bound xây một cây tìm kiếm bằng cách chọn một biến có giá trị phân số trong nghiệm LP relaxation hiện tại và tạo ra hai bài toán con thêm ràng buộc $x_1 \le 1$ hoặc $x_1 \ge 2$; mọi điểm khả thi nguyên thoả mãn đúng một trong hai điều kiện này, nên không có nghiệm nguyên nào bị mất qua phép chia này, và lặp lại phép chia tiếp tục phân hoạch không gian mà không để sót.

Tại mỗi nút, giải LP relaxation của bài toán con đó cho một cận trên cho mọi nghiệm nguyên còn có thể đạt tới bên dưới nó, theo cùng lập luận trên áp dụng cho tập ràng buộc nhỏ hơn. Nếu cận này không lớn hơn giá trị của nghiệm nguyên tốt nhất đã tìm được ở bất kỳ đâu trong cây, không nhánh con nào của nút này có thể cải thiện nghiệm tốt nhất hiện tại, nên toàn bộ nhánh con có thể bị cắt bỏ mà vẫn bảo đảm nghiệm tối ưu thật sự được tìm thấy ở nơi khác trong cây.