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:

    “Mead had studied for the ministry, but had lost his faith and took great delight in blasphemy. Capt. Charles H. Frady, pioneer missionary, held a meeting here and brought Mead back into the fold. He then became so devout that, one Sunday, when he happened upon a swimming party, he shot at the people in the river, and threatened to kill anyone he again caught desecrating the Sabbath.”
    —For the State of Nebraska, 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)