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
|
subject to
|
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 minister preached a sermon on Jonah and the whale, at the end of which an old chief arose and declared, We have heard several of the white people talk and lie; we know they will lie, but this is the biggest lie we ever heard.”
—Administration in the State of Miss, 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)

