Benders分解法

数理最適化

はじめに

Benders分解法[1]とは，特定の構造をもつ大規模な数理最適化問題を解く手法のひとつです．Benders分解法では，解きたい最適化問題（原問題）を，それより小さな規模の上位問題と下位問題に分割し，これらの問題を交互に繰り返し解くことで原問題の最適解を求めます．Benders分解法は，原問題において一部の変数を固定すると，残りの変数に関する最適化問題が線形計画問題となるような問題に対して有効なアルゴリズムとして知られていますが，Benders分解法そのものを解説した日本語の情報源は数少なく，私の知るかぎり書籍[2]-[5]やウェブサイト[6][7]などに限られています．

本記事では，これらの書籍やウェブサイトを参考としつつも，個人的に重要と思うポイントを強調しつつ，Benders分解法の基本的な考え方やアルゴリズムについて自分なりに整理していきたいと思います．

本記事で議論する最適化問題の定式化

本記事では，以下のかたちで記述される最適化問題を題材とします：

\begin{align}
(\mathrm{P}): \underset{\boldsymbol{x}, \boldsymbol{y}}{\mathrm{minimize}} \, & \boldsymbol{c}^{\top}\boldsymbol{x} + f(\boldsymbol{y}) \tag{1} \\
\mathrm{subject\,to} \, &\boldsymbol{A}\boldsymbol{x} + \boldsymbol{g}(\boldsymbol{y}) \ge \boldsymbol{b}, \tag{2} \\
& \boldsymbol{x} \ge \boldsymbol{0}, \tag{3} \\
& \boldsymbol{y} \in \mathcal{Y}. \tag{4}
\end{align}

ただし，$\boldsymbol{x}, \boldsymbol{y}$は決定変数で，それぞれ$N$次元の非負連続変数ベクトル，集合$\mathcal{Y}$内の要素とします．$\boldsymbol{c}, \boldsymbol{b}, \boldsymbol{A}$は適当なサイズのベクトル，行列とします．また$f,\boldsymbol{g}$はそれぞれ$\mathcal{Y}$を定義域とする適当なスカラ，ベクトル関数とします．

Benders分解法の考えかた

最適化問題$(\mathrm{P})$に対して，その問題構造を利用した分解解法を考えます．$(\mathrm{P})$において，決定変数$\boldsymbol{y}$を適当に固定すると，残りの決定変数$\boldsymbol{x}$に関する最適化問題は線形計画問題となり，容易に解けるという点に着目します．そこで，$(\mathrm{P})$を解くアルゴリズムのプロトタイプとして，以下のような計算手順を考えます（最終的にはやや異なる計算手順となります）．

  • Step 1: 適当な上位問題を解き，$\bar{\boldsymbol{y}} \in \mathcal{Y}$を決定する．
  • Step 2: Step 1で決定した$\bar{\boldsymbol{y}}$のもとで，下位問題

\begin{align}
(\mathrm{P}(\bar{\boldsymbol{y}})): \underset{\boldsymbol{x}}{\mathrm{minimize}} \, & \boldsymbol{c}^{\top}\boldsymbol{x} \tag{5} \\
\mathrm{subject\,to} \, &\boldsymbol{A}\boldsymbol{x} + \boldsymbol{g}(\bar{\boldsymbol{y}}) \ge \boldsymbol{b}, \tag{6} \\
& \boldsymbol{x} \ge \boldsymbol{0}. \tag{7}
\end{align}

を解き，その解を$\boldsymbol{x}^{\ast}(\bar{\boldsymbol{y}})$とする．

  • Step 3: $(\boldsymbol{x}^{\ast}(\bar{\boldsymbol{y}}), \bar{\boldsymbol{y}})$について，最適性の証拠が得られていればこれを最適解として計算を終了する．そうでなければ下位問題の最適化結果をフィードバックしつつStep 1へ戻る．

上述の計算手順の構築にあたっては，以下の2点が技術的課題となります．

  • (a) 上位問題をどのように定式化するか？
  • (b) 下位問題の最適化結果を上位問題にどのようにフィードバックするか？

ここで，下位問題$(\mathrm{P}(\bar{\boldsymbol{y}}))$の双対問題

