Circulation problem: Difference between revisions

Revision as of 21:04, 13 September 2006

Latest revision as of 16:42, 24 May 2025

(46 intermediate revisions by 35 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 flow network <math>G(V,E)</math> with:

Given:<math>l(v,w)</math>, lower bound aon flow networkfrom node <math>\,G(V,E)v</math> withto node <math>w</math>,

| :<math>\,f_iu(uv,vw)</math>, ||upper Thebound on flow offrom commoditynode <math>iv</math> fromto <math>u</math> tonode <math>vw</math>,

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

You haveand the constraints :

: <math>\sum_{l(uv,vw) \inleq E} af(uv,vw) \cdotleq fu(uv,vw)</math>,

:<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

| '''Flow conservation''': || <math>\ \sum_{(v,w) \in VE} f_ic(uv,w) =\cdot 0f(v,w).</math>

=== Multi-commodity circulation ===

In a multi-commodity circulation problem, you also need to keep track of the flow of the individual commodities:

:{|

| <math>\,lf_i(u,v,w)</math> || LowerThe boundflow onof flowcommodity <math>i</math> from <math>uv</math> to <math>vw</math>.

|-

| <math>\,cf(uv,w) = \sum_i f_i(v,w)</math> || UpperThe boundtotal (often denoted <math>u</math> instead of <math>c</math>)flow.

|-

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

|-

| <math>\,K_i = (s_i,t_i,d_i)</math> || The source, sink, and demand of commodity <math>i</math>

|-

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

|-

| <math>\,f(u,v) = \sum_i f_i(u,v)</math> ||

|}

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

You have the constraints

:{|

| '''Capacity constraints''': &nbsp; || <math>\quad l,l_i(uv,vw) \leq ff_i(u,v) \leq c(u,vw)</math>

|-

| '''Skew symmetry''': || <math>\;f_i(u,v) = - f_i(v,u)</math>

|-

| '''Flow conservation''': || <math>\ \sum_{w \in V} f_i(u,w) = 0</math>

|}

The conservation constraint must be upheld individually for the commodities:

In the minimum cost variant of the problem, minimise

: <math>\sum_{(u,v) \in E} a(u,v) \cdot f(u,v)</math>

| :<math>\,f(u,v) =\sum_{w \sum_iin V} f_i(u,vw) = 0.</math> ||

Note that the parameters for commodity <math>\,s_i,t_i,d_i</math> are not used directly in the optimisation problem. To get a flow of <math>\,d_i</math> from <math>\,s_i</math> to <math>\,t_i</math>, set <math>\,l(t_i,s_i) = c(t_i,s_i) = d_i</math>.

== Solution ==

For the circulation problem, many polynomial algorithms have been developed (e.g., [[Edmonds–Karp algorithm]], 1972; Tarjan 1987-1988). Tardos found the first strongly polynomial algorithm.<ref name="Ta85">{{cite 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 complexity of timetable and multi-commodity flow problems | publisher = SIAM | year = 1976 | journal = SIAM Journal on Computing | volume = 5 | 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]].

The only known polynomial solution to any multi-commodity flow 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 45 ⟶ 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>l_i(t_i,s_i) = u(t_i,s_i) = d_i</math> for all commodities <math>i</math>. Let <math>l_i(u,v)=0</math> for all other edges.

* [[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 maximummulti-commodity flow problem]] - LetAs theabove, backbut edgeminimize have unlimitedthe capacitycost.

* [[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 negative<math>l(t,s)=0</math>, <math>u(t,s)=</math>∞ and cost<math>c(t,s)=-1</math>.

* [[Minimum cost maximum flow problem]] - Let the back edge have unlimited capacity.

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

* [[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]] - FindLet <math>l(u,v)=0</math> and <math>c(u,v)=1</math> for all edges in the cheapestgraph, flowand ofadd an edge <math>(t,s)</math> with <math>l(t,s)=u(t,s)=1</math> and <math>c(t,s)=0</math>.

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

Line 59 ⟶ 64:

<references/>

[[Category:Network flow problem]]

[[Category:Mathematical problems]]