Circulation problem

Circulation problem

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 multiple commodities flowing through the network, and a cost on the flow.

Contents

Definition

Given is a flow network G(V,E) with:

l(v,w), lower bound on flow from node v to node w,
u(v,w), upper bound on flow from node v to node w,
c(v,w), cost of a unit of flow on (v,w)

and the constraints:

l(v,w) \leq f(v,w) \leq u(v,w),
\sum_{w \in V} f(u,w) = 0 (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, minimise

\sum_{(v,w) \in E} c(v,w) \cdot f(v,w).

Multi-commodity circulation

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

\,f_i(v,w) The flow of commodity i from v to w.
\,f(v,w) = \sum_i f_i(v,w) The total flow.

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

\ \sum_{w \in V} f_i(u,w) = 0.

Solution

For the circulation problem, many polynomial algorithms have been developed (e.g., Edmonds and Karp, 1972; Tarjan 1987-1988).

For the case of multiple commodities, the problem is NP-complete for integer flows.[1] For fractional flows, it is solvable in polynomial time, as one can formulate the problem as a linear program.

Related problems

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
  • Multi-commodity circulation - Solve without optimising cost.
  • Simple circulation - Just use one commodity, and no cost.
  • Multi-commodity flow - If Ki(si,ti,di) denotes a demand of di for commodity i from si to ti, create an edge (ti,si) with l(ti,si) = c(ti,si) = di for all commodities i. Let l(u,v) = 0 for all other edges.
  • Minimum cost multi-commodity flow problem - As above, but minimise 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 t to the source s with l(t,s) = 0, c(t,s) = ∞ and a(t,s) = − 1.
  • Minimum cost maximum flow problem - First find the maximum flow amount m. Then solve with l(t,s) = c(t,s) = m and a(t,s) = 0.
  • Single-source shortest path - Let l(u,v) = 0 and c(u,v) = 1 for all edges in the graph, and add an edge (t,s) with l(t,s) = c(t,s) = 1 and a(t,s) = 0.
  • All-pairs shortest path - Let all capacities be unlimited, and find a flow of 1 for v(v − 1) / 2 commodities, one for each pair of nodes.

References

  1. ^ S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing (SIAM) 5 (4): 691–703. doi:10.1137/0205048. http://link.aip.org/link/?SMJ/5/691/1. 

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Circulation — may refer to: Circulatory system, a biological organ system whose primary function is to move substances to and from cells Circulation (fluid dynamics), the path integral of the fluid velocity around a closed curve Circulation (journal), one of… …   Wikipedia

  • circulation — circulable /serr kyeuh leuh beuhl/, adj. /serr kyeuh lay sheuhn/, n. 1. an act or instance of circulating, moving in a circle or circuit, or flowing. 2. the continuous movement of blood through the heart and blood vessels, which is maintained… …   Universalium

  • Circulation control wing — A circulation control wing (CCW) is a form of high lift device for use on the main wing of an aircraft to increase the lift coefficient. CCW technology has been in the research and development phase for over sixty years, and the early models were …   Wikipedia

  • Circulation — The movement of fluid in a regular or circuitous course. Although the noun "circulation" does not necessarily refer to the circulation of the blood, for all practical purposes today it does. Heart failure is an example of a problem with …   Medical dictionary

  • Minimum-cost flow problem — The minimum cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network. Contents 1 Definition 2 Relation to other problems 3 Solutions 4 See also …   Wikipedia

  • Maximum flow problem — An example of a flow network with a maximum flow. The source is s, and the sink t. The numbers denote flow and capacity. In optimization theory, the maximum flow problem is to find a feasible flow through a single source, single sink flow network …   Wikipedia

  • Multi-commodity flow problem — The multi commodity flow problem is a network flow problem with multiple commodities (or goods) flowing through the network, with different source and sink nodes. Contents 1 Definition 2 Relation to other problems 3 Usage 4 …   Wikipedia

  • Minimum cost flow problem — The minimum cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network. Definition Given a flow network ,G(V,E) with source s in V and sink t in V, where edge (u,v) in E has capacity ,c(u,v) …   Wikipedia

  • Shutdown of thermohaline circulation — Shutdown or slowdown of the thermohaline circulation is a postulated effect of global warming.There is some speculation that global warming could, via a shutdown or slowdown of the thermohaline circulation, trigger localized cooling in the North… …   Wikipedia

  • Brain Circulation — is a concept that is posited as a counter factual to the idea of Brain Drain. The concept of Brain Drain gained popularity as skilled labour from certain countries emigrated to other countries in search of better opportunties. In India for… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”