本文是孙小玲教授整数规划教学视频的学习笔记
以一个实际问题为例引出列生成算法。
Cutting stockproblem 切割下料问题
假设工厂有标准长度为218cm的钢管，现有客户需要44个长度为81cm的钢管，3个长度为70cm的钢卷，48个长度为68cm的钢卷。请问如何将标准长度为218cm的钢管进行切割，才能保证所使用标准长度钢管的数目最小？
切法1：将1个标准长度的钢管切成1个81cm的钢管
切法2：将1个标准长度的钢管切成1个70cm的钢管
切法3：将1个标准长度的钢管切成1个68cm的钢管
……
切法n:
可能各位也发现上述3种切法有点浪费材料，但这么切一定能满足要求，所以可以作为文末求解该问题时的初始解。
还可以有好多种切法，文章的最后会对该问题进行求解。
切割下料问题经典的数学模型如下所示：
但是这个数学模型从计算角度和理论角度而言效率不高。
主要原因是这个数学模型的线性松弛问题LP很差（即LP问题的解与原问题的解相差很大）。事实上，松弛问题LP的界为
改进的数学模型
符号：
虽然上述模型看起来比第一个模型简单了，但是我们并不知道一共有多少种切法，所以这个模型无法用显式表达出来。
微博：随心390