列生成（column generation）的应用问题

本文主要是介绍列生成（column generation）的应用问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

当我们讨论列生成算法，一定要了解一个经典问题——木材下料问题(The cutting stock problem)，最初问题的形式为线性规划，相关的问题解析有很多：

优化 | 从集合划分问题到列生成算法

单纯形法和列生成算法解释

线性规划技巧: 列生成(Column Generation)

列生成算法求解矩形下料问题（Matlab代码）

列生成和分支定价

从木材下料问题向外拓展，列生成算法也被用于大规模的线性规划问题，这些问题有以下特征：

大规模意味着变量特别多，很难一次性完全的考虑进来；
只有一小部分变量值是非零的（基变量），大部分变量值为零（非基变量）；
只有部分变量可以改善目标函数。

这篇文章主要想把重心放在，当应用列生成算法时会遇到的一些问题及可能的解决方案。

抽象来说，列生成的思路是在子区域（只包含部分列）先生成一个MVP（也就是可行但不是最优的策略），再去寻找可能减少差额成本/非基变量检验数（reduced cost）的列，可行的话就将这个列加入原本的策略中（微调策略）并更新所有列的cost，继续迭代寻找，直到找到最优的策略。

具体来说，在确定要解决的主问题（MP）之后，需要进行几个关键步骤：

分解问题（Master Problem，MP）为限制主问题（Restricted Master Problem，RMP）与估价问题/子问题（Pricing Problem，PP）；
在每次迭代中，PP通过reduce cost（dual cost）来判断是否有RMP中未涉及到的列（column/independent set）可以改善整个策略。
如果有则将这个列与cost一同加入当前的RMP，重新计算cost。
一直迭代到目标函数接近最优。

所以，这个过程中将会涉及到很多个具体问题：

如何拆分原主问题（MP）？
列如何定义？
reduce cost如何定义？
最开始的子区域是如何选择的？
如何迭代求解最优的策略？
如何判断其接近最优？

而且，即使是这样的整数线性规划问题，随着问题规模的增大，求解的时间也会是难以接受的。如何尽量减少求解的时间？

实际生活中，遇到的问题也并不如木材下料问题那么规整，可能伴随着大量显式或隐式的constraint，我们又如何处理它们？

如何拆分原主问题（MP）？列如何定义？

这两个问题几乎是等价的，当你确定了列的定义，也就知道如何拆分主问题了，因为所求的RMP形式上一般都满足求某个子区域内的向量的线性组合，这个向量一般就是列生成算法中所说的“列”。

所以列可以理解为是最终策略的一个元素，而最终策略，需要集合多种不同的元素达到最优化。换言之，如果最终想要得到的方案一般是一个整体的优化方案，比如最大流问题，路径规划问题等。

有些情况下，列的定义可以是与时间t相关的函数，这种方法比较取巧。

有些问题的拆分是逻辑上自然而然的，因为很容易找到有现成求解办法又使问题规模变小的RMP。比如在木材下料问题中，主问题是最小化切割方案的cost，cost被定义为浪费的木材长度。一条固定长度的木材的切割方案自然地可以通过穷举来得到。所以MP被转化为了选择切割方案的线性组合，这是典型的线性规划问题。切割方案也就是列，组合的weight自然与cost（所浪费的木材长度）所挂钩。

但在一些问题上，RMP和PP的定义是相当困难的。不一定一开始就能找到所有的方案再从中寻找，而是需要特殊的Price model去限制。