分枝定界法
對有限制條件的最優化問題（其可行解為有限數）的所有可行解空間恰當地進行系統搜尋，這就是分枝與定界内容。通常，把全部可行解空間反複地分割為越來越小的子集，稱為分枝；并且對每個子集内的解集計算一個目标下界（對于最小值問題），這稱為定界。在每次分枝後，凡是界限超出已知可行解集目标值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。
分枝定界法可用于解純整數或混合的整數規劃問題。在本世紀六十年代初由 LandDoig 和Dakin 等人提出的。由于這方法靈活且便于用計算機求解，是以現在它已是解整數規劃的重要方法。目前已成功地應用于求解生産進度問題、旅行推銷員問題、工廠選址問題、背包問題及配置設定問題等。
基本思想：設有最大化的整數規劃問題 A ，與它相應的線性規劃為問題B ，從解問題B 開始，若其最優解不符合 A的整數條件，那麼B的最優目标函數必是 A的最優目标函數z*的上界，記作z上 ；而 A的任意可行解的目标函數值将是z*的一個下界z下。分枝定界法就是将B的可行域分成子區域的方法。逐漸減小z 上和增大z下 ，最終求到z*。
整數規劃例題
用分枝定界法求解整數規劃（最大化）問題的步驟為：首先，将要求解的整數規劃問題稱為問題 A ，将與它相應的線性規劃問題稱為問題B 。
1、求解下述整數規劃
(1)、先利用LP思路求出最優解
(2)、利用IP思路分析解，先對x1進行分枝、定界
(3)、先對B1進行分枝、定界
(4)、還要對B2進行分枝、定界