带你彻底了解Column Generation(列生成)算法的原理附java代码

00

前言

这几天勤奋的小编一直在精确算法的快乐学习之中不能自拔。到列生成算法这一块,看了好几天总算把这块硬骨头给啃下来了。

然后发现网上关于列生成的教学资料也不是很多,大部分讲的不是那么通俗易懂。所以今天就打算写一写这个算法,尽可能写得通俗易懂。

01

预备知识预警

由于列生成算法涉及的知识点非常多,所以在开始之前希望读者必须要具备以下基础知识,不然就没法往下玩了:

  • 线性规划以及线性规划对偶问题
  • 单纯形法原理
  • 原问题的影子价格(shadow price)以及对偶变量
  • 单纯形法非基变量进基时非基变量检验数(reduce cost)的计算

以上内容我就不展开科普了。如果对这些概念还不熟悉的小伙伴,一定要回去搞清楚再往下看哦。

Cutting Stock Problem[1]

讲column generation怎么可能少得了Cutting Stock Problem这个经典的问题呢!在开始之前我们将以这个问题为铺垫一步一步往下讲解。

我们有以下问题,原纸卷每个长为L=16m,顾客们分别需要25个3m长,20个5m长,18个7m长的纸卷。那么需要怎样切割才能使得浪费最小呢?

建模

Column Generation Formulation:

对于一卷纸,可以有很多种切割方案。

表示跟第j种切割方案可获得的类别为i的短纸卷个数。

表示根据第 j 种方案切割的长纸卷个数。

于是,我们得到如下模型:

上面的模型中,所有可行的切割方案的总数为n,我们并不知道这个值是多少,也不需要知道,只需要知道它很大很大。并且,随着长纸卷长度增加,短纸卷个数增加,n的值会呈指数增长。

总之,可行的切割方案非常多,当问题规模很大时,我们无法将所有的切割方案枚举出来,也就是说我们无法将所有的变量显性的列出来。

02

什么是Column Generation?

2.1

相关背景

Column Generation是一种用于求解大规模线性优化问题的非常高效的算法[3],其理论基础是由Danzig等于1960年提出。本质上而言,列生成算法就是单纯形法的一种形式,是用来求解线性规划问题的。列生成算法已被应用于如下著名的NP-hard问题,即:机组人员调度问题(Crew Assignment Problem)、切割问题(Cutting Stock Problem)、车辆路径问题(Vehicle Routing Problem)、单资源工厂选址问题(The single facility location problem )等。

2.2

Large Linear Programing Model

在某些线性优化问题的模型中,约束的数目有限,但是变量的数目可能会非常非常的多,因此不能把所有的变量都显性的在模型中表达出来。

比如刚刚介绍的Cutting Stock Problem的模型。随着一卷纸长度的不断增加,可行的切割方案数量是爆炸式增长的。

2.3

Column Generation

单纯型法虽然能保证在数次迭代后找到最优解,但像Cutting Stock Problem这一类的问题,由于变量太多根本无法把所有的变量都显性的在模型中表达出来。所以单纯形法在这里就无能为力了。

再有,在用单纯形法求解这类线性规划问题时,基变量(basic variable)只与约束的个数相关,每次迭代只会有一个新的非基变量(non-basic variable)进基,因此,在整个求解过程中其实只有很少一部分变量会被涉及到。

因此,有人基于单纯型法提出了列生成算法。其思路概述如下[1]:

1. 先把原问题P_0限制(restrict)到一个规模更小(即变量数比原问题少的)的问题P_1,用单纯形法求解P_1的最优解,但是此时只求得了P_1的最优解,而不是P_0 的最优解。

2. 此时,就需要通过一个子问题(subproblem)去检查是否存在一个非基变量,其reduced cost小于零?如果有,那么就把这个变量相关的系数列(column)加入到原问题P_0的系数矩阵中,回到第1步。

经过反复迭代,直到找不到reduced cost小于零的非基变量,那么就求得了原问题P_0的最优解。

看算法流程图会更加直观哦[2]:

03

相关概念科普

刚刚讲的内容涉及到了几个概念,master problem,linear master problem(LMP),restricted linear master problem (RLMP),subproblem等,这一节来把这几个概念给讲清楚。还是基于上面的Cutting Stock Problem的模型:

3.1

Master Problem(MP)

对于一般问题而言,如果要用列生成求解,一般需要重新建模成set covering model,也就是和上面的Cutting Stock Problem类似形式的模型。重新建模成set covering model以后的问题就是master problem了。在Cutting Stock Problem中由于一开始就是建成这种形式,所以其Master Problem就是原模型:

3.2

Linear Master Problem(LMP)

Column Generation 是一种用于求解大规模线性优化问题的方法。而上面的模型中,决策变量是整数,因此要用列生成算法的话,需要把整数变量进行线性松弛,从而得到linear master problem:

3.3

Restricted Linear Master Problem(RLMP)

把LMP给restrict到一个规模更小(即变量数比原问题少的)的就是restricted linear master problem了。在上面的linear master problem中找出满足约束条件的k个列,得到如下restricted linear master problem:

可以看到,相比原来的linear master problem,restricted linear master problem相当于把

强制限制为非基变量了[4]。

3.4

Subproblem

核能预警,如果这部分看不懂,请确保预备知识过关。如果预备知识不过关,请在运筹学老师的陪同下观看,谢谢合作!

RLMP求解完成后,我们想看看是否有非基变量

可以变为基变量。

还记得怎么找进基的非基变量吗?(不记得就去问你们的运筹学老师)。当然是通过非基变量的检验数辣,通过

中寻找检验数最小并且为负数的变量,将变量对应的那一列添加到RLMP中。

那么,在检验数的计算公式中,大家还记得

是什么吗?

有两重含义:

  • 通过求解RLMP问题得到的影子价格(shadow price)。
  • 通过求解RLMP对偶问题得到的对偶变量(dual variable)。

所以在开始之前小编一直强调预备知识一定要过关。这两个含义意味着我们有上面两种方式得到

,不过我们一般倾向于使用第二种,WHY?

虽然通过单纯型法直接求解restricted linear master problem能得到

。但是restricted linear master problem也可能是一个变量很多的线性规划。

为了加快求解速度,通过单纯型法求restricted linear master problemde的对偶问题(将restricted linear master problem对偶一下,就能使得变量数大幅减小,因为这些变量转换成了对偶问题中的限制条件了),能更快地得到子问题想要的[1]。

所以我们总结一下:

通过求解RLMP问题或者RLMP对偶问题,得到我们想要的

以后,subproblem就是通过

这条公式,在

中寻找检验数为负并且最小的变量,将变量对应的那一列添加到RLMP中。

3.5

算法流程图

通过上面讲了这么多以后,这里在给出一个更详细的流程图[5]:

04

Column Generation过程

通过上面的问题分析和建模以后,我们这一步一步一步来求解该问题,让大家彻底理解column generation这个过程。

该过程模拟需要用到一个线性求解器,大家还记得小编以前讲过的lpsolve的教程吗?赶紧去翻一下以前的教程,干货 | 关于数学规划求解器lp_solve 这里有份超全面超详细的教程,你离lpsolve高手只有一步之遥!把lpsolveIDE装上,然后跟着小编的脚步一步一步往下走。

4.1

Restricted Linear Master Problem

前面我们完成了问题的建模,得到了Cutting Stock Problem的linear Master Problem。现在,我们想办法找到一个有可行解的RLMP问题:

首先,一个卷筒有很多种切割方案,其中比较简单的三种如下:

方案1:切成5个3m

方案2:切成2个6m

方案3:切成2个7m

很容易得出,5个方案1、10个方案2、8个方案3,是能满足所有客户需求的,这就意味着只要RMP问题包含了这三个方案,肯定是能找到一个可行解的。即得到LMP的一个RLMP如下:

其中,

这三列分别对应着方案1、方案2、方案3。还有一点需要注意的,对于每一列,都需要满足:

也就是每一个长纸卷只有16的长度,不能超出这个长度。这个叫列生成规则,不同问题有不同的规则约束。subproblem在寻找某些列或者生成某些列时,就是必须受到列生成规则的约束。

4.2

列生成迭代

iteration 1

RLMP:

将该模型输入lpsolve,得到对偶变量如下:

得到

。现在要找一列加入RLMP,是哪一列呢?现在还不知道,我们暂记为

非基变量检验数

subproblem:

求解结果得

,reduced cost 为负数,因此将

加入RLMP,开始第二轮迭代。

iteration 2

RLMP:

将该模型输入lpsolve,得到对偶变量如下:

得到

。现在要找一列加入RLMP,是哪一列呢?现在还不知道,我们暂记为

。非基变量检验数

subproblem:

求解结果得

,reduced cost 为负数,因此将

加入RLMP,开始第三轮迭代。

iteration 3

RLMP:

将该模型输入lpsolve,得到对偶变量如下:

得到

。现在要找一列加入RLMP,是哪一列呢?现在还不知道,我们暂记为

。非基变量检验数

subproblem:

求解结果得

,reduced cost 不为负数,因此不用将

加入RLMP,列生成算法结束。

最终,我们求解最后一次迭代的RLMP:

(0.9999999999是精度问题)

得到RLMP的最优解

,这里因为把MP的整数决策变量给线性松弛了,求解的是MP问题的一个lower bound。毕竟列生成是用于求解linear program的。如果要求解大规模整数规划问题,后面我们会介绍结合column generation的branch and price方法。

至此,我们已经完完整整把列生成算法给走了一遍。

05

References

[1] 从单纯型法到列生成算法, Xijun (Ted)

[2] A tutorial on column generation and branch-and-price for vehicle routing problems, Dominique Feillet

[3] https://en.wikipedia.org/wiki/Column_generation

[4] 运筹系列8:Set partitioning问题的列生成方法

[5] Column generation algorithms

[6] Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints, Zhixing Luo, Hu Qin, Andrew Lim

原文发布于微信公众号 - 程序猿声(ProgramDream)

原文发表时间:2019-08-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券