\begin{align}
(\mathrm{D}(\bar{\boldsymbol{y}})): \underset{\boldsymbol{\lambda}}{\mathrm{maximize}} \,& (\boldsymbol{b} - \boldsymbol{g}(\bar{\boldsymbol{y}}) )^{\top}\boldsymbol{\lambda} \tag{8} \\
\mathrm{subject\,to} \,& \boldsymbol{A}^{\top} \boldsymbol{\lambda} \le \boldsymbol{c}, \tag{9} \\
& \boldsymbol{\lambda} \ge \boldsymbol{0}. \tag{10}
\end{align}

を考え，$(\mathrm{P}(\bar{\boldsymbol{y}}))$と$(\mathrm{D}( \bar{\boldsymbol{y}}))$の実行可能解集合をそれぞれ

\begin{align}
\mathcal{X}(\bar{\boldsymbol{y}}) &= \left\{ \boldsymbol{x} \mid \boldsymbol{A}\boldsymbol{x} + \boldsymbol{g}(\bar{\boldsymbol{y}}) \ge \boldsymbol{b}, \boldsymbol{x} \ge \boldsymbol{0} \right\} \tag{11} \\
\mathcal{L} &= \{ \boldsymbol{\lambda} \mid \boldsymbol{A}^{\top} \boldsymbol{\lambda} \le \boldsymbol{c}, \boldsymbol{\lambda} \ge \boldsymbol{0} \} \tag{12}
\end{align}

と書くこととします．ここで，$(\mathrm{P}(\bar{\boldsymbol{y}}))$の実行可能解集合は上位問題の解$\bar{\boldsymbol{y}}$に依存するいっぽうで，$(\mathrm{D}( \bar{\boldsymbol{y}}))$の実行可能解集合は$\bar{\boldsymbol{y}}$に依存しないという点に注意します．

以降では$(\mathrm{P}(\bar{\boldsymbol{y}}))$を「下位主問題」，$(\mathrm{D}(\bar{\boldsymbol{y}}))$を「下位双対問題」とよぶこととし，$\mathcal{L} \neq \emptyset$とします．また，議論を簡単にするため，任意の上位問題の解$\bar{\boldsymbol{y}}\in \mathcal{Y}$に対して$(\mathrm{P}(\bar{\boldsymbol{y}}))$は実行可能解をもつと仮定します．本仮定のもとで，線形計画問題の弱双対定理より，任意の$\bar{\boldsymbol{y}}\in \mathcal{Y}, \boldsymbol{x} \in \mathcal{X}(\bar{\boldsymbol{y}})$と$\boldsymbol{\lambda} \in \mathcal{L}$に対し，
$$
(\boldsymbol{b} - \boldsymbol{g}(\bar{\boldsymbol{y}}))^{\top} \boldsymbol{\lambda} \le \boldsymbol{c}^{\top}\boldsymbol{x} \tag{13}
$$

がなりたちます．また，$(\mathrm{P}(\bar{\boldsymbol{y}}))$と$(\mathrm{D}( \bar{\boldsymbol{y}}))$の最適解をそれぞれ$\boldsymbol{x}^{\ast}(\bar{\boldsymbol{y}}),\boldsymbol{\lambda}^{\ast}(\bar{\boldsymbol{y}})$，最適値をそれぞれ$f^{\ast}(\mathrm{P}(\bar{\boldsymbol{y}})), f^{\ast}(\mathrm{D}(\bar{\boldsymbol{y}}))$としたとき，線形計画問題の強双対定理より
$$
f^{\ast}(\mathrm{D}(\bar{\boldsymbol{y}})) = (\boldsymbol{b} - \boldsymbol{g}(\bar{\boldsymbol{y}}))^{\top} \boldsymbol{\lambda}^{\ast}(\bar{\boldsymbol{y}}) = \boldsymbol{c}^{\top}\boldsymbol{x}^{\ast}(\bar{\boldsymbol{y}}) = f^{\ast}(\mathrm{P}(\bar{\boldsymbol{y}})) \tag{14}
$$

がなりたちます．ここで，(13)式と(14)式が示す性質

  • $(\mathrm{D}(\bar{\boldsymbol{y}}))$の任意の実行可能解の目的関数値は$(\mathrm{P}(\bar{\boldsymbol{y}}))$の任意の実行可能解の目的関数値以下である
  • $(\mathrm{D}(\bar{\boldsymbol{y}}))$と$(\mathrm{P}(\bar{\boldsymbol{y}}))$の最適値は一致する

