0-1整数规划与隐枚举法-感受剪枝的魅力

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; s.t.{   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; s.t.{   -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; s.t.{   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; s.t.{   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..0xj...x1的目标函数z1取值大于已得到的可行解,那么只要是以xj...x1结尾只将xj...x1中某些位由0变为1的解的目标函数取值一定大于z1,当然也就大于z0,故一定不会是最优解,可以直接剪枝,即不考虑上述两种情况,直接按照二进制数码顺序枚举其他形式。

隐枚举步骤如下:

(1) 先忽略除" xi或xi' = 0或1 "以外的约束条件,从xi = 0也就是0...0开始枚举。

(2) 计算出枚举出的目标函数值。

  • 若小于已有可行解的函数值,或者还无可行解,则执行(3);
  • 若大于已有可行解的函数值,剪枝,再进行枚举。

(3) 检查枚举的解是否满足除去的约束条件。(只要检查出一个约束条件不满足就无需再检查)

  • 若不满足,则此时的枚举值不是可行解,继续枚举;
  • 若满足,则更新可行解和目标函数值z0。可行解0..0xj...x1(前面'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.

总结:

在解决很多问题的时候,枚举(搜索)似乎是一种直接了当的方式。但是,当解空间较大时,枚举的效率可能就很低,无法达到目的。此时,不妨想想是否在枚举过程中有一些解可以在枚举之前就判断它一定不满足要求,直接不考虑它们(剪枝),这样就可以缩小解空间,提高效率。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏游戏开发那些事

【随笔】游戏程序开发必知的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n logn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事...

883
来自专栏瓜大三哥

Matlab基础语法4

matlab提供了一些处理多项式的专用函数,用户可以很方便地进行多项式的建立、多项式求值、乘法和除法运算,以及求多项式的倒数和微分、多项式的根、多项式的展开和拟...

22110
来自专栏CDA数据分析师

数据分析师不可不知的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

2128
来自专栏闻道于事

算法学习(一)

不论学习有多忙,也要抽空读点书。 算法 什么是算法? 有一个很著名的公式  “程序=数据结构+算法”。 曾经跟朋友吃饭的时候我问他什么是算法,他说算法嘛,就是一...

3489
来自专栏老九学堂

程序员必须知道的十大基础实用算法及讲解!

最近社群很多的小伙伴们对算法进行了激烈的讨论与学习,今天老九君就给大家介绍一些编程语言里的基础算法,提高小伙伴们的算法知识及编程里对算法的运用。 我们一起来看看...

3515
来自专栏吴伟祥

时间复杂度和空间复杂度详解 原

(1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时...

1002
来自专栏程序员互动联盟

程序员必须要掌握的十大经典算法

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

40013
来自专栏CSDN技术头条

程序员都应该知道的10大算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。

1081
来自专栏随笔小哥哥

程序员必须知道的10大基础实用算法及其讲解:排序、查找、搜索和分类等

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

520
来自专栏华章科技

程序员必须知道的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,...

872

扫码关注云+社区