运筹优化（十三）--大规模优化方法

针对因为算例的规模过大或者结果过于复杂而无法整体求解的数学模型，将原味分解成多个足够简单、可以单独迭代直接求解的子问题，伴随的主问题结合所有子问题的结果给出模型的精确或者近似精确的最优解，并将最优解相关的信息传递给子问题用以更新模型中相应的参数。

列生成算法

列生成算法通常被应用于求解大规模整数规划问题的分支定价算法(branch-and-price algorithm)中，其理论基础是由Danzig等于1960年提出。当求解一个最小化问题时，列生成算法主要的作用是为每个搜索树节点找到一个较优的下界(lower bound)。本质上而言，列生成算法就是单纯形法的一种形式，是用来求解线性规划问题的。列生成算法已被应用于求解如下著名的NP-hard优化问题：机组人员调度问题(Crew Assignment Problem)、切割问题(Cutting Stock Problem)、车辆路径问题(Vehicle Routing Problem)、单资源工厂选址问题(The single facility location problem )等。

列生成算法的基本思想

在某些线性优化问题的模型中,约束的数目有限，但是变量的数目随着问题规模的增长会爆炸式的增长，因此不能把所有的变量都显性的在模型中表达出来。在用单纯形法求解这类线性规划问题时，基变量(basic variable)只与约束的个数相关，每次迭代只会有一个新的非基变量(non-basic variable)进基，因此，在整个求解过程中其实只有很少一部分变量会被涉及到。简单来说，列生成算法通过求解子问题(pricing problem)，来找到可以进基的非基变量，该非基变量在模型中并没有显性的写出来（可以看成是生成了一个变量，每个变量其实等价于一列，所以该方法被称为列生成算法）。如果找不到一个可以进基的非基变量，那么就意味着所有的非基变量的检验数（reduced cost）都满足最优解的条件，也就是说，该线性规划的最优解已被找到，即使很多变量没有在模型中写出来。

拉格朗日松弛

拉格朗日松弛算法并不是采用直接搜索最优解的策略，而是希望通过对模型进行分解，计算模型最优目标函数值的较强的上下界。有时该分解算法可以用于求解大规模离散模型的线性松弛问题，另外有时，利用拉格朗日松弛甚至可以得到比线性松弛更好的上下界。该算法还可以提高分支界定或者分支割平面算法的求解效率，还可以结合取整运算为原模型得到近似最优解。

对于一个给定的整数规划问题，线性松弛是去掉模型中的整数约束，而拉格朗日松弛则是放松模型中的部分线性约束，保留整数约束和其他线性约束，这些被松弛的约束并不是完全去掉，而是在利用拉格朗日乘子在目标函数上增加相应的惩罚项，对不满足这些约束条件的解进行较大的惩罚。

考虑到任何一个合理的松弛问题都应该使得到的问题更加容易处理，因此，拉格朗日松弛通过利用对偶乘子尽可能松弛线性约束的方法，使得到的子问题更容易求解。

Dantzig-Wolfe分解

该分解算法不再是针对决策候选方案对应于完全信息下的列情况，而是借助拉格朗日松弛算法，将大量的复杂约束与一个或多个具有容易处理的特殊结构（如网络流）的线性约束分解开。

DW分解的问题对应的约束条件具有如下的结构：
运筹优化（十三）--大规模优化方法

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

3.1. 子问题

先给出Bx = b的一些极点和极线，比如说是 x1...xk ，带入子问题求解：
min Σi(cN−πAj)xi
s.t. Bixi=bi
然后可以求得新的极点/极线 xk+1

3.2. 限制主问题

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