資材切出し問題と列生成法

※この記事は数理最適化Advent Calender2020の6日目の記事です．5日目は@ikeday_jagaさんによる数理最適化モデリング言語 PySIMPLE の紹介でした． はじめに 列生成法(column generation method)は線形計画問題に対する単体法のバリエーションの1つです．整数計画問題を解こうとすると，変数の数が膨大でそもそも線形計画緩和問題すら解けそうにない状況が少なくありません．列生成法はそのような状況において，全ての変数を陽に考慮することなく線形計画問題を解いてしまう手法です．列生成法は，GilmoreとGomoryによって1961年に提案されました[1][2]．ここでは，その論文で取り上げられた資材切出し問題(cutting stock problem)を例に列生成法を紹介します． 資材切出し問題と定式化 資材切出し問題は，定型の母材から様々な長さ