列生成算法是一种算法框架（也可以称为是一种思想，不能单独用来具体求解），运用DW分解将问题分解为主问题和子问题，在子问题中求出检验数最优的列（子问题的求解需要用其他诸如启发式、求解器等进行求解），将此列加入主问题中进行求解（主问题求解方式可以是启发式、求解器等进行求解，加入此列的过程即为列生成算法）。
列生成算法实际起到一种辅助计算的作用，能够缩小问题规模，使之能够算得更快。除了列生成，类似其能够简化问题的算法还有行生成。
一、Cutting Stock Problem引入
（运用该问题的引入作为例子进行讲解）
问题：原纸卷每个长为L=16m，顾客们分别需要25个3m长，20个5m长，18个7m长的纸卷。那么需要怎样切割才能使得浪费最小呢？
二、简介
当求解一个最小化问题时，列生成算法主要的作用是为每个搜索树节点找到一个较优的下界(lower bound)（目标函数为求解最小值，故问题的下界为理论最优解，较优的下界实际为较优的可行解）。本质上而言，列生成算法就是单纯形法的一种形式，是用来求解线性规划问题的。
在某些线性优化问题的模型中,约束的数目有限，但是变量的数目可能会非常非常的多，因此不能把所有的变量都显性的在模型中表达出来。比如刚刚介绍的Cutting Stock Problem的模型。随着一卷纸长度的不断增加，可行的切割方案数量是爆炸式增长的。
单纯形法虽然能保证在数次迭代后找到最优解，但像Cutting Stock Problem这一类的问题，由于变量太多根本无法把所有的变量都显性的在模型中表达出来。所以单纯形法在这里就无能为力了。
再有，在用单纯形法求解这类线性规划问题时，基变量(basic variable)只与约束的个数相关，每次迭代只会有一个新的非基变量(non-basic variable)进基，因此，在整个求解过程中其实只有很少一部分变量会被涉及到。
**总结详细表述：**在某些线性优化问题的模型中,约束的数目有限，但是变量的数目随着问题规模的增长会爆炸式的增长，因此不能把所有的变量都显性的在模型中表达出来。在用单纯形法求解这类线性规划问题时，基变量(basic variable)只与约束的个数相关，每次迭代只会有一个新的非基变量(non-basic variable)进基，因此，在整个求解过程中其实只有很少一部分变量会被涉及到。简单来说，列生成算法通过求解子问题(pricing problem)，来找到可以进基的非基变量，该非基变量在模型中并没有显性的写出来（可以看成是生成了一个变量，每个变量其实等价于一列，所以该方法被称为列生成算法）。如果找不到一个可以进基的非基变量，那么就意味着所有的非基变量的检验数（reduced cost）都满足最优解的条件，也就是说，该线性规划的最优解已被找到，即使很多变量没有在模型中写出来。
三、基本思路
-
先把原问题P_0限制（restrict）到一个规模更小（即变量数比原问题少的）的问题P_1（主问题），用单纯形法求解P_1的最优解，但是此时只求得了P_1的最优解，而不是P_0 的最优解。
-
此时，就需要通过一个子问题（subproblem）（拥有问题P_1外的其他部分变量的问题）去检查是否存在一个非基变量，其reduced cost小于零？如果有，那么就把这个变量相关的系数列（column）加入到原问题P_0的系数矩阵中，回到第1步。
经过反复迭代，直到找不到reduced cost（检验数，此时目标函数是求最小值，所以需要检验数小于0的，才能使目标函数减小）小于零的非基变量，那么就求得了原问题P_0的最优解。
四、相关概念
4.1 Master Problem(MP)
对于一般问题而言，如果要用列生成求解，一般需要重新建模成set covering model（集合覆盖模型），也就是和上面的Cutting Stock Problem类似形式的模型。重新建模成set covering model以后的问题就是master problem了。在Cutting Stock Problem中由于一开始就是建成这种形式，所以其Master Problem就是原模型：
4.2 Linear Master Problem（LMP）
Column Generation 是一种用于求解大规模线性优化问题的方法。而上面的模型中，决策变量是整数，因此要用列生成算法的话，需要把整数变量进行线性松弛，从而得到linear master problem：
4.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.4 Subproblem
RLMP求解完成后，我们想看看是否有非基变量
可以变为基变量。通过
中寻找检验数最小并且为负数的变量，将变量对应的那一列添加到RLMP中。
有两重含义：
- 通过求解RLMP问题得到的影子价格（shadow price）。
- 通过求解RLMP对偶问题得到的对偶变量(dual variable)。
虽然通过单纯型法直接求解restricted linear master problem能得到
。但是restricted linear master problem也可能是一个变量很多的线性规划。为了加快求解速度，通过单纯型法求restricted linear master problemde的对偶问题（将restricted linear master problem对偶一下，就能使得变量数大幅减小，因为这些变量转换成了对偶问题中的限制条件了)，能更快地得到子问题想要的。
总结：通过求解RLMP问题或者RLMP对偶问题，得到我们想要的
以后，subproblem就是通过这条公式，在
中寻找检验数为负并且最小的变量，将变量对应的那一列添加到RLMP中。
五、算法流程
六、列生成过程（以Cutting Stock Problem求解过程为例）
6.1 Restricted Linear Master Problem
首先，一个卷筒有很多种切割方案，其中比较简单的三种如下：
方案1：切成5个3m
方案2：切成2个6m
方案3：切成2个7m
很容易得出，5个方案1、10个方案2、9个方案3，是能满足所有客户需求的，这就意味着只要RMP问题包含了这三个方案，肯定是能找到一个可行解的。即得到LMP的一个RLMP如下：
其中，
这三列分别对应着方案1、方案2、方案3。还有一点需要注意的，对于每一列，都需要满足：
也就是每一个长纸卷只有16的长度，不能超出这个长度。这个叫列生成规则，不同问题有不同的规则约束。subproblem在寻找某些列或者生成某些列时，就是必须受到列生成规则的约束。
6.2 列生成迭代过程
6.2.1 第一次迭代
6.2.2 第二次迭代
6.2.3 第三次迭代
得到RLMP的最优解y = [1.2,0,0,1,18]，这里因为把MP的整数决策变量给线性松弛了，求解的是MP问题的一个lower bound（理论最优解)。毕竟列生成是用于求解linear program的。文章来源：https://www.toymoban.com/news/detail-743348.html
yj是第j个方案的用纸（大纸，16m）数量，a1j表示第j个方案得到3m纸的数量，a2j表示第j个方案得到6m纸的数量，a3j表示第j个方案得到7m纸的数量。文章来源地址https://www.toymoban.com/news/detail-743348.html
到了这里，关于【算法】列生成算法原理解析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![【Python数据结构与算法】--- 递归算法的应用 ---[乌龟走迷宫] |人工智能|探索扫地机器人工作原理](https://imgs.yssmx.com/Uploads/2024/02/752756-1.gif)
