Editing Max-flow min-cut theorem (section)

==Linear program formulation==
The max-flow problem and min-cut problem can be formulated as two [[Dual linear program|primal-dual]] [[Linear programming|linear programs]].<ref>{{Cite web| url= http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf|title=Lecture 15 from CS261: Optimization|last=Trevisan|first=Luca}}</ref>

{| class="wikitable" rules="" cellspacing="0" cellpadding="0" border="0"
!
! style="border: 1px solid darkgrey;"|
Max-flow (Primal)
! style="border-top: 1px solid darkgrey; border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey;"|
Min-cut (Dual)
|-
|'''variables'''
| style="border-right: 1px solid darkgrey; border-left: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
<math>f_{uv}</math> <math>\forall (u,v)\in E</math> ''[two variables per edge, one in each direction]''
| style="border-right: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
<math>d_{uv}</math> <math>\forall (u,v)\in E</math> ''[a variable per edge]''

<math>z_{v}</math> <math>\forall v\in V\setminus \{s,t\}</math> ''[a variable per non-terminal node]''
|-
|'''objective'''
| style="border-right: 1px solid darkgrey; border-left: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
maximize <math>\sum\nolimits_{v: (s,v)\in E} f_{sv}</math>

''[max total flow from source]''
| style="border-right: 1px solid darkgrey; padding: 1em;" valign="top" align="left" |
minimize <math>\sum\nolimits_{(u,v) \in E } c_{uv}d_{uv}</math>

''[min total capacity of edges in cut]''
|-
|'''constraints'''
| style="border-left: 1px solid darkgrey; border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey; padding: 1em;" valign="top" |
subject to 

:<math>\begin{align} 
f_{uv} & \leq c_{uv} && \forall (u, v) \in E \\
\sum_{u} f_{uv} - \sum_{w} f_{vw} & = 0 && v \in V\setminus \{s,t\} 
\end{align}</math>

''[a constraint per edge and a constraint per non-terminal node]''
| style="border-bottom: 1px solid darkgrey; border-right: 1px solid darkgrey; padding: 1em" valign="top" |
subject to

:<math>\begin{align}
d_{uv} - z_u + z_v & \geq 0 && \forall (u, v) \in E, u\neq s, v\neq t \\
d_{sv} + z_v & \geq 1 && \forall (s, v) \in E, v\neq t \\
d_{ut} - z_u & \geq 0 && \forall (u, t) \in E,u\neq s \\
d_{st} & \geq 1 && \text{if } (s, t) \in E
\end{align}</math>

''[a constraint per edge]''
|-
|'''sign constraints'''
|<math>\begin{align} 
f_{uv} & \geq 0 && \forall (u, v) \in E\\
\end{align}</math>
|<math>\begin{align}
d_{uv} & \geq 0 && \forall (u, v) \in E \\
z_v & \in \R && \forall v \in V\setminus \{s,t\} 
\end{align}</math>
|}

The max-flow LP is straightforward. The dual LP is obtained using the algorithm described in [[dual linear program]]: the variables and sign constraints of the dual correspond to the constraints of the primal, and the constraints of the dual correspond to the variables and sign constraints of the primal. The resulting LP requires some explanation. The interpretation of the variables in the min-cut LP is:

:<math>d_{uv} = \begin{cases} 1, & \text{if }u \in S \text{ and } v \in T \text{ (the edge } uv \text{ is in the cut) }
\\ 0, & \text{otherwise} \end{cases}</math> 

:<math>z_{v} = \begin{cases} 1, & \text{if } v \in S \\ 0, & \text{otherwise} \end{cases}</math>

The minimization objective sums the capacity over all the edges that are contained in the cut.

The constraints guarantee that the variables indeed represent a legal cut:<ref>{{Cite web|url=http://u.cs.biu.ac.il/~rosenfa5/Alg2/LP.ppt|title=LP min-cut max-flow presentation|last=Keller|first=Orgad}}</ref>

* The constraints <math>d_{uv} - z_u + z_v \geq 0</math> (equivalent to <math>d_{uv} \geq z_u - z_v </math>) guarantee that, for non-terminal nodes ''u,v'', if ''u'' is in ''S'' and ''v'' is in ''T'', then the edge (''u'',''v'') is counted in the cut (<math>d_{uv} \geq 1 </math>).
* The constraints <math>d_{sv} + z_v \geq 1</math> (equivalent to <math>d_{sv} \geq 1 - z_v </math>) guarantee that, if ''v'' is in ''T'', then the edge ''(s,v)'' is counted in the cut (since ''s'' is by definition in ''S'').
* The constraints <math>d_{ut} - z_u \geq 0</math> (equivalent to <math>d_{ut} \geq z_u </math>) guarantee that, if ''u'' is in ''S'', then the edge ''(u,t)'' is counted in the cut (since ''t'' is by definition in ''T'').

Note that, since this is a minimization problem, we do not have to guarantee that an edge is ''not'' in the cut - we only have to guarantee that each edge that should be in the cut, is summed in the objective function.

The equality in the '''max-flow min-cut theorem''' follows from the [[Dual linear program|strong duality theorem in linear programming]], which states that if the primal program has an optimal solution, ''x''*, then the dual program also has an optimal solution, ''y''*, such that the optimal values formed by the two solutions are equal.