ベンダーズ分解法とは？わかりやすく解説

ベンダーズ分解法（ベンダーズぶんかいほう、ベンダース分解法、英: Benders decomposition, Benders' decomposition）とは、数理最適化において特別なブロック構造を持つ大規模線形計画問題に対する解法の一種である。このブロック構造は確率計画法（英語版）においてしばしば見られる構造である。ヤコブス・F・ベンダーズ（英語版）に因んで名づけられた。

ベンダーズ分解法の戦略としては問題の分割と支配が挙げられる。すなわち、ベンダーズ分解法において元の問題の変数は二つの部分集合に分割され、第一段階として主問題を解く。続いてその情報を用いて部分問題を解く。もし、今解いた部分問題によって真の最適解が求まっていないことが判明すれば、ベンダーズカット^{[注釈 1]}と呼ばれる新たな制約を主問題に加えて、再び主問題を解き直す。ベンダーズ分解法は反復によって新たな制約を付け加えて行く手法であることから、ダンツィーグ・ウルフ分解法（英語版）に対する列生成法と対比して行生成的手法である。

方法

問題は二つ以上の段階から構成されている。ある段階における問題はそれ以前の段階によって得られた情報を用いて手続きが行われる。最初の段階で解く問題はその問題に関する情報を使用せずに解くことから始める。第一段階では主問題を解く。続いて部分問題を解く。そして、その部分問題で得られた解の情報を主問題に加える。もし、部分問題によって得られた解が最適性の条件を満たさなければ、主問題に制約として加える。そして主問題を再び解き直す。

主問題の制約は部分問題を解くことで得られる情報から構成される凸集合によって表現される。主問題の実行可能空間は新たに制約が加われば縮小されるため、各反復において主問題を解き直すことで元の問題の下界を得られる。

ベンダーズ分解法は大規模なブロック角構造を持つ問題に対して適用されている。

定式化

以下のような構造を持つ問題が与えられたとする:

{\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} \\&{\text{subject to}}&&A\mathbf {x} +B\mathbf {y} \geq \mathbf {b} \\&&&\mathbf {y} \in Y\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}

カテゴリ（最適化 • アルゴリズム） • ソフトウェア

[注釈 1]

一般	バリア関数ペナルティ関数法
微分可能	ラグランジュの未定乗数法拡張ラグランジュ関数法逐次二次計画法逐次線形計画法

ベンダーズ分解法とは？ わかりやすく解説

ベンダーズ分解法

方法

定式化

急上昇のことば

「ベンダーズ分解法」の関連用語

ベンダーズ分解法とは？わかりやすく解説