ベンダーズ分解法

ベンダーズ分解法#

  • 読み: べんだーずぶんかいほう

  • 英名: Benders Decomposition Method

  • 別名: ベンダーズの分割法

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

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

(104)#\[\begin{split}(P) \begin{array}{ll} \min & c^\top x + f(y) \\ \mathrm{s.t.} & Ax + g(y) \ge b \\ & x \ge 0 \\ & y \in Y \end{array}\end{split}\]

の変数 \(y\) を固定してパラメータとみなした問題を

(105)#\[\begin{split}(P_y) \begin{array}{ll} \min & c^\top x + f(y) \\ \mathrm{s.t.} & Ax \ge b - g(y)\\ & x \ge 0 \end{array}\end{split}\]

その双対問題を

(106)#\[\begin{split}(D_y) \begin{array}{ll} \max & \left(b-g(y)\right)^\top u + f(y) \\ \mathrm{s.t.} & A^\top u \le c\\ & u \ge 0 \end{array}\end{split}\]

とすると,\((P_y)\)\((D_y)\) の最適値 \(z_y\) を最小にするパラメータ \(y^*\) は元の問題 \((P)\) の最適解であり,また,\((D_y)\) の実行可能解の集合を \(U\) とすると,任意の \(u \in U\) に対して \(\left(b-g(y)\right)^\top u + f(y) \le z_y\)(ベンダーズカットと呼ばれる)が成り立つので,\(y^*\) は,\(y\)\(z\) を変数とする最適化問題

(107)#\[\begin{split}(I_U) \begin{array}{ll} \min & z \\ \mathrm{s.t.} & \left(b-g(y)\right)^\top u + f(y) \le z, \ \forall{u} \in U\\ & y \in Y \end{array}\end{split}\]

の最適解となる.

一般に \(U\) は無限集合なので,ベンダーズ分解法では, \(U\) の有限部分集合 \(U_p\) を用いて \((I_{U_0})\) を解き,得られた最適解 \(y_p\) をパラメータとして \((D_{y_0})\) を解き,さらにその最適解 \(u_p\) を加えて \(U_{p+1} = U_p \cup \{u_p\}\) とする反復法が用いられ,\(y^*\)\(y_p \to y^*\) として得られる.