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:

    “During the Civil War the area became a refuge for service- dodging Texans, and gangs of bushwhackers, as they were called, hid in its fastnesses. Conscript details of the Confederate Army hunted the fugitives and occasional skirmishes resulted.”
    —Administration in the State of Texa, 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)