を用いると，原問題$(\mathrm{P})$の最適な$\boldsymbol{y}$を求める上位問題は，$(\mathrm{D}(\bar{\boldsymbol{y}}))$を内包するかたちで
\begin{align}
(\mathrm{MP}): \underset{\boldsymbol{y}}{\mathrm{minimize}} \, & \max_{\boldsymbol{\lambda} \in \mathcal{L}}(\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}))^{\top} \boldsymbol{\lambda} + f(\boldsymbol{y}) \tag{15} \\
\mathrm{subject\,to} \, &\boldsymbol{y} \in \mathcal{Y}. \tag{16}
\end{align}

と定式化することができます．

上位問題$(\mathrm{MP})$の最適解$\boldsymbol{y}^{\ast}$が得られれば，$\boldsymbol{y}^{\ast}$のもとで下位主問題$(\mathrm{P}(\boldsymbol{y}^{\ast}))$を解くことで（$\boldsymbol{y}^{\ast}$とあわせて）$(\mathrm{P})$の最適解を得ることができます．そこで当面は$(\mathrm{MP})$を解く方法を考えることとします．

上位問題$(\mathrm{MP})$は，補助変数$\zeta \in \mathbb{R}$を用いて，
$$
\begin{align}
(\mathrm{MP}'): \underset{\zeta, \boldsymbol{y}}{\mathrm{minimize}} \, & \zeta + f(\boldsymbol{y}) \tag{17} \\
\mathrm{subject\,to} \, &(\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}))^{\top} \boldsymbol{\lambda}\le \zeta \quad(\forall \boldsymbol{\lambda} \in \mathcal{L}), \tag{18} \\
& \zeta > -\infty，\tag{19} \\
&\boldsymbol{y} \in \mathcal{Y}. \tag{20}
\end{align}
$$

と書き換えることができます．ただし$\mathcal{L}$の要素数は無限にあり，$(\mathrm{MP}')$を直接解くことは困難です．そこで，必要に応じて逐次$\boldsymbol{\lambda} \in \mathcal{L}$を求めて制約条件を追加していく計算手順を考えることとします．

上位問題$(\mathrm{MP}')$のうち，一部の$\mathcal{C} \subseteq \mathcal{L}$のみについて制約条件として考慮した緩和問題
$$
\begin{align}
(\mathrm{MP}'(\mathcal{C})): \underset{\zeta, \boldsymbol{y}}{\mathrm{minimize}} \, & \zeta + f(\boldsymbol{y}) \tag{21} \\
\mathrm{subject\,to} \, &(\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}))^{\top} \boldsymbol{\lambda}\le \zeta \quad(\forall \boldsymbol{\lambda} \in \mathcal{C}), \tag{22} \\
& \zeta > -\infty, \tag{23} \\
&\boldsymbol{y} \in \mathcal{Y}. \tag{24}
\end{align}
$$

を考え，その最適解を$(\zeta^{\ast}(\mathcal{C}), \boldsymbol{y}^{\ast}(\mathcal{C}))$とします．また，$\boldsymbol{y}^{\ast}(\mathcal{C})$のもとでの下位双対問題$(\mathrm{D}(\boldsymbol{y}^{\ast}(\mathcal{C})))$の最適解を$\boldsymbol{\lambda}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C}))$とします．$(\mathrm{D}(\boldsymbol{y}^{\ast}(\mathcal{C})))$は，$\boldsymbol{\lambda} \in \mathcal{L}$のなかで$(\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}^{\ast}(\mathcal{C})))^{\top} \boldsymbol{\lambda}$を最大化する問題ですので，
$$
(\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}^{\ast}(\mathcal{C})))^{\top} \boldsymbol{\lambda}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C})) \le \zeta^{\ast}(\mathcal{C}) \tag{25}
$$

