Max-flow Min-cut Theorem - Linear Program Formulation

Linear Program Formulation

The max-flow problem and min-cut problem can be formulated as two primal-dual linear programs.

Max-flow (Primal)

Min-cut (Dual)

maximize

minimize

subject to


\begin{array}{rclr} f_{ij} & \leq & c_{ij} & (i, j) \in E \\
\sum_{j: (j, i) \in E} f_{ji} - \sum_{j: (i, j) \in E} f_{ij} & \leq & 0 & i \in V, i \neq s,t \\
\nabla_s + \sum_{j: (j, s) \in E} f_{js} - \sum_{j: (s, j) \in E} f_{sj} & \leq & 0 & \\
\nabla_t + \sum_{j: (j, t) \in E} f_{jt} - \sum_{j: (t, j) \in E} f_{tj} & \leq & 0 & \\
f_{ij} & \geq & 0 & (i, j) \in E\\
\end{array}

subject to

\begin{array}{rclr}
d_{ij} - p_i + p_j & \geq & 0 & (i, j) \in E \\
p_s & = & 1 & \\
p_t & = & 0 & \\
p_i & \geq & 0 & i \in V \\
d_{ij} & \geq & 0 & (i, j) \in E
\end{array}

The equality in the max-flow min-cut theorem follows from the 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.

Read more about this topic:  Max-flow Min-cut Theorem

Famous quotes containing the words program and/or formulation:

    On our streets it is the sight of a totally unknown face or figure which arrests the attention, rather than, as in big cities, the strangeness of occasionally seeing someone you know.
    —For the State of Vermont, U.S. public relief program (1935-1943)

    You do not mean by mystery what a Catholic does. You mean an interesting uncertainty: the uncertainty ceasing interest ceases also.... But a Catholic by mystery means an incomprehensible certainty: without certainty, without formulation there is no interest;... the clearer the formulation the greater the interest.
    Gerard Manley Hopkins (1844–1889)