分支定界法

---

是一种对整数线性规划求解的方法。

求解整数规划很容易想到的方法是枚举法，即将所有可行的整数点都找出来，比较它们的目标函数值以定出最优解。但这只能对小型问题而言，稍微大一点的问题，枚举法就不现实了。

分支定界法是采用这样的方式求解，它从求解相应线性规划出发，如果最优解不符合整数条件，就将相应线性规划的可行域分成几个部分，每个部分都增加了约束条件，因此可行域便缩小了。然后对缩小了的可行域进行观察，对建立在这些可行域上的整数规划问题作出评价。

在划分、评价过程中要随时考虑到两种性质。第一，(对求极大值问题)任何整数线性规划最优解的目标函数均小于或等于其相应线性规划最优解的目标函数值。这性质的意义是，任何整数线性规划的最优解目标函数，都可以通过求解其相应的线性规划得到一个上界。第二，(对求极小值问题)任何整数线性规划最优解的目标函数，均大于或等于其相应线性规划最优解的目标函数值。

这就是说，极小问题的整数线性规划最优解目标函数，可以通过求解相应的线性规划得到一个下界。另外，还应考虑到任何整数可行点的目标函数值，总是原问题目标函数最优值的下界(设问题为求极大值)。

分支定界法可以用于求解纯整数规划，也可用于求解混合整数线性规划。这种方法目前应用很广，几乎所有商业上应用的整数规划计算机程序都有分支定界法。