本文是孫小玲教授整數規劃教學視訊的學習筆記
以一個實際問題為例引出列生成算法。
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