ベンダーズ分解法

この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2020年9月）

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

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

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

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

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

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

${\displaystyle {\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}}}$

ただし、${\displaystyle A,B}$ は制約の係数行列を表し、${\displaystyle Y}$ は ${\displaystyle \mathbf {y} }$ の実行可能解を表す。今 ${\displaystyle \mathbf {y} }$ を一種の定数 ${\displaystyle \mathbf {\bar {y}} \in Y}$ とみなすと、問題は以下のように表される:

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

上記の問題の双対問題は以下の通りである:

${\displaystyle {\begin{aligned}&{\text{maximize}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}}$

元の問題の双対問題から、元の問題は以下のminmax型の問題に書き換えることができる:

${\displaystyle \min _{\mathbf {y} \in Y}\left[\mathbf {d} ^{\mathrm {T} }\mathbf {y} +\max _{\mathbf {u} \geq \mathbf {0} }\left\{(\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {u} \mid A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \right\}\right].}$

ベンダーズ分解法では反復手続きにおいてカット集合によって ${\displaystyle \mathbf {y} }$ を逐次求めて、双対問題の解を生成していく。minmax型の主問題では、${\displaystyle (\mathbf {u} ,\mathbf {y} )}$ の値のみ求まるが、最適な ${\displaystyle \mathbf {\bar {y}} }$ が求まれば、元の問題において ${\displaystyle \mathbf {\bar {y}} }$ を最適解で固定して解くことで最適な ${\displaystyle \mathbf {\bar {x}} }$ も求まる。

一段階目は規模の小さな最小化問題を解くことから始まる:

${\displaystyle {\begin{aligned}&{\text{minimize}}&&\mathbf {z} \\&{\text{subject to}}&&\{{\text{cuts}}\}\\&&&\mathbf {y} \in Y\\\end{aligned}}}$

初期における上記のカット集合は空である。上記の主問題を解くことで元の問題の最適解を推測していく。この問題の目的関数 ${\displaystyle \mathbf {z} }$ はいくらでも小さくとることができ、${\displaystyle \mathbf {y} }$ も任意の実行可能解とする。

カット集合は主問題の双対問題を解くことで各反復ごとに付け加えられる。カットが与えられることで、主問題において実行可能な ${\displaystyle \mathbf {y} }$ が求まっていくと同時に最適な ${\displaystyle \mathbf {y} }$ が最終的には求まる。各反復において ${\displaystyle \mathbf {y} }$、${\displaystyle \mathbf {z} }$、${\displaystyle \mathbf {x} }$ を交互に求めていく。

反復開始前は ${\displaystyle z}$ に関する制約が無いことから、各反復において ${\displaystyle z}$ に関する制約を追加していくことで、実行可能空間を縮小していく。もし、ある ${\displaystyle \mathbf {\bar {y}} }$ の下で主問題の最適値と限定問題の最適値が一致すれば、双対定理より最適解が求まったと判定することができる。

部分問題を解くことで主問題に ${\displaystyle \mathbf {\bar {y}} }$ を与え、minmax型の定式化から、その双対問題を解くことができる。 双対問題は以下のように定式化される:

${\displaystyle {\begin{aligned}&{\text{maximize}}&&(\mathbf {b} -B\mathbf {\bar {y}} )^{\mathrm {T} }\mathbf {u} +\mathbf {d} ^{\mathrm {T} }\mathbf {\bar {y}} \\&{\text{subject to}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}}$

主問題は各反復において下界を与え、部分問題は上界を与える。${\displaystyle \mathbf {\bar {y}} }$ の下で部分問題を解くことによって端点 ${\displaystyle \mathbf {\bar {u}} }$、後退錐（英語版）に含まれる端線 ${\displaystyle \mathbf {\bar {u}} }$ が求まるか、部分問題が実行不可能であることが判明する。

ベンダーズ分解法は主問題と部分問題を交互に解き続ける手続きを行う。各反復において主問題と部分問題の最適値は元の問題の最適値の上界と下界を与え、反復により上界と下界の差が縮まる。部分問題を解くことで主問題の制約条件を新たに求める、もしくは元の問題に最適解をもたないことを判定することができる。このことからベンダーズ分解法は問題が最適解を持たない、あるいは上界と下界のギャップが十分に小さくなれば終了する。各反復において、解 ${\displaystyle \mathbf {\bar {x}} }$ は主問題により求まった ${\displaystyle \mathbf {\bar {y}} }$ を定数とみなして限定問題を解くことで求まる。

より正確にはベンダーズ分解法は上界（上限）を ${\displaystyle \inf }$、下界（下限）を ${\displaystyle -\inf }$ とし、主問題のカット集合は空として始める。続いて手続きにより ${\displaystyle \mathbf {\bar {y}} \in Y}$ が選択される。反復手順を通じて上界と下界の差が ${\displaystyle \epsilon }$ より小さくなる、あるいは最適解が存在しないことが判明すればアルゴリズムは終了する。

各反復における1つの手続きは部分問題を解いて求まった ${\displaystyle \mathbf {\bar {y}} }$ を用いて上界を更新することから始まる。また部分問題を解くことで3つの事実が導かれる。

一つ目は、部分問題が非有界で最適値が得られない場合である。双対定理より、双対問題が非有界ならば、すなわち主問題は実行不可能である。これは ${\displaystyle \mathbf {\bar {y}} }$ の下では ${\displaystyle A\mathbf {x} +B\mathbf {\bar {y}} \geq \mathbf {b} }$ を満たすような ${\displaystyle \mathbf {x} \geq \mathbf {0} }$ が存在しないことを意味する。この ${\displaystyle \mathbf {\bar {y}} }$ は 主問題から得られた端線 ${\displaystyle \mathbf {\bar {u}} }$ を用いて部分問題の制約として ${\displaystyle (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} \leq \mathbf {0} }$ を追加する手続きを行う。

二つ目は、部分問題が実行不可能となる場合である。双対実行可能空間が空であり、この場合主問題は実行不可能あるいは非有界でいくらでも大きい値をとり得ることが考えられる。主問題がどちらの場合でも、ベンダーズ分解法は終了する。

三つ目は、部分問題に最適値が存在する場合である。線形計画問題の双対定理より、部分問題の最適値は元の問題において ${\displaystyle \mathbf {\bar {y}} }$ を固定した問題の最適値と一致する。このことから、部分問題の最適値が今までに見つかった上界より小さければ、上界は更新される。端点 ${\displaystyle \mathbf {\bar {u}} }$ が求まることで、主問題の新たな制約 ${\displaystyle z\geq (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} +\mathbf {d} ^{\mathrm {T} }\mathbf {y} }$ が目的関数に対して有効に働く。${\displaystyle \mathbf {\bar {y}} }$ が最適解でなければ、新たな制約の追加により主問題の目的関数 ${\displaystyle z}$ は厳密に増大する。

最後に、各反復において新たな制約を主問題に加えて、それによって得られる新たな最適解を生成する。得られた解 ${\displaystyle (\mathbf {\bar {y}} ,z)}$ によって下界は更新される。もし上界と下界の差が許容誤差 ${\displaystyle \epsilon }$ より小さくなれば、反復手順は終了し、${\displaystyle \mathbf {\bar {y}} }$ を元の問題に代入して、その問題を解くことで ${\displaystyle \mathbf {\bar {x}} }$ は求まる。許容誤差の条件を満たさなければ、反復は続けられる。

• Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.
• Lasdon, Leon S. (2002), Optimization Theory for Large Systems (reprint of the 1970 Macmillan ed.), Mineola, New York: Dover Publications, pp. xiii+523, MR1888251 .

• 列生成法
• FortSP（英語版）

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア