运筹优化理论|列生成算法（Column Generation）解决下料问题-使用ortools求解器

Answer 1

列生成算法涉及的知识点非常多，掌握列生成算法要具备以下基础知识：

Column Generation是一种用于求解大规模线性优化问题的非常高效的算法，其理论基础是由Danzig等于1960年提出。本质上而言，列生成算法就是单纯形法的一种形式，用来求解线性规划问题。它的核心思想是通过四个步骤实现：第一步，将原问题（Master Problem）的规模缩小，得到一个限制主问题（Restricted Master Problem，RMP）。第二步，在 RMP 上运用单纯形法求最优解，可以得到解以及一个对偶解。第三步，通过对偶解来构造子问题（Subproblem，SP），求解子问题得到一个新的生成列，验证生成列的检验数（一般就是子问题的目标函数），如果检验数非负则结束算法，否则把生成列作为新变量加入 RMP 。第四步，反复迭代直到找到最优解为止。

列生成算法广泛应用于大规模整数规划问题的求解中。例如，Gilmore 和 Gomory 在1961年首次将列生成技术用于求解下料问题（Cutting Stock Problem）；Desrosiers 等人于1984年将列生成与分支定界结合以求解带时间窗的车辆路径规划问题，称之为分支定价算法（branch and price）。列生成算法也被用于装箱和切割问题、并行机调度问题、车辆路线问题的相关研究中。另外，它也被用于乘务员调度、通信网络中的信道分配、多商品流等问题的研究中。

一维下料问题一般描述是：钢材厂有一批钢管数量为[公式]，长度都为 [公式]；假设有 [公式]种不同长度的产品：每种产品的长度为 [公式]，每种产品的需求量是 [公式]根，优化的目标是：如何切割钢管使得既能满足客户的产品又能消耗最少？

常规的整数规划模型中我们算的是最小的被切割钢管数量，但是同时也知道了每一根钢管上的不同的切割规格和次数。我们把钢管上不同的切割规格和次数看成一种可行切割方案。这里我们假设所有的可行切割方案均已知，令所有可行切割方案集合为[公式]，引入参数和决策变量，可以得到原问题的模型。

通过使用Column Generation的方法，我们可以找到进基的非基变量，即如何不断的找出新的切割方案(新的一列)，使得新的一列添加进去之后（实际上就是单纯形法的进基），主问题的目标函数能下降最多。我们令检验数为[公式]，选择检验数为负且最小的作为进基。子问题的优化目标就是基于检验数的最小化。

我们通过一个小栗子来看一下列生成算法。假设钢管的长度[公式]是17米,有三种产品的需求长度分别为 [公式]=[3,6,9];需求量分别为 [公式]=[25,20,18]。首先，我们要建模并且给出一个初始可行解。然后，根据我们子问题的模型以及求出的[公式]= [0.2,0.5,1.0]来构建我们的SP，求解SP并更新主问题模型直到检验数非负，此时说明已经没有其他的列能对优化目标产生减少作用，那么我们的目标已经达到了全局的最优值。