トップ > 数理計画用語集 > ベンダーズ分解法

数理計画用語集

ベンダーズ分解法

読み:べんだーずぶんかいほう
英名:Benders Decomposition Method
別名:ベンダーズの分割法

最適化問題 P を線形部分と非線形部分(または整数部分)に分け,2つの問題を繰り返し解くことで最適解を見つけるアルゴリズムであり,大規模問題の解法として知られている.

具体的には,線形部分と非線形部分からなる最適化問題

equation

の変数 equation を固定してパラメータとみなした問題を,

equation

その双対問題を,

equation

とすると, equation,equation の最適値 equation を最小にするパラメータ equation は元の問題 equation最適解であり,また, equation実行可能解の集合を equation とすると,任意の equation に対して

equation (ベンダーズカットと呼ばれる)

が成り立つので, equation は, equation,equation を変数とする最適化問題

equation

最適解となる.

 一般に equation は無限集合なので,ベンダーズ分解法では, equation の有限部分集合 equation を用いて equation を解き,得られた最適解 equation をパラメータとして equation を解き,さらにその最適解 equation を加えて equation とする反復法が用いられ, equationequation として得られる.