運籌學(xué)分支定界法

分支定界法（branch and bound）是一種求解整數(shù)規(guī)劃問題的最常用算法。這種方法不但可以求解純整數(shù)規(guī)劃，還可以求解混合整數(shù)規(guī)劃問題。分支定界法是一種搜索與迭代的方法，選擇不同的分支變量和子問題進行分支。

對于兩個變量的整數(shù)規(guī)劃問題，使用網(wǎng)格的方法有時更為簡單。

通常，把全部可行解空間反復(fù)地分割為越來越小的子集，稱為分支；并且對每個子集內(nèi)的解集計算一個目標下界（對于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解集目標值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。