下料问题，也称作Cutting Stock，板材切割问题。例如，有一批长度为110cm的板材（且称之为母料吧），需要切割成不同尺寸的小板材，例如下图所示，20cm的需要48个，45cm的需要35个, ....，请问怎样切割，才能最省母料。

切割板材

同样，这个场景也适用于物资打包、车辆物资装载等实际问题。

常规建模

常规建模MIP

这个模型很直观，学过离散优化的同学，第一时间都能手写出来。离散变量是建模的关键，代表从母料b中打造小板材s的个数。
但这个模型性能很差，主要有两个缺点

1. 对约束做线性松弛后，可行解的范围大大增加。而越紧的线性松弛，对剪枝算法来说，性能越好。
2. 充满对称性，导致搜索空间中存在大量的重复计算。

优化模型

建模的对象是一个个切割模式，有点像数学中的标架理论，一个切割模式，就是一个长度为的列向量，代表一块母料的一种切割方式。
我们将母料的所有切割方式放在一起，就形成了一个特别宽的矩阵。目标，就是找到一个正整数向量,使元素之和最小， 同时满足需求条件。

优化建模

这个模型好在哪呢？
首先，线性松弛性很紧，只需要把 去掉即可，例如如果得到 , 说明在最优解中，第1种切割方式需要1.2次，那我们就向上取整，实际值为即可。
最重要的是，这个建模方式里没有对称性，算法搜索空间相对减小了。
问题是，这个切割方式的种类 特别多，实际求解中，不可能全部列举出来，而是采用了一种叫做“列生成”的技术，根据问题特性，通过迭代，每次找到一个有价值的列，过滤掉大部分对目标无益处的列。