Circulation problem: Difference between revisions

Revision as of 15:09, 2 September 2009

Latest revision as of 16:42, 24 May 2025

(30 intermediate revisions by 26 users not shown)

Line 1:

{{Short description|Generalization of network flow problems}}

The '''circulation problem''' and its variants isare a generalisation of [[flow network|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, youthere haveare multiple commodities flowing through the network, and a cost on the flow.

== Definition ==

Given a flow network <math>\,G(V,E)</math> with:

| :<math>\,ul(v,w)</math>, || Upperlower bound on flow from node <math>v</math> to node <math>w</math>.,

:{|

| :<math>\,lu(v,w)</math>, || Lowerupper bound on flow from node <math>v</math> to node <math>w</math>.,

| :<math>\,c(v,w)</math>, || Costcost of a unit of flow on <math>(v,w)</math>.

|-

| <math>\,u(v,w)</math> || Upper bound on flow from node <math>v</math> to node <math>w</math>.

|-

| <math>\,c(v,w)</math> || Cost of a unit of flow on <math>(v,w)</math>.

|}

You haveand the constraints :

:<math>l(v,w) \leq f(v,w) \leq u(v,w)</math>,

:{|

| :<math>\quad l(v,sum_{w) \leqin V} f(vu,w) \leq= u(v,w)0</math> (flow cannot appear or disappear in nodes).

|-

| <math>\ \sum_{w \in V} f(u,w) = 0</math> || Flow cannot appear or disappear in nodes.

|}

Finding a flow assignment satisfying the constraints gives a solution to the given circulation problem.

In the minimum cost variant of the problem, minimiseminimize

: <math>\sum_{(v,w) \in E} c(v,w) \cdot f(v,w).</math>

Line 30 ⟶ 24:

:{|

| <math>\,f_i(v,w)</math> || The flow of commodity <math>\,i</math> from <math>\,v</math> to <math>\,w</math>.

|-

| <math>\,f(v,w) = \sum_i f_i(v,w)</math> || The total flow.

|}

There is also a lower bound on each flow of commodity.

The conservation constraint must be upheld for individually for the commodities:

:{|

| <math>\ \sum_{,l_i(v,w) \in V}leq f_i(uv,w) = 0.</math>

|}

The conservation constraint must be upheld for individually for the commodities:

| :<math>\ \sum_{w \in V} ff_i(u,w) = 0.</math> || Flow cannot appear or disappear in nodes.

== Solution ==

For the circulation problem, many polynomial algorithms have been developed (ege.g., [[Edmonds-KarpEdmonds–Karp algorithm|Edmonds and Karp]], 1972; Tarjan 1987-1988). Tardos found the first strongly polynomial algorithm.<!--ref whichname="Ta85">{{cite articles?journal --| author = Éva Tardos | title = A strongly polynomial minimum cost circulation algorithm | journal = Combinatorica | date = 1985 | volume = 5 | issue = 3 | pages = 247–255 | doi = 10.1007/BF02579369}}</ref>

<!-- which articles? -->

For the case of multiple commodities, the problem is [[NP-complete]] for integer flows.<ref name="EIS76">{{cite journal | author = S. Even and A. Itai and A. Shamir | title = On the Complexitycomplexity of Timetabletimetable and Multicommoditymulti-commodity Flowflow Problemsproblems | publisher = SIAM | year = 1976 | journal = SIAM Journal on Computing | volume = 5 | number = 4 | pages = 691–703 | url = http://link.aip.org/link/?SMJ/5/691/1 | doi = 10.1137/0205048 | issue = 4 | url-status = dead | archiveurl = https://archive.today/20130112133748/http://link.aip.org/link/?SMJ/5/691/1 | archivedate = 2013-01-12 | url-access = subscription }}</ref>. For fractional flows, it is solvable in [[polynomial time]], as one can formulate the problem as a [[linear programming|linear program]].

== Related problems ==

Line 52 ⟶ 51:

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

* Minimum cost circulation problem - Use a single commodity

* Multi-commodity circulation - Solve without optimising cost.

* Simple circulation - Just use one commodity, and no cost.

* [[Multi-commodity flow problem|Multi-commodity flow]] - If <math>K_i(s_i,t_i,d_i)</math> denotes a demand of <math>d_i</math> for commodity <math>i</math> from <math>s_i</math> to <math>t_i</math>, create an edge <math>(t_i,s_i)</math> with <math>ll_i(t_i,s_i) = cu(t_i,s_i) = d_i</math> for all commodities <math>i</math>. Let <math>ll_i(u,v)=0</math> for all other edges.

* [[Minimum cost multi-commodity flow problem]] - As above, but minimiseminimize the cost.

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

* [[Maximum flow problem]] - Set all costs to 0, and add an edge from the sink <math>t</math> to the source <math>s</math> with <math>l(t,s)=0</math>, <math>cu(t,s)=</math>&infin;∞ and <math>ac(t,s)=-1</math>.

* [[Minimum cost maximum flow problem]] - First find the maximum flow amount <math>m</math>. Then solve with <math>l(t,s)=cu(t,s)=m</math> and <math>ac(t,s)=0</math>.

* [[Shortest path problem|Single-source shortest path]] - Let <math>l(u,v)=0</math> and <math>c(u,v)=1</math> for all edges in the graph, and add an edge <math>(t,s)</math> with <math>l(t,s)=cu(t,s)=1</math> and <math>ac(t,s)=0</math>.

* [[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.

Line 65 ⟶ 64:

<references/>

[[Category:Network flow problem]]

[[Category:Mathematical problems]]