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:

    “[T]he Congregational minister in a neighboring town definitely stated that ‘the same spirit which drove the herd of swine into the sea drove the Baptists into the water, and that they were hurried along by the devil until the rite was performed.’”
    —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)