列生成法

列生成法#

  • 読み: れつせいせいほう

  • 英名: Column Generation Method

制約付きネットワークフロー問題やカッティングストック問題など, 解が特徴的な構造を持つ「部分解」の重ね合わせとして表現できる性質を利用して大規模な問題を解く技法.

例えばネットワークフロー問題の部分解はネットワークの始点と終点を結ぶパスであり, カッティングストック問題の部分解は,与えられた紙の幅に収まる品目の切り方のパターンである.

ネットワークフロー問題において,始点と終点を結ぶパスは膨大に存在することからわかるように,部分解の数は組合せ的に膨大になる. しかしながら,列生成法ではそのすべてをあらかじめ列挙することなく,アルゴリズム内において必要に応じて生成する. 列生成法は大規模な問題を扱うことができることの他に,下界が求められる, また部分解を求める問題と全体の問題を分離することにより,問題が持つ階層構造を明確化することができるといったメリットがある.以下の説明では解くべき問題が最小化問題であることを仮定している.

列生成法の枠組みは以下の通り.

  1. 解を限定された部分解の重ね合わせで表現した定式(RMP:Restricted Master Problem)を構成する.

  2. RMP を解いて,目的関数の下界と双対変数の値を求める.

  3. 双対変数の値を用いて生成すべき部分解(列)を生成する.

  4. 生成した列を RMP に加えて,何等かの方法で実行可能解と目的関数の上界を求める.

  5. 上下界値のギャップが許容値以下であれば終了する.そうでなければ 1. に戻る

列生成法には初期のRMPの構成の方法や双対変数の取得,実行可能解の取得など実装上の多数のキーポイントが存在し, パフォーマンスを大きく左右することが知られている [1]. また,列生成法はラグランジュ緩和法と密接に関連 [2] しており,2. で現れる「双対変数」は, ラグランジュ緩和法で更新するラグランジュ乗数に他ならない. また,ラグランジュ乗数の更新に劣勾配法でなく微分不可能な凸関数に対する切除平面法 [3] を用いれば, ラグランジュ緩和法は列生成法と等価となる.

関連

参考文献

[1]

O. Briant, C. Lemaréchal, Ph. Meurdesoif, S. Michel, N. Perrot, and F. Vanderbeck. Comparison of bundle and classical column generation. Mathematical Programming, 113(2):299–344, jun 2008. URL: http://link.springer.com/10.1007/s10107-006-0079-z, doi:10.1007/s10107-006-0079-z.

[2]

Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon, editors. Column Generation. Springer US, Boston, MA, 2005. ISBN 978-0-387-25485-2. URL: https://link.springer.com/10.1007/b135457, doi:10.1007/b135457.

[3]

Stephen Boyd and Lieven Vandenberghe. Localization and cutting-plane methods. From Stanford EE 364b lecture notes, 2007. URL: https://see.stanford.edu/materials/lsocoee364b/05-localization_methods_notes.pdf.