分支定界法

設最大化的整數規劃問題為A, 相應的不含整數約束的線性規劃為B, 若B 的最優解不符合A 的整數條件, 那麼B 的最優目標函數值必為A 的最優目標函數值Z* 的一個上界, 記作Z; 而A 的任意可行解的目標函數值將是Z* 的一個下界, 記作Z。對B 的非整數解的相鄰整數作附加條件, 從而形成兩個分枝, 即兩個子問題, 兩個子問題的可行域中包含原整數規劃問題的所有可行解。不斷分枝, 逐步減小Z, 增大Z, 最終求得Z* 。

第1步：放寬或取消原問題的某些約束條件，如求 整數解的條件。如果這時求出的最優解是原問題的 可行解，那麼這個解就是原問題的最優解，計算結束。否則這個解的目標函數值是原問題的最優解的上界。

第2步：將放寬了某些約束條件的替代問題分成若干子問題，要求各子問題的解集合的並集要包含原問題的所有 可行解，然後對每個子問題求 最優解。這些子問題的 最優解中的最優者若是原問題的 可行解，則它就是原問題的 最優解，計算結束。否則它的目標函數值就是原問題的一個新的上界。另外，各子問題的最優解中，若有原問題的 可行解的，選這些可行解的最大目標函數值，它就是原問題的最優解的一個下界。

第3步：對 最優解的 目標函數值已小於這個下界的子問題，其 可行解中必無原問題的最優解，可以放棄。對最優解（不是原問題的可行解）的目標函數值大於這個下界的子問題，都先保留下來，進入第4步。

第4步：在保留下的所有子問題中，選出 最優解的 目標函數值最大的一個，重複第1步和第2步。如果已經找到該子問題的最優 可行解，那麼其目標函數值與前面保留的其他問題在內的所有子問題的可行解中目標函數值最大者，將它作為新的下界，重複第3步，直到求出最優解。