看到BC编程系统中的算法运用和做过大量的BC项目后，越来越能感觉到，现在的所有的程序系统搭建演变，都是附随着一代又一代的算法迭代和创新才推动出更多元化的项目场景的解决方案。平时的BC演示项目中运用比较多的列生成算法，应该是逻辑算法中的应用典范了。让我用最简单的文字叙述来慢慢为你解释列生成算法的逻辑演变过程。

弄懂列生成算法的基础原理，才能更好的使用好这个工具

列生成算法是由对偶角度和单纯形算法角度组成。在

对偶的概念。

假设有个长得很标准的线性规划问题：

那么，它的对偶问题为：

下面我们都以这个问题来讨论，即说到原问题时，默认是一个最小化问题；说到对偶问题时，默认是一个最大化问题。

怎么理解这个对偶关系呢？借用经济学方面的话来说，假设原问题的目标是让成本最小，那么对偶就是让收入最大。更确切地讲，是：

原问题丶：保证收入不低于某个值的条件下，使成本最小化。

对偶问题：保证成本不高于某个值的条件下，使收入最大化。

那个丶纯粹是为了对齐，忽略之……

可以看到，原问题和对偶问题其实就是一个问题：目标净收益最大。只是一个是约束收入优化成本，一个是约束成本优化收入。角度不同而已。体现在公式上，就是原问题的变量对应对偶问题的约束，目标系数对应约束边界，约束矩阵倒转过来。

单纯型法虽然能保证在数次迭代后找到最优解，但是其面对变量很多的线性规划问题就显得很弱了。因为它需要去在众多变量里进行基变换，就上面的问题而言，你想想你要在近10000个变量里面找个能进基的，活着不好吗？

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

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

先把原问题(master problem)restrict到一个规模更小（即变量数比原问题少的）的restricted master problem，在restricted master problem上用单纯型法求最优解，但是此时求得的最优解只是restricted master problem上的，并不是master problem的最优解。

此时，就需要通过一个subproblem去check在那些未被考虑的变量中是否有使得reduced cost小于零的？如果有，那么就把这个变量的相关系数列加入到restricted master problem的系数矩阵中，回到第1步。

经过反复的迭代，直到subproblem中的reduced cost rate大于等于零，那么master problem就求到了最优解。

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

03 相关概念科普

刚刚讲的内容涉及到了几个概念，master problem，restricted master problem，subproblem等，这一节来把这几个概念给讲清楚。基于一个问题线性规划问题：

min(y1+...+yn)R1:a11y1+...+a1nyn≥b1R2:a21y1+...+a2nyn≥b2……Rm:am1y1+...+amnyn≥bmmin(y1+...+yn)R1:a11y1+...+a1nyn≥b1R2:a21y1+...+a2nyn≥b2……Rm:am1y1+...+amnyn≥bm

3.1 master problem(MP)

master problem可以认为是原问题。即

min(y1+...+yn)R1:a11y1+...+a1nyn≥b1R2:a21y1+...+a2nyn≥b2……Rm:am1y1+...+amnyn≥bmmin(y1+...+yn)R1:a11y1+...+a1nyn≥b1R2:a21y1+...+a2nyn≥b2……Rm:am1y1+...+amnyn≥bm

3.2 restricted master problem(RMP)

前面我们说过，把原问题(master problem)restrict到一个规模更小（即变量数比原问题少的）的就是restricted master problem了。比如可以用启发式算法，在上面的master problem找出满足条件（也就是形成的restricted master problem必须要有可行解）的k个列，得到如下的restricted master problem：

min(y1+y2+...+yk)R1:a11y1+...+a1kyk≥b1R2:a21y1+...+a2kyk≥b2……Rm:am1y1+...+amkyk≥bmmin(y1+y2+...+yk)R1:a11y1+...+a1kyk≥b1R2:a21y1+...+a2kyk≥b2……Rm:am1y1+...+amkyk≥bm

可以看到，相比原来的master problem，restricted master problem相当于把yk+1...ymyk+1...ym强制限制为非基变量了。[4]

3.3 subproblem

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

上面的限制主问题求解完成后，我们想使用单纯型法进行基变量的转换，看看yk+1...ymyk+1...ym中，是否有可以转入基变量的列。还记得怎么找进基的非基变量吗？（不记得就去问你们的运筹学老师）。当然是通过非基变量的检验数辣，通过σj=cj−cBB−1ajσj=cj−cBB−1aj，在yk+1...ymyk+1...ym中寻找检验数最小并且为负数的变量，将变量对应的那一列添加到RMP中。

那么，在检验数的计算公式中，大家还记得cBB−1cBB−1是什么吗？cBB−1cBB−1有两重含义：

通过求解RMP问题得到的影子价格（shadow price）。

通过求解RMP对偶问题得到的对偶变量(dual variable)。

所以在开始之前小编一直强调预备知识一定要过关。这两个含义意味着我们有上面两种方式得到cBB−1cBB−1，不过我们一般倾向于使用第二种，WHY？