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:

    “To the cry of “follow Mormons and prairie dogs and find good land,” Civil War veterans flocked into Nebraska, joining a vast stampede of unemployed workers, tenant farmers, and European immigrants.”
    —For the State of Nebraska, 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)