1.割平面法
实际上，1958年由R.E.戈莫里提出割平面法之后，整数规划问题才形成规划问题的一个独立分支。整数规划割平面法的求解思路，是在不考虑决策变量整数约束的条件下，首先求得松弛问题的最优解，若得整数最优解，即为所求最优解。若不满足整数约束，则在松弛问题中逐次增加一个新约束，即割平面。整数规划问题的割平面是一个新引入的函数约束条件，可以在不减少整数规划问题可行解的情况下缩小松弛问题的可行域，即它能割去原松弛可行域中一块不含整数解的区域。逐次切割下去，直到切割最终所得松弛可行域的一个最优极点为整数解终止。
割平面法的具体步骤如下：
（1）求解整数规划问题对应的松弛问题，求得相应的最优解。
（2）若结果是无可行解或者取得了整数最优解，则无需继续计算，求解结束；否则求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解。
（3）若仍没有得到整数最优解，则继续作割平面方程，重复（2）步骤。
虽然整数规划问题的第一种求解算法就涉及割平面法，但在现实中，除了某些特定问题，它并不实用，因此割平面法的具体解法本章不做详细介绍，而将重点放在分支定界法。
2.分支定界法
分支定界法是上世纪60年代初，由Land Doig和Dakin提出的。在整数规划算法中，最常见、最传统的方法是使用分支定界法及其相关思想，通过枚举可行整数解。这种方法及其变形方法已经成功地应用于多种运筹学问题，在解决整数规划问题时尤其适用。 目前，分支定界法已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。
分支定界法是一种求解整数规划问题最常用的算法，求解思路是拆分排除法，将一些难以直接有效解决的复杂问题，拆分为越来越小的子问题，直到最终能有效处理这些子问题为止。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分支定界法形成分支、定界和剪支等三个环节。通过把整个可行解的集合分成越来越小的子集完成分支工作，剪支的工作通过界定子集中最好的解的程度后，舍弃其边界值，表明它不可能包含原问题最优解的子集完成。
分支定界法的主要思路是：首先，计算原问题目标函数值的初始上界和初始下界；其次，增加约束条件将原问题分支，分别求解一对分支；然后，修改上下界，最终结束准则。分支定界法实际上是一种隐枚举法，通过在枚举过程中逐步排斥一部分可行解，大大减少了不必要的工作量。分支定界法的关键之处在于分支和定界。分支定界法的一般步骤如下：
（1）放宽或取消原问题的某些约束条件，如求整数解的条件。若求出的最优解是原问题的可行解，即为原问题的最优解，计算结束。否则这个解的目标函数值是原问题的最优解的上界。
（2）将放宽了某些约束条件的替代问题分成若干子问题，要求各子问题的解集合的并集要包含原问题的所有可行解，然后对每个子问题求最优解。
（3）这些子问题的最优解中的最优者若是原问题的可行解，则得到原问题的最优解，计算结束。否则它的目标函数值就是原问题的一个新的上界。另外，各子问题的最优解中，若有原问题的可行解的，可行解的最大目标函数值，就是原问题最优解的一个下界。
（4）对最优解的目标函数值已经小于这个下界的问题，其可行解中必无原问题的最优解，可以放弃。对最优解的目标函数值大于下界的子问题，先保留下来，进入第（5）步。
（5）在保留下的所有子问题中，选出最优解的目标函数值最大的一个，重复（1）至（3）步骤。如果已经找到该子问题的最优可行解，那么其目标函数值与前面保留的其他问题在内的所有子问题的可行解中目标函数值最大者，将它作为新的下界，重复（4），直到求出最优解。
根据上述步骤，进行分支、定界与剪支，对于不断出现新的解进行判断，最终求得整数规划最优解。
例3-6利用分支定界法求解如下整数规划问题。
解：求解整数规划问题对应的松弛问题，最优单纯形表如表3-20所示。
表 3-20
对子问题Ⅰ和子问题Ⅱ相应的松弛问题进行求解，最优解结果见表3-21。
表 3-21最优结果
由子问题Ⅱ的整数解对应的目标函数值为22，可得整数规划问题新的下界；而子问题Ⅰ为非整数解，且目标函数值小于整数规划最优值的下界，因此被剪支，故求得最优解。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
