Cirkulationsproblem

Cirkulationsproblemet och dess varianter är en generalisering av nätverksflödesproblem , med den extra begränsningen av en nedre gräns för kantflöden, och med flödeskonservering som också krävs för källan och sänkan (dvs. det finns inga speciella noder). I varianter av problemet finns det flera varor som strömmar genom nätverket och en kostnad på flödet.

Definition

Givet flödesnätverk $G(V,E)$ med:

$l(v,w)$ , nedre gräns för flöde från nod $\displaystyle v}$ till nod $w$ ,

$u(v ,w)$ , övre gräns för flöde från nod $v$ till nod $w$ ,

$c(v,w)$ , kostnad för en flödesenhet på $(v,w)$

och begränsningarna:

$l(v,w)\leq f(v,w)\leq u(v,w)$ ,

$\sum _{w\in V}f(u,w)=0$ (flöde kan inte visas eller försvinna i noder).

Att hitta en flödesuppgift som uppfyller begränsningarna ger en lösning på det givna cirkulationsproblemet.

I den lägsta kostnadsvarianten av problemet, minimera

$\sum _{(v,w)\in E}c(v,w)\cdot f(v,w).$

Cirkulation av flera varor

I ett cirkulationsproblem med flera varor måste du också hålla reda på flödet av de enskilda varorna:

$\,f_{i}(v,w)$	Flödet av varu $i$ från $v$ till $w$ .
$\,f(v,w)=\summa _{i}f_{i}(v,w)$	Det totala flödet.

Det finns också en lägre gräns för varje flöde av råvara.

$\,l_{i}(v,w)\leq f_{i}(v,w)$

Bevarandebegränsningen måste upprätthållas individuellt för varorna:

$\ \sum _{w\in V}f_{i}(u,w)=0.$

Lösning

För cirkulationsproblemet har många polynomalgoritmer utvecklats (t.ex. Edmonds–Karp algorithm , 1972; Tarjan 1987-1988). Tardos hittade den första starkt polynomiska algoritmen.

För fallet med flera varor är problemet NP-komplett för heltalsflöden. För bråkflöden är det lösbart i polynomtid , då man kan formulera problemet som ett linjärt program .

Relaterade problem

Nedan ges några problem och hur man löser dem med den allmänna cirkulationsuppsättningen som ges ovan.

• Minsta kostnadsproblem med cirkulation av flera varor - Använder alla begränsningar som anges ovan.
• Cirkulationsproblem med minimal kostnad - Använd en enda vara
• Multi-commodity cirkulation - Lös utan att optimera kostnaden.
• Enkel cirkulation - Använd bara en vara och utan kostnad.
• Multi-commodity flow - Om $K_{i}(s_{i},t_{i},d_{i})$ anger ett krav på ${\ displaystyle d_{i}}$ för commodity $i$ från $s_{i}$ till $t_{i}$ , skapa en kant $(t_{i},s_{i})$$displaystyle l_{i}(t_{i},s_{i })=u(t_{i},s_{i})=d_{i}}$ i för alla varor $i$ . Låt $l_{i}(u,v)=0$ för alla andra kanter.
• Lägsta kostnad flödesproblem för flera varor - Som ovan, men minimera kostnaden.
• Minsta kostnadsflödesproblem - Som ovan, med 1 vara.
• Maximalt flödesproblem - Sätt alla kostnader till 0 och lägg till en kant från sänkan $t$ till källans $s$ med $l(t,s)= 0$ , $u(t,s)=$ ∞ och $c(t,s)=-1$ .
• Minsta kostnad maximalt flöde problem - Hitta först den maximala flödesmängden $m$ . Lös sedan med $l(t,s)=u(t,s)=m$ och $c( t,s)=0$ .
• Enkällas kortaste väg - Låt $l(u,v)=0$ och $c(u,v)=1$ för alla kanter i grafen och lägg till en kant $(t,s)$ med $l(t,s)=u( t,s)=1$ och $c(t,s)=0$ .
• Kortaste vägen för alla par - Låt alla kapaciteter vara obegränsade och hitta ett flöde på 1 för $v(v-1)/2$ varor, en för varje nodpar.