ベンダース分解法

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

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

\[ \begin{array}{ll}

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

\end{array} \]

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

\[ \begin{array}{ll}

       \mbox{min.} & \hspace*{-2mm} \phi(y)  \\
        \mbox{s.t.} &  \hspace*{-2mm} y \in Y \cap 
    \left\{ y \bigm| \exists \, x \geq 0 
              \mbox{ s.t. } A x + g(y) \leq b \right\} 

\end{array} \]

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