ラグランジュ緩和法#

読み: らぐらんじゅかんわほう
英名: Lagrangean Relaxation Method

問題 \(P\) の構造に着目してラグランジュ緩和問題を生成し，ラグランジュ乗数の更新を繰り返すことにより，大規模問題の下界および上界を求めるアルゴリズムである．ラグランジュ乗数の特定の求め方（劣勾配法）と結び付けて捉えられているため，列生成法とは別個のものとして扱われるが，ラグランジュ双対を構成して大規模問題を反復的に解く方法であると考えれば列生成法と等価な枠組みだと解釈することもでき，アルゴリズムの性能も同等である．以下の説明では問題 \(P\) が最小化問題であると仮定している．

ビンパッキング問題や多品種流問題を考えると，多くの部分問題を「結節点」となる制約で結び付けたような構造を持っている．ビンパッキング問題では部分問題がビンの詰め込み問題，カバーの制約が結節点となる．一方，多品種流問題では，品種毎のフローの問題が部分問題で，各辺の流量制約が結節点となる．そのような場合，「結節点」の制約をラグランジュ緩和すると，緩和問題 \(L(\lambda)\) は分離可能となり，部分問題は元の問題に比べて小さな，独立に解ける問題となる．したがって \(L(\lambda)\) の最適解 \(\theta(\lambda)\)，すなわち問題 \(P\) の下界値は元の問題 \(P\) を解くよりも少ない計算コストで得ることができる．

良質な下界を得るためには，ラグランジュ乗数の値を決定する方法が重要であるが，ラグランジュ緩和法では通常，\(\theta(\lambda)\) が一般にラグランジュ乗数 \(\lambda\) の微分不可能な凸関数となるという性質を用いて劣勾配法を用いる．ラグランジュ乗数の更新と，\(L(\lambda)\) の最適化を繰り返して下界を更新し，実行可能解（上界）は \(L(\lambda)\) の最適解から問題依存の方法を用いて適宜復元するのがラグランジュ緩和法の枠組みである．

ラグランジュ乗数の値を決定するのに主に採用される劣勾配法は実装が簡単であるが，微分不可能な凸関数を最適化する方法としては素朴で，性能の良い方法ではない．そのため発電計画問題（Unit Commitment問題）を解く場合には，劣勾配法ではなく，切除平面法を改良したバンドル法を用いることが行われている [1]．この方法は列生成法における安定化（Stabilization）と呼ばれる方法と同様の動機から現れていることは興味深い．