0-1整数规划与隐枚举法-感受剪枝的魅⼒
整数规划是线性规划的特殊情况，即当约束条件是变量为整数时，线性规划就变成了整数规划。若要求所有变量都为整数，即为纯整数规划；若允许存在⼀部分变量不⼀定为整数，则称为混合整数规划。⽽本⽂要讨论的0-1整数规划则是纯整数规划的特殊情况，即所有变量要么等于0，要么等于1，故这种变量⼜成为逻辑变量。 0-1整数规划在⽣活中还是很常见的，通常可以总结为“是”“否”问题。例如，有n个产品销地x1,...,xn可供选择，为使得利润最⼤，那么每⼀个销地都⾯临是否选择的问题，通常还会有⼀些限制条件，由于销地xi与销地xj距离较近，所以规定若选择xi就不能选择xj等。那么如何求解0-1规划问题？最朴素的⽅法是枚举，即将所有销地是否被选择的情况都考虑，那么就是从{0, ... ,0}枚举到{1, ... ,1}，需要2的n次⽅的枚举次数。显然，当n较⼤时，这种⽅式的效率就⾮常低。本⽂要介绍的隐枚举法就可以提⾼求解出最优解的效率。 贵阳医学院学报所谓隐枚举法，从字⾯上理解，就是隐去⼀些不需要枚举的情况，下⾯从⼀个例⼦出发，来给出隐枚举法的步骤。
【例】求解下列规划问题
max z = 8*x1 + 2*x2 - 4*x3 - 7*x4 - 5*x5;
<{
3*x1 + 3*x2 + x3 + 2*x4 + 3*x5 <= 4
5*x1 + 3*x2 - 2*x3 - x4 + x5 <= 4
安南将军 xi = 0或1，i = 1, ..., 5
}
1. 预处理
⾸先需要对原问题进⾏预处理，⾄于为什么后⽂将会解释。预处理的步骤如下：
1) 将⽬标函数统⼀为求最⼩值，即"min", 同时将约束条件都化为">="。 若原约束条件为"<="，则不等式左右同乘-1;
若原约束条件为"Ai * X = bi"，则化为"Ai * X >= bi" 和 "-Ai * X >= -bi"，其中Ai为系数⾏向量，X为变量列向量。
min z' = -8*x1 - 2*x2 + 4*x3 + 7*x4 + 5*x5;
安徽省化工研究院
<{
-3*x1 - 3*x2 - x3 - 2*x4 - 3*x5 >= 4
-5*x1 - 3*x2 + 2*x3 + x4 - x5 >= 4
xi = 0或1，i = 1, ..., 5
}
2) 将⽬标函数中系数为负的变量xi化为系数为正的变量xi'，其中 xi = 1 - xi’ （若xi = 0 则 xi' = 1; 若xi = 1则xi' = 0）。
故针对本问题，在⽬标函数中x1和x2前的系数为负，故令x1 = 1 -x1', x2 = 1 - x2'，代⼊1)中化简得
min z' = 8*x1' + 2*x2' + 4*x3 + 7*x4 + 5*x5 - 10;
<{
3*x1' + 3*x2' - x3 - 2*x4 - 3*x5 >= 2
5*x1' + 3*x2' + 2*x3 + x4 - x5 >= 4
快乐语文网站 xi或xi' = 0或1，i = 1, ..., 5
}
3) 重新排列变量在⽬标函数和约束条件的先后顺序，使其在⽬标函数中的系数递增。
min z' = 2*x2' + 4*x3 + 5*x5 + 7*x4 + 8*x1' - 10;
<{
3*x2' - x3 - 3*x5 - 2*x4 + 3*x1' >= 2 (a)
3*x2' + 2*x3 - x5 + x4 + 5*x1' >= 4 (b)
xi或xi' = 0或1，i = 1, ..., 5
潘金莲之前世今生诱僧
}
2. 隐枚举
隐枚举的思想是⾸先枚举到⼀个可⾏解，并得到⽬标函数值z0，之后的枚举若⽬标函数值没有z0优，那么就⼀定不是最优解。
现在说明预处理的作⽤：
预处理使得⽬标函数是求最⼩值，变量的系数都为正且由⼩到⼤排列，所以有如下规律：
从xi = 0开始枚举是使⽬标函数最优的，此时得到的函数值也就是最优解的下界；
只要按照⽬标函数中变量的顺序枚举也就是⼆进制数位从⼩到⼤（0...0到1...1）就能尽量较早的枚举出使得⽬标函数取最⼩值（最优值）的可⾏解z0。若解形如0..1的⽬标函数z1取值⼤于已得到的可⾏解，那么只要是以xj...x1结尾和只将xj...x1中某些位由0变为1的解的⽬标函数取值⼀定⼤于z1，当然也就⼤于z0，故⼀定不会是最优解，可以直接剪枝，即不考虑上述两种情况，直接按照⼆进制数码顺序枚举其他形式。
隐枚举步骤如下：
(1) 先忽略除" xi或xi' = 0或1 "以外的约束条件，从xi = 0也就是0...0开始枚举。
(2) 计算出枚举出的⽬标函数值。
若⼩于已有可⾏解的函数值，或者还⽆可⾏解，则执⾏(3)；
若⼤于已有可⾏解的函数值，剪枝，再进⾏枚举。
(3) 检查枚举的解是否满⾜除去的约束条件。（只要检查出⼀个约束条件不满⾜就⽆需再检查）
若不满⾜，则此时的枚举值不是可⾏解，继续枚举;
若满⾜，则更新可⾏解和⽬标函数值z0。可⾏解0..1（前⾯'0'的个数可能为0），那么只要是以xj...x1结尾和只将xj...x1中某些位由0变为1的解的⽬标函数取值⼀定⼤于z0，剪枝，再进⾏枚举。
对于本问题，从xi = 0 (i = 1到5)开始枚举，得到z' = -10，所以-10便是最优解的下界（所以10便是原问题的上界）。枚举过程列表如下（'-'代表没有判断）：
x1' x4 x5 x3 x2' z' 是否(Y/N)满⾜约束条件
(a) (b)
是否(Y/N)为可⾏解
0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 -10
-8
-6
-4
N -
Y N
N -
Y Y
N
N
N
Y 剪枝
0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 -5
-3
-1
-3
2
N -
中国中医急症
函数值-3⼤于已知可⾏解的函数值-4,⼀定不会是最优解
-1 > -4
-3 > -4
2 > -4
N
⽆需判断约束条件，该分⽀也⽆需再枚举，即剪枝
同上
同上
同上
由表可以看出，我们在第4次枚举得到了⼀个较优的可⾏解，其⽬标函数值z0 = -4，之后的枚举要么是不满⾜约束条件，要么是函数值⼤于-4，剪枝。最后我们只枚举了9次就完成了整个过程（⽐直接枚举的2^5 = 32次快了很多），得到最优解为{0，0，0，1，1}，min z' = -4，将其还原成原问题，最优解为{1, 0, 1, 0, 0}，max z = 4.
总结：
在解决很多问题的时候，枚举（搜索）似乎是⼀种直接了当的⽅式。但是，当解空间较⼤时，枚举的效率可能就很低，⽆法达到⽬的。此时，不妨想想是否在枚举过程中有⼀些解可以在枚举之前就判断它⼀定不满⾜要求，直接不考虑它们（剪枝），这样就可以缩⼩解空间，提⾼效率。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议