ベンダーズ分解法

ベンダーズ分解法（ベンダーズぶんかいほう、ベンダース分解法、テンプレート:Lang-en-short）とは、数理最適化において特別なブロック構造を持つ大規模線形計画問題に対する解法の一種である。このブロック構造はテンプレート:仮リンクにおいてしばしば見られる構造である。テンプレート:仮リンクに因んで名づけられた。

ベンダーズ分解法の戦略としては問題の分割と支配が挙げられる。すなわち、ベンダーズ分解法において元の問題の変数は二つの部分集合に分割され、第一段階として主問題を解く。続いてその情報を用いて部分問題を解く。もし、今解いた部分問題によって真の最適解が求まっていないことが判明すれば、ベンダーズカットテンプレート:Efnと呼ばれる新たな制約を主問題に加えて、再び主問題を解き直す。ベンダーズ分解法は反復によって新たな制約を付け加えて行く手法であることから、テンプレート:仮リンクに対する列生成法と対比して行生成的手法である。

方法

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

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

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

定式化

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

$\begin{array}{cccc}& \text{minimize}& & {𝐜}^{\mathrm{T}}𝐱+{𝐝}^{\mathrm{T}}𝐲\\ & \text{subject to}& & A𝐱+B𝐲\ge 𝐛\\ & & & 𝐲\in Y\\ & & & 𝐱\ge \mathrm{𝟎}\end{array}$

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

$\begin{array}{cccc}& \text{minimize}& & {𝐜}^{\mathrm{T}}𝐱+{𝐝}^{\mathrm{T}}\overline{𝐲}\\ & \text{subject to}& & A𝐱\ge 𝐛-B\overline{𝐲}\\ & & & 𝐱\ge \mathrm{𝟎}\end{array}$

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

$\begin{array}{cccc}& \text{maximize}& & (𝐛-B\overline{𝐲}{)}^{\mathrm{T}}𝐮+{𝐝}^{\mathrm{T}}\overline{𝐲}\\ & \text{subject to}& & A^{\mathrm{T}}𝐮\le 𝐜\\ & & & 𝐮\ge \mathrm{𝟎}\end{array}$

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

$\underset{𝐲\in Y}{\min }[{𝐝}^{\mathrm{T}}𝐲+\underset{𝐮\ge \mathrm{𝟎}}{\max }\{(𝐛-B𝐲{)}^{\mathrm{T}}𝐮\mid A^{\mathrm{T}}𝐮\le 𝐜\}].$

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

主問題の定式化

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

$\begin{array}{cccc}& \text{minimize}& & 𝐳\\ & \text{subject to}& & \{\text{cuts}\}\\ & & & 𝐲\in Y\\ \end{array}$

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

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

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

部分問題の定式化

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

$\begin{array}{cccc}& \text{maximize}& & (𝐛-B\overline{𝐲}{)}^{\mathrm{T}}𝐮+{𝐝}^{\mathrm{T}}\overline{𝐲}\\ & \text{subject to}& & A^{\mathrm{T}}𝐮\le 𝐜\\ & & & 𝐮\ge \mathrm{𝟎}\end{array}$

主問題は各反復において下界を与え、部分問題は上界を与える。$\overline{𝐲}$ の下で部分問題を解くことによって端点 $\overline{𝐮}$、テンプレート:仮リンクに含まれる端線 $\overline{𝐮}$ が求まるか、部分問題が実行不可能であることが判明する。

手続き

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

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

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

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

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

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

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

参考文献

• Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.
• テンプレート:Citation.

関連項目

• 列生成法
• テンプレート:仮リンク