離散最適化

この定理は、最大化問題(最大の流れを求める)を、それと等価な最小化問題(最小のボトルネックを求める)に変換する。そのため、一つのカットを示すだけで、その流れがすでに最適であることを即座に検証できる証明となる。これはLP双対性や分枝限定法での枝刈りを支える主双対の考え方と同じである。

まず弱双対性を示す。$s$ が $S$ に、$t$ が $T$ に属する任意の $s$-$t$ カット $S$,$T$ と、任意の実行可能フロー $|f|$ を考える。$s$ から出るすべての単位のフローは、最終的に $t$ に到達するために $S$ から $T$ へ渡らなければならず、保存則により、カットを横切る正味フローはフローの総量に等しい。$T$ から $S$ へ戻る辺はこの正味量を減らすことしかできないため、フロー値は $S$ から出る辺の容量の合計を決して超えない。すなわち任意のカットについて $|f|$ は $\mathrm{cap}(S,T)$ 以下である。

次にFord-Fulkersonアルゴリズムを最後まで実行する:残余グラフ(残り容量とすでに送ったフローの逆転可能分)の中で $s$ から $t$ への経路を繰り返し見つけ、その経路上で最も細い辺が許す分だけフローを押し出す。容量は整数または有理数であり、使用するたびに経路上で真に減少するため、この過程は有限回の増加で終了する。

終了時には増加経路が存在しない。最終的な残余グラフで $s$ から到達可能なノードの集合を $S$、残りを $T$ とする(到達する経路がないため、$t$ は $T$ に属する)。元のネットワークで $S$ から $T$ へのすべての辺は完全に飽和していなければならず(そうでなければ残余容量が残り、$S$ がさらに広がる)、$T$ から $S$ へのすべての辺のフローはゼロでなければならない(そうでなければその逆残余辺が $S$ を広げる)。

$S$ 内のすべてのノードについてフロー保存則を足し合わせると、総フロー値は飽和した順方向辺の容量の合計からゼロの逆方向フローを引いたものに正確に等しく、これはこのカットに対する $\mathrm{cap}(S,T)$ そのものである。最初の段落で示した上界と合わせると、このカットは達成可能な最小容量を実現しており、したがって最大フロー値は最小カット容量に等しい。

LP緩和を解くのは高速(多項式時間)であるため、これまでに見つかった最良の整数解と比較するための安価な上界を与える。ある枝がその上界を超えられないなら、それ以上探索するのは無駄な作業であり、これこそが大規模な整数計画に対して分枝限定法を実用的にしている理由である。

整数実行可能集合を $x \in \mathbb{Z}^n_{\ge 0}$、同じ制約 $Ax \le b$ に対する(より大きな)LP緩和の実行可能集合を $x \in \mathbb{R}^n_{\ge 0}$ とする。整数条件を外すことは制約を減らすだけなので、整数実行可能な点はすべてLP実行可能でもあり、したがって整数実行可能集合はLP緩和の実行可能集合の部分集合である。

両方の問題が同じ線形目的関数 $c^T x$ を最大化し、整数計画の実行可能集合がLP緩和の実行可能集合に含まれるため、小さい集合上で達成できる最良値は大きい集合上で達成できる最良値を超えることはできない。したがってLP緩和の最適値は整数計画の最適値の上界となる。

分枝限定法は、現在のLP緩和解の中で分数値をとる変数を一つ選び、それぞれ $x_1 \le 1$ または $x_1 \ge 2$ を追加した二つの子部分問題を作ることで探索木を構築する。すべての整数実行可能点はこの二つの条件のどちらか一方を必ず満たすため、この分割によって整数解が失われることはなく、分割を繰り返しても空間は隙間なく分割され続ける。

各ノードで、その部分問題のLP緩和を解くと、より小さな制約集合に対して上と同じ議論を適用することで、その下でまだ到達可能なすべての整数解に対する上界が得られる。この上界が、木の中でこれまでに見つかった最良の整数解の値以下であれば、このノードのどの子孫もそれを改善できないため、木の他の場所で真の最適解が見つかることを保証したまま、この部分木全体を刈り取ってよい。