Circulation problem: Difference between revisions

Revision as of 10:42, 2 September 2006

Revision as of 11:04, 2 September 2006

Line 1:

The '''circulation problem''' and its variants is a generalisation of [[network flow]] problems, with the added constraint of a lower bound on edge flows, and with '''flow conservation''' also being required for the source and sink (i.e. there are no special nodes). In variants of the problem, you have multiplemmultiple commodities flowing through the network, and a cost on the flow.

== Definition ==

Line 35:

== Solution ==

The only known polynomial solution to this problem is [[linear programming]]<ref>{{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]] | title = [[Introduction to Algorithms]] | origyear = 1990 | edition = 2nd edition | year = 2001 | publisher = MIT Press and McGraw-Hill | pages = 788-789 | chapter = 29 | id = ISBN 0-262-03293-7}}</ref>.

== Related problems ==

Line 41:

Below are given some problems, and how to solve them with the general circulation setup given above.

* ''Minimum cost multi-commodity circulation problem'' - Using all constraints given above.

* ''Minimum cost circulation problem'' - Use a single commodity

* [[Minimum cost multi-commodity flow problem]]. Set all lower bounds to 0. Add an edge from the sink to the source with cost less that the negative sum of all other edges. Control the amount of flow by adjusting <math>l(t_i,s_i)=u(t_i,s_i)=d_i</math>.

* [[Minimum cost flow problem]]. As above, with 1 commodity.

* [[Maximum flow problem]]. Set all costs to 0, and add an edge from the sink to the source with negative cost.

* [[Shortest path problem|Single-source shortest path]]. Set all capacities to 1, and findFind the cheapest flow of 1.

* [[Multi-commodity flow problem|Multi-commodity flow]]. Set all costs to 0. Back-edges with <math>l(t_i,s_i)=u(t_i,s_i)=d_i</math>.

* [[Maximum flow problem|Maximum flow]]. Solve with 1 commodity, and maximize the flow by adding an edge <math>(t,s)</math> with negative cost.

* [[Shortest path problem|All-pairs shortest path]]. Let all capacities be unlimited, and find a flow of 1 for <math>v(v-1)/2</math> commodities, one for each pair of nodes.