要求一部分或全部决策变量必须取整数值的规划问题称为整数规划（integer programming，简记IP）。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题（slack problem）。若松弛问题是一个线性规划，则称该整数规划为整数线性规划（integer linear programming）。

要求一部分或全部决策变量必须取整数值的规划问题称为整数规划（integerprogramming，简记IP）。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题（slackproblem）。若松弛问题是一个线性规划，则称该整数规划为整数线性规划（integerlinear programming）。

不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。

相关结论：

（1）最优解不一定在顶点上达到；

（2）最优解不一定是松弛问题最优解的邻近整数解；

（3）整数可行解远多余于顶点，枚举法不可取。

设有最大化的整数规划问题A，与它相应的线性规划问题为B，求解问题B，若B的最优解不符合A的整数条件，则B的最优值一定为A最优值Z*的上界，而A的任意可行解的目标函数值将是Z*的下界，分支定界法就是将B的可行域分成子区域（称为分支方法）的方法，通过减小最优值的上界和下界最终得到最优值。

分枝定界法求解问题的步骤：

将要求解的整数规划问题称为问题A，将其松弛问题称为问题B，若

（1）B没有可行解，这时A也没有可行解，停止；

（2）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解；

（3）B有最优解，但不符合A的整数条件，记它目标函数值为最优值上界。

松弛问题作为一个线性规划问题，其可行解的集合是一个凸集，任意两个可行解的凸组合仍为可行解。

整数规划问题的可行解是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。由于整数规划问题的可行解一定也是它的松弛问题的可行解（反之则不一定），所以，前者最优解的目标函数值不会优于后者最优解的目标函数值，即松弛问题的最优解是整数规划问题最优解的上限。

在一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解。此时，若对松弛问题的这个最优解中不符合整数要求的分量简单地取整，所得到的解不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解。

1、在全部可行性域上解松弛问题

若松弛问题最优解为整数解，则其也是整数规划的最优解；

2、分枝过程

（1）若松弛问题最优解中某个不是整数，令为的整数部分

（2）构造两个新的约束条件和，分别加于原松弛问题，形成两个新的整数规划；

3、求解分枝的松弛问题 — 定界过程

设两个分枝的松弛问题分别为问题1和问题2，它们的最优解有如下情况：

情况 2, 4, 5 找到最优解；

情况 3 在缩减的域上继续分枝定界法；

情况 6 问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况 4 或 5。

计算过程可利用灵敏度分析（增加约束条件），简化问题的计算量。

试用分枝定界法求解下面整数规划问题的解：

解：松弛问题的最优解为，由得到两个分枝如下：

问题1：

问题2：

分枝问题的松弛解：

如图1所示，则该整数规划松弛问题的解为：

若继续为原问题增加两个条件：；

则