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:

    Adjoining a refreshment stand ... is a small frame ice house ... with a whitewashed advertisement on its brown front stating, simply, “Ice. Glory to Jesus.” The proprietor of the establishment is a religious man who has seized the opportunity to broadcast his business and his faith at the same time.
    —For the State of New Jersey, U.S. public relief program (1935-1943)

    In necessary things, unity; in disputed things, liberty; in all things, charity.
    —Variously Ascribed.

    The formulation was used as a motto by the English Nonconformist clergyman Richard Baxter (1615-1691)