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:
“Adjoining a refreshment stand ... is a small frame ice house ... with a whitewashed advertisement on its brown front stating, simply, Ice. Glory to Jesus. The proprietor of the establishment is a religious man who has seized the opportunity to broadcast his business and his faith at the same time.”
—For the State of New Jersey, 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)