ベンダーの分解

ベンダー分解（またはベンダーの分解）は、特殊なブロック構造を持つ非常に大規模な線形計画問題の解決を可能にする数理計画法の手法です。このブロック構造は、不確実性が通常シナリオで表現されるため、確率計画法などのアプリケーションでよく使用されます。この手法は、ジャック・F・ベンダーにちなんで名付けられました。

ベンダー分解の背後にある戦略は、分割統治法として要約できます。つまり、ベンダー分解では、元の問題の変数が 2 つのサブセットに分割され、第 1 段階のマスター問題が最初の変数セットに対して解決され、2 番目の変数セットの値が、与えられた第 1 段階のソリューションに対する第 2 段階のサブ問題で決定されます。サブ問題で、固定された第 1 段階の決定が実際には実行不可能であると判断された場合、いわゆるベンダー カットが生成されてマスター問題に追加され、カットが生成されなくなるまでマスター問題が再解決されます。ベンダー分解は、ソリューションに向かって進むにつれて新しい制約を追加するため、このアプローチは「行生成」と呼ばれます。対照的に、ダンツィヒ-ウルフ分解では「列生成」が使用されます。

2 つ以上のステージで発生する問題を想定します。後者のステージの決定は、前のステージの結果に依存します。第 1 ステージの決定は、後続のステージの決定に従って、最適性に関する事前の知識がなくても実行できます。この第 1 ステージの決定がマスター問題です。その後のステージは、個別のサブ問題として分析できます。これらのサブ問題からの情報は、マスター問題に返されます。サブ問題の制約に違反した場合は、それをマスター問題に追加できます。その後、マスター問題が再度解決されます。

マスター問題は、サブ問題から収集された情報によってさらに制約される初期の凸集合を表します。実行可能な空間は情報が追加されるにつれて縮小するだけなので、マスター関数の目的値は、全体の問題の目的関数の下限を提供します。

ベンダー分解は、主にブロック対角構造を持つ問題に適用できます。

次のような構造の問題を想定します。

${\displaystyle {\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} } \mathbf {y} \\&{\text{対象}}&&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 {\bar {y}} \in Y}$

${\displaystyle {\begin{aligned}&{\text{minimize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} +\mathbf {d} ^{\mathrm {T} } \mathbf {\bar {y}} \\&{\text{対象}}&&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{対象}}&&A^{\mathrm {T} }\mathbf {u} \leq \mathbf {c} \\&&&\mathbf {u} \geq \mathbf {0} \end{aligned}}}$

残差問題の双対表現を使用すると、元の問題は同等のミニマックス問題として書き直すことができる。

${\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} }$${\displaystyle (\mathbf {u} ,\mathbf {y} )}$${\displaystyle \mathbf {\bar {y}} }$${\displaystyle \mathbf {\bar {x}} }$${\displaystyle \mathbf {\bar {y}} }$

第一段階の問題に対する決定は、より小さな最小化問題によって記述できる。

${\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 \mathbf {\bar {y}} }$

サブ問題は、マスター問題に対する 提案された解決策を考慮し、ミニマックス定式化から内部最大化問題を解きます。内部問題は、双対表現を使用して定式化されます。${\displaystyle \mathbf {\bar {y}} }$

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

各反復の最初のステップは、 の最新の値を使用してサブ問題を解決することにより上限を更新することから始まります。サブ問題を解決した場合、3 つの結果が考えられます。 ${\displaystyle \mathbf {\bar {y}} }$

最初のケースでは、サブ問題の目的値は 上で無制限です。双対性理論により、双対問題が無制限の目的を持つ場合、対応する主問題は実行不可能です。これは、 の選択が任意の に対してを満たさないことを意味します。このソリューションは、サブ問題が無制限の目的を持つことを証明する極端な光線を取り、 を主張する制約をマスターに追加することで、マスター問題から削除できます。 ${\displaystyle \mathbf {\bar {y}} }$${\displaystyle A\mathbf {x} +B\mathbf {\bar {y}} \geq \mathbf {b} }$${\displaystyle \mathbf {x} \geq \mathbf {0} }$${\displaystyle \mathbf {\bar {u}} }$${\displaystyle (\mathbf {b} -B\mathbf {y} )^{\mathrm {T} }\mathbf {\bar {u}} \leq \mathbf {0} }$

2 番目のケースでは、サブ問題は実行不可能です。問題の双対実行可能空間が空であるため、元の問題が実行不可能であるか、主問題に目的値が下方に無制限であることを証明する光線が存在します。どちらの場合も、手順は終了します。

3 番目のケースでは、サブ問題には有限の最適解があります。線形計画法の双対理論により、サブ問題の最適値は、 の選択に制約された元の問題の最適値に等しくなります。これにより、サブ問題の最適解の値が現在の上限よりも優れている場合、上限をサブ問題の最適解の値に更新できます。最適な極値点 が与えられると、 を主張することにより、マスター問題でこの特定の解の下での目的値を考慮することを要求する新しい制約も生成されます 。の選択が最適でなかった場合、これにより、マスター問題の解におけるの値が確実に増加します。 ${\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 z}$${\displaystyle \mathbf {\bar {y}} }$${\displaystyle \mathbf {\bar {y}} }$

最後に、各反復の最後の部分では、新しい制約を使用してマスター問題を解くことにより、マスター問題に対する新しいソリューションを作成します。新しいソリューションは、下限を更新するために使用されます。最適な上限と下限の差が より小さい場合、手順は終了し、 を修正して主残差問題を解くことで の値が決定されます。それ以外の場合、手順は次の反復に進みます。 ${\displaystyle (\mathbf {\bar {y}} ,z)}$${\displaystyle \epsilon }$${\displaystyle \mathbf {\bar {x}} }$${\displaystyle \mathbf {\bar {y}} }$

• FortSPソルバーは、確率的計画問題を解くためにベンダー分解を使用します。

• Benders, JF (1962年9月)、「混合変数プログラミング問題を解くための分割手順」、Numerische Mathematik 4(3): 238–252。
• ラスドン、レオン S. (2002)、大規模システムの最適化理論(1970 年マクミラン版の再版)、ミネオラ、ニューヨーク:ドーバー出版、pp. xiii+523、MR  1888251。