がなりたつならば，緩和問題$(\mathrm{MP}'(\mathcal{C}))$の解$(\zeta^{\ast}(\mathcal{C}), \boldsymbol{y}^{\ast}(\mathcal{C}))$は，(18)式を満足することから$(\mathrm{MP})$の最適解となります．なおこの場合，上述のとおり$\boldsymbol{y}^{\ast}(\mathcal{C})$のもとで下位主問題$(\mathrm{P}(\boldsymbol{y}^{\ast}(\mathcal{C})))$を解くことで$(\mathrm{P})$の最適解を得ることができます．いっぽう，
$$
(\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}^{\ast}(\mathcal{C})))^{\top} \boldsymbol{\lambda}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C})) > \zeta^{\ast}(\mathcal{C}) \tag{26}
$$

であるならば，$(\zeta^{\ast}(\mathcal{C}), \boldsymbol{y}^{\ast}(\mathcal{C}))$は(18)式を満足しないため，$\boldsymbol{\lambda}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C}))$を$\mathcal{C}$の要素として加え（つまり新しい制約条件を追加し），$(\mathrm{MP}'(\mathcal{C}))$を解きなおす必要があります．

Benders分解法とは，以上の考え方をもとに，集合$\mathcal{C}$を更新しつつ，上位問題の緩和問題$(\mathrm{MP}'(\mathcal{C}))$と下位双対問題$(\mathrm{D}(\boldsymbol{y}^{\ast}(\mathcal{C})))$を交互に解くことで上位問題$(\mathrm{MP})$の最適解$\boldsymbol{y}^{\ast}$を求め，最後に$\boldsymbol{y}^{\ast}$のもとで下位主問題$(\mathrm{P}(\boldsymbol{y}^{\ast}))$を解くことで（$\boldsymbol{y}^{\ast}$とあわせて）原問題$(\mathrm{P})$の最適解$(\boldsymbol{x}^{\ast}, \boldsymbol{y}^{\ast})$を求めるアルゴリズムとなります．

Benders分解法のアルゴリズム

前節の議論を踏まえ，Benders分解法のアルゴリズムを以下のとおりまとめます．

  • Step 1（初期化）: $\mathcal{C} = \emptyset$とする．
  • Step 2（上位緩和問題最適化）:上位問題の緩和問題

$$
\begin{align}
(\mathrm{MP}'(\mathcal{C})): \underset{\zeta, \boldsymbol{y}}{\mathrm{minimize}} \, & \zeta + f(\boldsymbol{y}) \tag{27} \\
\mathrm{subject\,to} \, &(\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}))^{\top} \boldsymbol{\lambda}\le \zeta \quad(\forall \boldsymbol{\lambda} \in \mathcal{C}), \tag{28}\\
& \zeta > -\infty, \tag{29}\\
&\boldsymbol{y} \in \mathcal{Y}. \tag{30}
\end{align}
$$

を解き，その最適解を$(\zeta^{\ast}(\mathcal{C}), \boldsymbol{y}^{\ast}(\mathcal{C}))$とする．

  • Step 3（下位双対問題最適化）: Step 2で求めた$\boldsymbol{y}^{\ast}(\mathcal{C})$のもとで，下位双対問題

$$
\begin{align}
(\mathrm{D}(\boldsymbol{y}^{\ast}(\mathcal{C}))): \underset{\boldsymbol{\lambda}}{\mathrm{maximize}} \,& (\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}^{\ast}(\mathcal{C})) )^{\top}\boldsymbol{\lambda} \tag{31}\\
\mathrm{subject\,to} \,& \boldsymbol{A}^{\top} \boldsymbol{\lambda} \le \boldsymbol{c}, \tag{32} \\
& \boldsymbol{\lambda} \ge \boldsymbol{0}. \tag{33}
\end{align}
$$

を解き，その最適解を$\boldsymbol{\lambda}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C}))$とする．

  • Step 4（制約条件追加）: Step 2で求めた$\zeta^{\ast}(\mathcal{C})$とStep 3で求めた$\boldsymbol{\lambda}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C}))$が

$$
(\boldsymbol{b} - \boldsymbol{g}(\boldsymbol{y}^{\ast}(\mathcal{C})))^{\top} \boldsymbol{\lambda}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C})) \le \zeta^{\ast}(\mathcal{C}) \tag{34}
$$

を満たすならばStep 5へ進む．そうでないならば，
$$
\mathcal{C} := \mathcal{C} \cup \{ \boldsymbol{\lambda}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C})) \} \tag{35}
$$

としてStep 2へ進む．

  • Step 5（下位主問題最適化）: Step 2で求めた$\boldsymbol{y}^{\ast}(\mathcal{C})$のもとで，下位主問題

$$
\begin{align}
(\mathrm{P}(\boldsymbol{y}^{\ast}(\mathcal{C}))): \underset{\boldsymbol{x}}{\mathrm{minimize}} \, & \boldsymbol{c}^{\top}\boldsymbol{x} \tag{36} \\
\mathrm{subject\,to} \, &\boldsymbol{A}\boldsymbol{x} + \boldsymbol{g}(\boldsymbol{y}^{\ast}(\mathcal{C})) \ge \boldsymbol{b}, \tag{37} \\
& \boldsymbol{x} \ge \boldsymbol{0}. \tag{38}
\end{align}
$$

を解き，その最適解を$\boldsymbol{x}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C}))$とする．$(\boldsymbol{x}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C})), \boldsymbol{y}^{\ast}(\mathcal{C}))$を最適化問題$(\mathrm{P})$の最適解として出力し，アルゴリズムを終了する．

補足

近似解法としてのBenders分解法

前節のアルゴリズムを実行することで，適当な仮定のもとで，有限回の反復で原問題$(\mathrm{P})$の最適解が求まることが示されています（文献[1]-[3]など）．ただし，計算時間の制約などから，途中で計算を打ち切る必要が生じる場合も考えられます．このような場合，アルゴリズムのStep 3において，下位双対問題$(\mathrm{D}(\boldsymbol{y}^{\ast}(\mathcal{C})))$とあわせて下位主問題$(\mathrm{P}(\boldsymbol{y}^{\ast}(\mathcal{C})))$も解いておくことで，毎回の反復において$(\mathrm{P})$の実行可能解を得ることができます．ここで得られる実行可能解$(\boldsymbol{x}^{\ast}(\boldsymbol{y}^{\ast}(\mathcal{C})), \boldsymbol{y}^{\ast}(\mathcal{C}))$に対して，
$$
\begin{align}
\boldsymbol{c}^{\top}\boldsymbol{x}(\boldsymbol{y}^{\ast}(\mathcal{C})) + f(\boldsymbol{y}^{\ast}(\mathcal{C})) \tag{39}
\end{align}
$$

