分枝定界法
对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。
分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 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进行分枝、定界
