1 CSP问题与模型

1.1 问题描述

我们有以下问题，原纸卷每个长为L=16m，顾客们分别需要25个3m长，20个6m长，18个7m长的纸卷。那么需要怎样切割才能使得浪费最小呢？

1.2 模型构建

假设有 n 中可行的裁切方案

由此我们得到模型如下：

2 列生成方法理论

2.1 引子

列生成方法是求解大规模线性规划问题的有效方法，这里的大规模是指问题的约束数目有限但变量数目随着问题规模的膨胀而急速膨胀的线性规划问题。

我们刚才讨论的CSP就很好的满足了这一点：

顾客需求确定，约束个数就是确定的；但是有效的方案数目是不确定的

假定n=100时，变量数为100；当n=1,000,000,000时，变量数为1,000,000,000

2.2 单纯形法到列生成

我们都知道求解线性规划的最经典的方法是单纯形法，它是一种在解空间的顶点上迁移来找到问题最优解的算法；但是对于变量很多的LP时，我们遍历顶点的代价是很大的。但是有一点我们肯定知道，那就是我们的约束个数是等于基变量的个数的。另外i啊我们每一步的操作只会让一个非基变量进基。

为了更好的说明先澄清几个概念：

基于上面的解释和概念定义，我们就可以描述单纯形法到列生成的演变路径：

将MP限制到一个变量更少的子问题RMP，使用单纯形法求解RMP的最优解

使用subproblem去检验剩余变量的reduced cost是否小于0；若是，将与该变量相关的系数列加入到RMP中，返回第1步；否则，得到了原问题的最优解。

2.3 subproblem

这里终点讨论一下子问题，子问题的作用是为了检查剩余非基变量的reduced cost，确定它能否作为入基变量。

先来一张规范的单纯形表：

在单纯形法中，我们通过计算非基变量检验数 ，为负且最小的情况下的变量作为入基变量

在这个问题中，我们求解的关键是，它包含两重含义：

通过求解RMP问题得到的影子价格（shadow price）。

通过求解RMP对偶问题得到的对偶变量(dual variable)。

通俗的理解，影子价格是针对RMP本身而言的，而对偶变量是针对RMP的对偶问题而言的。

若对影子价格和对偶变量理论不熟悉，可前去阅读2.3.1和2.3.2的内容；否则我们继续

作为一个懒虫，我们肯定是咋简单咋来：

要想得到影子价格，我们就得解RMP，但是很不幸RMP有很多变量，单纯形法可能解不了；此路不通

对偶问题变量少啊，那我们当然选择从对偶变量下手

那就好办了，我们通过求RMP的对偶问题来求解 ，从而得到非基变量的检验数 ，然后建立以检验数最小为目标的subproblem，如果它的目标函数为负，说明这个列可以加入到RMP中；如果它非负，说明已经得到了最优解

2.3.1 对偶理论

对于每个线性规划问题都有一个对偶问题，得到了一个问题的解，另一个问题的解也就迎刃而解了。

再啰嗦一下：

对偶问题的目标函数的系数是原问题约束的右端项

对偶问题的系数矩阵是原问题系数矩阵的转置

对偶问题的约束都是 ≤ ；原问题的约束都是 ≥

对偶问题求最小则原问题求最大

对偶问题的剩余变量和原问题的基变量共同构成了变量空间

对偶问题研究的是资源的估价问题，原问题研究的是资源的最优分配问题

2.3.2 影子价格

对偶变量 表示市场对单位第 i 种资源的估价，这种估价是由资源在生产过程发挥的作用决定的。

在资源最优利用条件下的估价，被我们称为该资源的影子价格；

下面是几点解释：

也可认为是在最优条件下，增加每单位 i 资源，对目标函数的增量贡献值。

当资源利用不充分时，他的影子价格为0；而影子价格不为0时，表示该资源已经耗尽

结合检验数的计算， ，前一项为产品 j 的产值，后一项为生产该产品消耗各资源的影子价格之和(隐含成本)。当产品产值大于资源隐含成本时，生成才有意义，所以检验数必须为非负

2.4 小结

列生成就是从一个变量较少的RMP开始，在得到RMP最优解后，利用其对偶变量建立起一个检验数最小化subproblem；若subproblem目标值为负，则增加新列到RMP中；如果subproblem目标值非负，则得到RMP的最优解。

所谓列生成，就是在每次迭代中添加一个列，直到无列可加时，得到的RMP的最优解就是原问题最优解。

列生成解决的是线性规划问题，如果要解决整数规划问题，还需要借助分支定界法、分支定价、分支切割等方法

3 Cplex OPL演示列生成迭代过程

3.1 第一次迭代

如果每个纸卷只裁切一个类别的纸卷，我们可以得到初始方案：

A = [5,0,0; 0,2,0; 0,0,2]

因此我们选择前三个方案，构建的RMP模型为：

Cplex OPL代码：

 dvar int+ y1; dvar int+ y2; dvar int+ y3;
 minimize y1 + y2 + y3;
 subject to{
5*y1 + 0*y2 + 0*y3 >= 25;
0*y1 + 2*y2 + 0*y3 >= 20;
0*y1 + 0*y2 + 2*y3 >= 18;
} 

得到结果为：Y = [5, 10, 9];

对偶变量为：

现在我们要加一列到RMP中，记为 ，计算其检验数：

我们便得到了一个子问题：

Cplex代码：

dvar int+ a14; dvar int+ a24; dvar int+ a34;
minimize 1 - (0.2*a14 + 0.5*a24 + 0.5*a34);
subject to{
3*a14 + 6*a24 + 7*a34 <= 16;
}

得到 ，ruduce cost的取值为负数，因此加入