は原問題$(\mathrm{P})$の上界値をあたえます．また，Step 1で計算される上位問題の緩和問題$(\mathrm{MP}'(\mathcal{C}))$の最適値は$(\mathrm{P})$の下界値をあたえます．これらは計算の反復に対してそれぞれ非増加，非減少となります．よって，各反復におけるギャップ（上界値と下界値の差）は，
$$
\begin{align}
\boldsymbol{c}^{\top}\boldsymbol{x}(\boldsymbol{y}^{\ast}(\mathcal{C})) - \zeta^{\ast}(\mathcal{C}) \tag{40}
\end{align}
$$

で計算でき，最適解に対してどの程度の近似解が得られているかを逐次チェックすることができます．

下位問題が実行不可能となりうる問題に対するBenders分解法

本記事では「上位問題の解によらず下位主問題・双対問題が実行可能解をもつ」という比較的強い仮定のもとで議論を進めましたが，上位問題の解によっては下位主問題が実行不可能となる場合も考えられます．そのような場合に対するBenders分解法については文献[1]-[3]などに詳述されています．

下位問題がさらに複数の問題に分割できる場合

Benders分解法がとくに威力を発揮する問題の例として「上位問題においていくつかの決定変数を固定することによって，下位問題が複数の小さな問題に分割できる」構造の問題があげられます．具体例として，以下の最適化問題を考えます．
$$
\begin{align}
(\mathrm{Pm}): \underset{\{\boldsymbol{x}_{i}\}_{i\in \mathcal{I}}, \boldsymbol{y}}{\mathrm{minimize}} \, & \sum_{i \in \mathcal{I}}\boldsymbol{c}_{i}^{\top}\boldsymbol{x}_{i} + f(\boldsymbol{y}) \tag{41} \\
\mathrm{subject\,to} \, &\boldsymbol{A}_{i}\boldsymbol{x}_{i} + \boldsymbol{g}_{i}(\boldsymbol{y}) \ge \boldsymbol{b}_{i} \quad (i \in \mathcal{I}), \tag{42} \\
& \boldsymbol{x}_{i} \ge \boldsymbol{0}\quad (i \in \mathcal{I}), \tag{43} \\
& \boldsymbol{y} \in \mathcal{Y}. \tag{44}
\end{align}
$$

ただし$\mathcal{I}$は有限個の要素をもつ添字集合とします．本問題をBenders分解法で解く際，上位問題において$\boldsymbol{y} = \bar{\boldsymbol{y}}$と固定すると，下位主問題は
$$
\begin{align}
(\mathrm{Pm}(\bar{\boldsymbol{y}})): \underset{\{\boldsymbol{x}_{i}\}_{i\in \mathcal{I}}}{\mathrm{minimize}} \, & \sum_{i \in \mathcal{I}}\boldsymbol{c}_{i}^{\top}\boldsymbol{x}_{i} \tag{45} \\
\mathrm{subject\,to} \, &\boldsymbol{A}_{i}\boldsymbol{x}_{i} + \boldsymbol{g}_{i}(\boldsymbol{\bar{y}}) \ge \boldsymbol{b}_{i} \quad (i \in \mathcal{I}), \tag{46} \\
& \boldsymbol{x}_{i} \ge \boldsymbol{0}\quad (i \in \mathcal{I}). \tag{47}
\end{align}
$$

となり，目的関数，制約条件ともに添字$i$ごとに独立していることがわかります．すなわち，$(\mathrm{Pm}(\bar{\boldsymbol{y}}))$の最適解は，添字$i$に関する最適化問題
$$
\begin{align}
(\mathrm{Pm}_{i}(\bar{\boldsymbol{y}})): \underset{\boldsymbol{x}_{i}}{\mathrm{minimize}} \, & \boldsymbol{c}_{i}^{\top}\boldsymbol{x}_{i} \tag{48} \\
\mathrm{subject\,to} \, &\boldsymbol{A}_{i} \boldsymbol{x}_{i} + \boldsymbol{g}(\bar{\boldsymbol{y}}) \ge \boldsymbol{b}_{i}, \tag{49} \\
& \boldsymbol{x}_{i} \ge \boldsymbol{0}. \tag{50}
\end{align}
$$

を$i \in \mathcal{I}$に対して個別に解き，各問題の最適解を集約することで得られます．$(\mathrm{Pm}_{i}(\bar{\boldsymbol{y}})) (i \in \mathcal{I})$は$(\mathrm{Pm}(\bar{\boldsymbol{y}}))$よりも小さい最適化問題であり解きやすく，さらに互いに独立していることから，これらを並列計算で解くことも可能です．同様に，下位双対問題
$$
\begin{align}
(\mathrm{Dm}_{i}(\bar{\boldsymbol{y}})): \underset{\boldsymbol{\lambda}_{i}}{\mathrm{maximize}} \,& (\boldsymbol{b}_{i} - \boldsymbol{g}_{i}(\bar{\boldsymbol{y}}) )^{\top}\boldsymbol{\lambda}_{i} \tag{51} \\
\mathrm{subject\,to} \,& \boldsymbol{A}_{i}^{\top} \boldsymbol{\lambda}_{i} \le \boldsymbol{c}_{i}, \tag{52} \\
& \boldsymbol{\lambda_{i}} \ge \boldsymbol{0}. \tag{53}
\end{align}
$$

についても添字$i$ごとに個別に解くことができ，前節のアルゴリズムのStep 4（制約条件追加）は，$(\mathrm{Dm}_{i}(\bar{\boldsymbol{y}}))$の最適解を集約するかたちで実現できます．

おわりに

本記事ではBenders分解法の基本的な考え方とアルゴリズムについて，自分なりに整理してみました．個人的には，「下位問題の双対問題の実行解集合が上位問題の解に依存しない」 という問題構造の性質を活用する点がBenders分解法の一番重要なポイントであると考えています．

Benders分解法は線形計画問題に対する双対問題・双対定理を最大限に利用したアルゴリズムになっており，これらの理解がほぼ前提となっています．いっぽうでBenders分解法は，アルゴリズム設計に双対問題・双対定理を直接応用する好例であり，これらについて理解を深めるよい題材であるとも考えています．

本記事が少しでもご参考となれば幸いでございます．

参考文献