Discrete optimization

It turns a maximization problem (find the biggest flow) into an equivalent minimization problem (find the smallest bottleneck), so a single cut gives an instant, checkable certificate that a flow is already optimal — the same primal-dual idea that powers LP duality and branch-and-bound pruning.

Weak duality first. Take any $s$-$t$ cut $S$,$T$ with $s$ in $S$ and $t$ in $T$, and any feasible flow $|f|$. Every unit of flow leaving $s$ must eventually cross from $S$ to $T$ to reach $t$, and by conservation the net flow across the cut equals the total flow value. Since edges from $T$ back to $S$ can only reduce this net amount, the flow value can never exceed the sum of capacities of edges leaving $S$, i.e. $|f|$ is at most $\mathrm{cap}(S,T)$ for every cut.

Now run the Ford-Fulkerson procedure to completion: repeatedly find a path from $s$ to $t$ in the residual graph (remaining capacity plus reversible flow already sent) and push as much flow as the tightest edge on that path allows. Because capacities are assumed integer or rational and strictly decrease along the path used, this process terminates after finitely many augmentations.

At termination no augmenting path exists. Let $S$ be the set of nodes reachable from $s$ in the final residual graph, and $T$ the rest (so $t$ is in $T$ since no path reaches it). Every edge from $S$ to $T$ in the original network must be fully saturated (otherwise it would still have residual capacity, extending $S$), and every edge from $T$ back to $S$ must carry zero flow (otherwise its reverse residual edge would extend $S$).

Summing flow conservation over all nodes in $S$ shows the total flow value equals exactly the capacity of the saturated forward edges minus the zero backward flow, which is precisely $\mathrm{cap}(S,T)$ for this particular cut. Combined with the upper bound from the first paragraph, this cut achieves the minimum possible capacity, so the maximum flow value equals the minimum cut capacity.

Solving the LP relaxation is fast (polynomial time), so it gives a cheap upper bound to compare against the best integer solution found so far; if a branch cannot possibly beat that bound, exploring it further would be wasted work, which is exactly what makes branch-and-bound practical on large integer programs.

Let $x \in \mathbb{Z}^n_{\ge 0}$ denote the integer feasible set and $x \in \mathbb{R}^n_{\ge 0}$ the (larger) LP-relaxed feasible set of the same constraints $Ax \le b$. Because dropping the integrality requirement only removes constraints, every integer-feasible point is also LP-feasible, so the integer feasible set is a subset of the LP-relaxed feasible set.

Since both problems maximize the same linear objective $c^T x$ and the integer program's feasible set is contained in the LP relaxation's feasible set, the best value achievable over the smaller set cannot exceed the best value achievable over the larger set. Hence the LP relaxation optimum is an upper bound on the ILP optimum.

Branch-and-bound builds a search tree by picking a variable with a fractional value in the current LP-relaxed solution and creating two child subproblems that add $x_1 \le 1$ or $x_1 \ge 2$ respectively; every integer-feasible point satisfies exactly one of these two conditions, so no integer solution is ever lost by this split, and repeating the split keeps partitioning the space without gaps.

At each node, solving the LP relaxation of that subproblem gives an upper bound for every integer solution still reachable below it, by the same argument as above applied to the smaller constraint set. If this bound is no larger than the value of the best integer solution found anywhere in the tree so far, no descendant of this node can improve on the current best, so the whole subtree may be pruned while still guaranteeing the true optimum is found elsewhere in the tree.