ベンダース分解法

【べんだーすぶんかいほう (Benders decomposition method)】

行列 $A\,$, ベクトル $b\,$ と $c\,$, スカラー値関数 $f\,$, ベクトル値関数 $g\,$ と有界閉集合 $Y\,$ により定義される次のような制約付き問題に対する 2 段階の反復法.

min.	$c^{\top }x+f(y)\,$
s.t.	$Ax+g(y)\leq b,\,$
	$x\geq 0,\quad y\in Y.\,$

変数 $y\,$ を固定した線形計画問題の最適値関数を $\phi (y)\,$ とするとき, 等価な問題

min.	$\phi (y)\,$
s.t.	$y\in Y\cap \{y\,$　|　$\exists x\geq 0\,$　s.t.構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A x + g(y) \leq b\}\,}

の目的関数と実行可能集合が有限回の反復で確定できることに基づいている.