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