分支定界法(branch and bound)是一種用於求解整數規劃問題的重要算法，它可以有效處理純整數規劃和混合整數規劃問題。以下是關於分支定界法的詳細介紹：
基本原理。分支定界法通過將原問題分解為多個子問題來工作，這個過程包括分支和定界兩個主要步驟。在分支步驟中，原問題被不斷地細分為若幹個子問題，形成搜尋樹；而定界步驟則涉及為這些子問題確定上下界，以剪枝搜尋空間，即排除無法提供最優解的子問題。這種方法特別適用於具有離散變數的問題，在物流管理、調度最佳化、機器學習等多個領域都有廣泛套用。
特點。分支定界法的優點在於能夠高效地在大型搜尋空間中尋找最優解，特別是在實時性問題上表現出色。其缺點是當搜尋空間過於複雜時，剪枝效果可能不佳，導致計算效率下降。
搜尋策略。分支定界法採用廣度優先或最小耗費優先的方法搜尋解空間樹，確保每個節點只有一次機會成為擴展節點。在選擇下一個擴展節點時，可以採用FIFO（先進先出）策略或基於耗費/收益的策略。
實際套用。在實現分支定界法時，需要定義問題對象，設定分支策略，設計剪枝策略，並使用回溯算法進行搜尋。Python等程式語言被廣泛套用於實現分支定界法，用於解決各種最佳化問題。