分支定界法是一种广义搜索算法，人工使用非常繁琐，但由于计算机的运算速度快的特点，这种算法十分适合计算机进行。分支定界法是计算机最擅长的广义搜索穷举算法。
基本思想：
1. 松弛模型的最优解要优于其相应的整数规划的解 由于松弛模型可行解的区域（多边形）包含了对应的整数规划的可行解的集合（多边形内的整数点），因而松弛模型的解要优于整数规划的解。这就是说，如果问题是求最大值的，则松弛模型最优解对应的目标函数值必大于或等于整数规划最优解对应的目标函数值；如果问题是求最小值的，则松弛模型的最优解对应的目标函数值必小于或等于整数规划最优解对应的目标函数值。由此可以推出：
2. 松弛模型的最优解如果是整数解，则必然也是整数规划的最优解。
3. 松弛模型的最优解如果不是整数解，则如果问题是求最大值的，松弛模型最优解的目标函数值是整数规划最优解目标函数值的一个上界；如果问题是求最小值的，则松弛模型最优解的目标函数值是整数规划最优解目标函数值的一个下界。
我们用例子来说明用分支定界法求解整数规划的步骤。 例 求下面整数规划的最优解
maxZ=40x1+90x2
s.t. 9x1+7x2≤56 7x1+20x2≤70 x1,x2≥0 x1,x2为整数
解 从上述各约束条件可见，(0,0)是一个可行解，对应的松弛模型目标函数值Z=0。本问题是一个求最大值的问题，因而整数规划最优解的目标函数的下界可以取为0，即取整数规划模型最优值的下界Z=0。
先考虑此整数规划问题的线性松弛模型0： 其解为
松弛模型0
Z0=356x1=4.81 x2=1.82
由于松弛模型解的目标函数值是整数规划模型最优值的一个上界，可以取此处的Z0为整数规划模型最优值的一个上界Z=356。由于该松弛模型解不是整数解，分原问题为x1≤4和x1≥5两个子模型：子模型1和子模型2。
1
子模型1
x1≤4
子模型2
x1≥5
Z1=349x1=4.00 x2=2.10
子模型1的形式：
Z2=349x1=5.00 x2=1.57
maxZ=40x1+90x2s.t. 9x1+7x2≤56 7x1+20x2≤70 x1≤4 x1,x2≥0
子模型2的形式：
maxZ=40x1+90x2s.t. 9x1+7x2≤56 7x1+20x2≤70 x1≥5 x1,x2≥0
所求整数规划模型的最优值不会超过这两个子模型的最优值中大的那个，即
349。这个值小于原来的上界Z=356，因而可以改取整数规划模型最优值的上界为Z=349。
由于子模型1和子模型2的解中x2都不是整数，我们按x2最接近的整数分别分解子模型1为子模型3、子模型4；分解子模型2为子模型5、子模型6（具体形式略）。分别求解，得
子模型3 子模型4 子模型5 子模型6
x2≤2
x2≥3
x2≤1
x2≥2
Z3=340x1=4.00 x2=2.00
Z4=327x1=1.42 x2=3.00
Z5=308x1=5.44 x2=1.00
无可行解
因为子模型3有整数解，因而所求整数规划的最优值不会比这个值更差。我们可以改记目标函数值的下界为Z=340。子模型4、子模型5在不考虑整数的
2
情况下最优（大）值都小于340，在整数约束下的最优值更要小于340，所以尽管这两个子模型的解不是整数，我们也不再继续分支，即剪去这两支。子模型6无解。因而最优解就是x1=4, x2=2，对应的最优值为Z=340。
我们把上述应用分支定界法求解整数规划的过程用下面的图表示出来：
3
因篇幅问题不能全部显示，请点此查看更多更全内容