1. 应用场景

列生成算法是不断添加求解变量的算法，可参考论文。列生成算法常常用于如下的场景：使用set-covering构建的模型，变量非常多，约束相对较少。
具体来说，场景如下：有n$n$个0-1变量z1...zn$z_1...z_n$，每个zi$z_i$带着很多中间变量xi,j$x_{i,j}$用来进行约束，这是个变量很多，约束也很多的模型。我们首先使用set-covering对问题模型进行转化，将所有zi$z_i$的组合枚举出来，在枚举的过程中，就把约束条件都过了一遍，只有满足所有约束条件的组合才会保留下来。最后的枚举结果分别对应y1...ym$y_1...y_m$。
不难看出，m$m$是n$n$的指数形式，使用set-covering模型之后，变量的数量大的可怕。比较好的情况是，原问题的约束条件比较紧，只有少数组合成立，这样m的数量比较小，问题就比较好解决。
Dantzig-Wolfe分解对应的问题有特殊的结构，很多讲解列生成算法的文献指的都是DW分解。这部分内容放在第3节。

2. Set-covering的列生成算法

列生成的思路和行生成基本相同，基本原理是：通过子问题不断给主问题添加变量进行求解。由于列生成算法求解的是松弛线性规划问题，因此对整数规划模型需要结合branch and bound算法进行。
列生成算法对应的模型是：
min |y|$|y|$
s.t. Aiy≥bi$A_{i}y\ge b_i$，i=1...n$i=\mathrm{1...}n$
将A$A$的第j$j$列记作aj$a_j$，y$y$是一个向量y=[y1,...,ym]$y=[y_1,...,y_m]$；并且有重要的一点：set-covering的变量yj$y_j$对应的列aj$a_j$生成的规则，可以通过线性约束条件 d∗aj≤e$d\ast a_j\le e$得到。这使得我们可以用线性规划的方法来求解子问题~

2.1. 限制主问题

首先用启发式算法找出一部分A$A$，比如说选出了k$k$列。然后我们的线性规划问题就变成了：
min y1+y2+...+yk$y_1+y_2+...+y_k$
s.t. a1∗y1+a2∗y2+...+ak∗yk≥bi$a_1\ast y_1+a_2\ast y_2+...+a_k\ast y_k\ge b_i$，i=1...n$i=\mathrm{1...}n$
相比原来的模型，相当于把yk+1$y_{k+1}$~ym$y_m$强制限制为非基变量了，称为限制主问题（Restricted Master Problem，RMP）。上面的限制主问题求解完成后，我们想使用单纯型法进行基变量的转换，看看yk+1$y_{k+1}$~ym$y_m$中，是否有可以转入基变量的列。检验数σ=cN−π∗aj$\sigma =c_N-\pi \ast a_j$，并且π=cBB−1$\pi =c_B{B}^{-1}$可以由求解器给出。我们要找出非基变量中最小的负数σ$\sigma$，将其转入基变量。正如前面所述，我们这里使用线性规划来找这个新的列。

2.2. 子问题

注意c=[1,...,1]$c=[1,...,1]$，并且aj$a_j$满足d∗a≤e$d\ast a\le e$，因此 min cN−πaj$c_N-\pi a_j$等价于
min 1−π∗a$1-\pi \ast a$
s.t. d∗a≤e$d\ast a\le e$ (列生成的规则)
称为子问题（sub problem）。如果目标函数最优值＜0，就将新生成的列y_k+1转入基变量，生成新的限制主问题进行求解。如此往复，直至子问题的目标函数≥0。

3. Dantzig-Wolfe分解

关于DW分解的内容，可以参考PPT
DW分解的问题对应的约束条件具有如下的结构：

第一行的约束Ay=b叫complicating/coupling constraints，后面的By=d可以看做是列生成的规则。
DW分解的思路是，将变量用极点/极线表示。开始的时候极点/极线对应的变量很少，然后根据子问题的求解结果不断给主问题添加极点/极线。

3.1. 子问题

先给出Bx = b的一些极点和极线，比如说是x1...xk$x_1...x_k$，带入子问题求解：
min Σi(cN−πAj)xi${\Sigma }_i(c_N-\pi A_j)x_i$
s.t. Bixi=bi$B_i{x}_i=b_i$
然后可以求得新的极点/极线xk+1$x_{k+1}$

3.2. 限制主问题

min cy$cy$
s.t. Ay=b（π）$Ay=b（\pi ）$
y=Σux$y=\Sigma ux$（这个约束可以用来消除模型中的y$y$）
Σu=1（t）$\Sigma u=1（t）$
t$t$是问题的上界，如果最优值cy∗=t$c{y}^{\ast }=t$，那么就取到了最优值，否则继续求解子问题添加变量。