单纯型法与列生成法

单纯型法 Simplex Method

单纯形法是求解线性规划代表性的算法。其基于这么样的一个事实：线性规划是在凸集上的凸优化问题，因此其局部最优解也是全局最优解。而这些局部最优解是会出现在该凸集的顶点上，所以单纯形法的思路就是在这些顶点上移动，一直移动到局部最优的顶点。这些顶点也叫做基本可行解，那么这些移动也就是从一个基本可行解通过基变换(即从众多非基变量中选择一个进基，再从基变量中选择一个使其出基)变成另一个基本可行解，直到不能再使得优化目标更优为止（这里，我们采用线性规划的标准形式，即最小化目标函数）。这个基变换的操作涉及到进基和出基，那么如何选择哪个非基变量进基呢？这里就会涉及到reduced cost rate。用单纯型法的语言来说就是，通过数次基变换，使得再也找不到一个非基变量使得reduced cost rate小于零，即再也找不到一个非基变量进基使得目标函数减小，这样我们就找到目标函数在其polyhedron上的最优值。单纯形法简单过程如下面这张图所示，但完整的推导请参考Introduction to Linear Optimization的第二、三章相关内容。

列生成算法 Column Generation Algorithm

单纯型法虽然能保证在数次迭代后找到最优解，但是其面对变量很多的线性规划问题就显得很弱了。因为它需要去在众多变量里进行基变换，这种枚举的工作量是可怕的。因此，有人基于单纯型法提出了列生成算法，其思路大概就是先把原问题(master problem)restrict到一个规模更小（即变量数比原问题少的）的restricted master problem，在restricted master problem上用单纯型法求最优解，但是此时求得的最优解只是restricted master problem上的，并不是master problem的最优解。此时，就需要通过一个subproblem去check在那些未被考虑的变量中是否有使得reduced cost rate小于零的呢（其具体的做法就是通过求解一个线性最大化问题，即求未被考虑的变量中的reduced cost rate的最大值）？如果有，那么我就把这个变量的相关系数列加入到restricted master problem的系数矩阵中。经过这样反复的迭代，直到subproblem中的reduced cost rate大于等于零，那么master problem就求到了最优解。更详细的过程参看以下两张图：

再次注意到，子问题是一个背包问题，通过求解该问题，我们既可以得到未被restricted master problem考虑到的变量中最大的reduced cost rate，又能得到相应的系数列。

列生成算法经典例子 Cutting Stock Problem

下面给出一个列生成法的经典例子，Cutting Stock Problem。

文章转载自：https://xijunlee.github.io/2017/10/12/%E4%BB%8E%E5%8D%95%E7%BA%AF%E5%9E%8B%E6%B3%95%E5%88%B0%E5%88%97%E7%94%9F%E6%88%90%E7%AE%97%E6%B3%95/