带你彻底了解Column Generation（列生成）算法的原理

前言

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

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

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、9个方案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

列生成代码

关于Cutting Stock Problem的列生成java代码，请参考此前公众号的一篇文章，运筹学教学|列生成（Column Generation）算法（附代码及详细注释）。下一次我们会给大家带来列生成算法关于VRP问题的求解方法，以及代码详解。敬请期待！

06

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