L4.11 Kapitola K4 — Toky a řezy (Slot 4) · [MUST] · souvisí s ústní

Cycle canceling (řešení MCF)

Jedna nová věc Cycle canceling (rušení cyklů): začni přípustným tokem, hledej záporný cyklus v reziduálním grafu $G_f$ (Bellman-Fordem) a augmentuj podél něj o $\gamma = \min_{e \in E(C)} u_f(e)$ — opakuj, dokud záporný cyklus existuje.

Minulá lekce [L4.10] Minimum Cost Flow + reziduální graf s cenami skončila objevem: záporný cyklus v $G_f$ = sleva beze změny bilancí. Na instanci ze slidu 32 jsi tak ručně srazil cenu toku z 18 přes 10 na 8. Dnes z toho objevu uděláme algoritmus — cycle canceling (slide 31, cvičení cv09) — a celý běh si odkrokujeme. Je to hlavní kombinatorický řešič MCF a častá otázka u ústní (spolu s Bellman-Fordem [L2.12], který v něm hraje detektiva).

Od slevy k algoritmu (slide 31)

Zkus sám: algoritmus už vlastně znáš. Ford-Fulkerson [L4.3] zní „dokud v $G_f$ existuje augmentující cesta $s \to t$, augmentuj o $\gamma$“. Dnes nezvyšujeme velikost, ale snižujeme cenu — a z [L4.10] víš, co cenu snižuje. Zformuluj celý algoritmus sám (tři kroky).

Stačí ve FF smyčce vyměnit „augmentující cesta“ za „záporný cyklus“: ① sežeň přípustný tok (bilance musí sedět od začátku — to je úloha z [L4.6]/[L4.7], tady ji jen použijeme); ② postav $G_f$ s cenami dle [L4.10] a najdi v něm cyklus se zápornou součtovou cenou; ③ pošli po něm $\gamma = $ minimum reziduálních kapacit na cyklu a vrať se na ②. Když záporný cyklus není, skonči — tok už zlevnit nejde. Jediné, co zatím neumíš, je krok ② „najdi záporný cyklus“ — to doženeme hned v další sekci.

Slide 31 — Minimum Cost Flow: Cycle Canceling Algorithm, 1:1

Input: Network $(G, l, u, b, c)$. Output: Minimum cost flow $f$.

  1. Find feasible flow $f$ while solving Feasible Flow with Balances in $(G, l, u, b)$.
  2. Build residual graph $G_f$ with respect to $f$. Find a negative-cost cycle $C$ in residual graph $G_f$. If none exists then stop.
  3. Compute $\gamma = \min_{e \in E(C)} u_f(e)$. Augment $f$ along $C$ by $\gamma$. Go to 2.

Všechny tři kroky stojí na věcech z dřívějších lekcí — proto je lekce o jedné nové věci, totiž o jejich složení do smyčky. Krok 1 je přesně [L4.6] (a při $l > 0$ [L4.7]). Krok 2 staví $G_f$ podle vzorců z [L4.10]: dopředná hrana $(u_f = u - f,\ c_f = +c)$, zpětná $(u_f = f - l,\ c_f = -c)$, hrany s $u_f = 0$ vypadnou. Krok 3 je augmentace jako ve FF [L4.3] — jen po cyklu, ne po cestě: na hranách cyklu souhlasných s původním grafem tok o $\gamma$ vzroste, na protisměrných klesne. Cvičení cv09 (Lab 9) to zapisuje pseudokódem:

cv09 (Lab 9) — Algorithm 1: Cycle canceling algorithm for Minimum-Cost Flow Problem, 1:1

Require: initial feasible balanced flow $f$ in $(G, l, u, c, b)$   Ensure: minimum-cost flow $f$ in $(G, l, u, c, b)$

function CYCLE-CANCELING(G, l, u, c, b, f)
    G_f ← build residual graph w.r.t. f
    while True do
        δ, C ← BELLMAN-FORD(G_f)
        if δ > 0 then
            for all e = (i, j) ∈ C do
                if e is a forward arc in G then       ▷ i.e., (i, j) ∈ E
                    f(i, j) ← f(i, j) + δ
                else
                    f(j, i) ← f(j, i) − δ
                end if
                u_f(i, j) ← u_f(i, j) − δ              ▷ update residual graph G_f
                u_f(j, i) ← u_f(j, i) + δ
            end for
        else
            break
        end if
    end while
    return f
end function

Pozn.: slide 31 značí kapacitu cyklu $\gamma$, cv09 píše $\delta$ — je to totéž číslo $\min_{e \in E(C)} u_f(e)$. Všimni si poslední dvojice řádků: augmentace o $\delta$ ubere kapacitu hranám cyklu a stejně tolik přidá hranám protisměrným — $G_f$ se přepočítá lokálně, nemusí se stavět celý znovu.

Krok 2 pod lupou: záporný cyklus najde Bellman-Ford

Zkus sám: nástroj na záporné cykly už máš — Bellman-Ford s detekcí [L2.12] („relaxuje se i po $|V|-1$ iteracích ⟹ záporný cyklus“). Jenže BF startuje z jednoho uzlu a vidí jen to, co je z něj dosažitelné. Z kterého uzlu ho v $G_f$ pustit, aby mu žádný cyklus neutekl?

Z žádného existujícího — žádný uzel $G_f$ nemusí mít dosah na celý graf. Trik: přidej pomocný uzel $s$ a veď z něj hranu s cenou $0$ do každého uzlu $G_f$. Z $s$ je teď dosažitelné všechno, takže BF z $s$ prohledá celý graf. A protože do $s$ žádná hrana nevede, nemůže pomocný uzel ležet na žádném cyklu — žádný falešný záporný cyklus jsme nevyrobili a ceny cyklů se nulovými hranami nezměnily.

Slide 31 (dole) — detekce záporného cyklu, 1:1

The negative-cost cycle $C$ in residual graph can be found as follows:

  1. Consider residual graph $(G_f, u_f, c_f)$ where all edges have $u_f(e) > 0$
  2. Add node $s$ and connect it to every $v \in V(G_f)$ by edge $e(s, v)$ with cost $c_f(e) = 0$.
  3. Use, for example, Bellman-Ford algorithm to detect a negative-cost cycle (with respect to cost $c_f$).
  4. Recover negative-cost cycle $C$ or state that it does not exist.

Samotnou detekci a rekonstrukci cyklu (přes vektor předchůdců) tu znovu nevykládáme — je to [L2.12]; proč to funguje, dokazuje [L3.7]. U ústní se obojí potkává: „k čemu je detekce záporného cyklu?“ → mimo jiné právě tady, v kroku 2 cycle cancelingu.

Celý běh na instanci ze slidu 32

Spustíme algoritmus na síti, kterou důvěrně znáš z [L4.10] (slide 32): uzly $u, v, w, x$ s bilancemi $b(u) = +4$, $b(x) = -4$, startovní přípustný tok za 18. (Slide 33 předvádí běh na obměně téže sítě — cykly $(v,w,x)$ a $(v,u,w)$ —, ale přepis obrázku p-38 neobsahuje hodnoty hran; proto krokujeme přesně instanci slidu 32, kde čísla máme ověřená — přiznáno.) Popisek hrany = $u_f \mid c_f$, protisměrné hrany čárkovaně; hrany s $u_f = 0$ jsou zešedlé s popiskem „$u_f = 0$“ — do $E_f$ nepatří, ve stepperu zůstávají jen proto, aby šlo krokovat oběma směry.

Zkus sám: poslední reziduální graf $G_f^{(3)}$ má pořád spoustu hran i cyklů — třeba $w \to x \to w$. Proč algoritmus přesto skončil? A co kdyby nějaký cyklus vyšel přesně na cenu 0?

Zastavovací podmínka nezní „žádný cyklus“, ale „žádný záporný cyklus“. V $G_f^{(3)}$ spočítej součty: $w \to x \to w$ má $1 + (-1) = 0$, $u \to v \to x \to u$ má $2 + 3 - 1 = +4$, $u \to v \to x \to w \to u$ má $2 + 3 - 1 - 2 = +2$… žádný součet není záporný, takže žádná úprava toku už cenu nesníží — 8 je optimum a neexistence záporného cyklu je jeho certifikát (přesně ten, který [L4.10] slibovala). Cyklus s cenou $0$ nevadí: augmentace po něm cenu nezmění — vyrobí jen jiné optimum za stejných 8.

Kolik iterací to může trvat? (slide 34)

Zkus sám: ať $U = \max u(i,j)$ a $C = \max |c(i,j)|$, vše celočíselné. Cena libovolného přípustného toku leží mezi $-|E| C U$ a $+|E| C U$ (každá z $|E|$ hran přispěje nejvýš $\pm C U$). Každá iterace cenu sníží aspoň o… kolik? A kolik nejvýš iterací tedy proběhne?

Při celočíselných datech je cena cyklu záporné celé číslo ($\le -1$) a $\gamma \ge 1$, takže každá iterace ubere aspoň $1$. Z ceny $\le |E| C U$ na cenu $\ge -|E| C U$ je to nejvýš $2|E| C U$ iterací. Každá iterace volá Bellman-Forda za $\mathcal{O}(|V| \cdot |E|)$ — dohromady $\mathcal{O}(|V| \cdot |E|^2 \cdot C \cdot U)$. Pozor: v odhadu sedí hodnoty $C$ a $U$, ne jen velikost grafu — je to pseudopolynomiální složitost, stejný úkaz jako u FF s $\mathcal{O}(|E| \cdot F)$ [L4.3].

Slide 34 — Cycle Canceling Algorithm: Complexity and its improvements, 1:1

Let $U = \max_{(i,j) \in E} u(i, j)$ and $C = \max_{(i,j) \in E} |c(i, j)|$. For any feasible flow $f$ its cost $c(f)$ is bounded as:

$$-|E| \cdot C \cdot U \le c(f) \le |E| \cdot C \cdot U$$

Each iteration decreases the objective by at least 1. Conclusion: there are at most $2|E| \cdot C \cdot U$ iterations. The Bellman-Ford complexity is $\mathcal{O}(|V| \cdot |E|)$. Overall time complexity is $\mathcal{O}(|V| \cdot |E|^2 \cdot C \cdot U)$.

An idea for improvement: Find the most negative cycle, but it is NP-hard. Better idea for improvement: Solution by a Minimum Mean Cycle Canceling Algorithm: Find cycle $C$ whose mean weight $\frac{c(E(C))}{|E(C)|}$ is minimum in $\mathcal{O}(|V| \cdot |E|)$. Minimum Mean Cycle Canceling Algorithm runs in $\mathcal{O}(|V|^2 \cdot |E|^3 \cdot \log |V|)$.

Čti poslední odstavec slidu jako příběh o výběru cyklu: brát nejzápornější cyklus by iterace srazilo, ale jeho nalezení je NP-těžké; brát cyklus s minimální průměrnou cenou na hranu jde polynomiálně — a celé minimum mean cycle canceling pak běží v čase polynomiálním jen ve velikosti grafu, bez $C$ a $U$. Pro ruční počítání u zkoušky je to jedno: vezmi kterýkoli záporný cyklus, který vidíš.

Nebezpečné polopravdy

1) Augmentuje se po CYKLU, ne po cestě $s \to t$. MCF žádné $s, t$ nemá — cesta by rozbila bilance, cyklus je nechává netknuté. (FF augmentuje cesty, cycle canceling cykly — to je celý rozdíl smyček.) 2) Stop = žádný ZÁPORNÝ cyklus, ne „žádný cyklus“. Cykly s cenou $\ge 0$ v $G_f$ klidně zbydou; nulové znamenají jen alternativní optima. 3) $\gamma$ ber z reziduálních kapacit $u_f$ na cyklu, ne z původních $u$ — a protisměrná hrana cyklu znamená, že tok na původní hraně o $\gamma$ klesne ($f(j,i) \leftarrow f(j,i) - \delta$ v Algorithm 1). 4) Bellman-Forda pouštěj z pomocného uzlu $s$ s $0$-hranami do všech uzlů — z obyčejného uzlu nemusí být celý $G_f$ dosažitelný a cyklus ti uteče; $s$ sám žádný cyklus nepřidá (nemá vstupní hrany). 5) Startovat se musí z PŘÍPUSTNÉHO toku (bilance + meze) — $f \equiv 0$ obecně přípustný není; sežeň ho přes [L4.6]/[L4.7].

Key takeaways — L4.11
T01 Cycle canceling — algoritmus a jeho čtyři ingredience zdroj: cv09_mcf_objecttracking.md (Lab 9, text EN 1:1; otázky i–iv vlastní — přiznáno; téma ústní)
Assignment (original, EN 1:1)

The cycle canceling algorithm for solving Minimum Cost Flow Problem is conceptually very similar to Ford-Fulkerson's algorithm for Maximum Flow problem. Ford-Fulkerson starts from a feasible flow, that is further improved via consequent iterations. Similarly, the cycle canceling algorithm gradually reduces the cost of the flow while keeping balances satisfied in each vertex. Such an improvement in each iteration is characterized by a cost-negative cycle in a suitably defined graph – so-called residual graph. After a cost-negative cycle is found, the flow is augmented along the cycle which results into a new flow that still satisfies balances but is cheaper. The algorithm terminates when no additional cost-negative cycle can be found.

There are four key ingredients when implementing the cycle canceling algorithm: 1. Residual graph, 2. Main loop, 3. Detecting a negative cycle, 4. Finding the initial balanced flow.

Studijní otázky (vlastní — přiznáno): (i) Define the residual graph $G_f$ (capacities and costs). (ii) Write down the main loop of the algorithm. (iii) Explain how a cost-negative cycle is detected. (iv) Explain how the initial feasible balanced flow is found.

a) Co je v zadání?

Teoretická/ústní úloha: popsat cycle canceling jako stavebnici čtyř dílů. Všechny čtyři už z kurzu znáš — tady jde o to umět je vyjmenovat, přesně zapsat a říct, ve které lekci (resp. na kterém slidu) každý díl bydlí.

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Drž se paralely s FF: „z čeho startuju → v čem hledám zlepšení → jak zlepšení provedu → kdy končím“. U každé ingredience si vybav vzorec nebo konstrukci, ne jen jméno: u $G_f$ čtveřici vzorců, u detekce pomocný uzel $s$, u startu redukci s $s', t'$.

d) Úplné řešení (dle cv09 / slidů 31–32)

(i) Residual graph (cv09 §1.1 = slide 32, 1:1):

$$ \begin{aligned} G_f &= (V, E_f, u_f, c_f) \\ u_f(i, j) &= u(i, j) - f(i, j) & \forall (i, j) \in E \\ u_f(j, i) &= f(i, j) - l(i, j) & \forall (i, j) \in E \\ c_f(i, j) &= c(i, j) & \forall (i, j) \in E \\ c_f(j, i) &= -c(i, j) & \forall (i, j) \in E \end{aligned} $$

Hrany s $u_f(e) = 0$ se vynechávají (nemohou ležet na žádném augmentujícím cyklu); $G_f$ má tedy nejvýš $2|E|$ hran. Detailně [L4.10].

(ii) Main loop (cv09 Algorithm 1 = slide 31): dokud Bellman-Ford v $G_f$ najde záporný cyklus $C$ s kapacitou $\delta = \min_{e \in C} u_f(e) > 0$, augmentuj: pro každou hranu $e = (i,j) \in C$, je-li $e$ dopředná v $G$, pak $f(i,j) \leftarrow f(i,j) + \delta$, jinak $f(j,i) \leftarrow f(j,i) - \delta$; reziduální kapacity uprav $u_f(i,j) \leftarrow u_f(i,j) - \delta$ a $u_f(j,i) \leftarrow u_f(j,i) + \delta$. Když záporný cyklus neexistuje, vrať $f$ — je to minimum cost flow.

(iii) Detecting a negative cycle (cv09 §1.3 = slide 31 dole, 1:1): 1. Take the current $G_f$, remove all edges with zero residual capacity. 2. Introduce a dummy vertex $s$ and connect it with every other vertex in $G_f$ by edge with cost $c_f(e) = 0$. 3. Compute the shortest path tree (with respect to costs $c_f$) from the dummy vertex $s$ to all other vertices. 4. Recover a negative cycle or state that it does not exist. — Bellman-Ford relaxuje i po $|V| - 1$ iteracích ⟺ záporný cyklus, který se zrekonstruuje z vektoru předchůdců ([L2.12], důkaz [L3.7]).

(iv) Initial feasible balanced flow (cv09 §1.4, 1:1): 1. Introduce dummy vertices $s, t$ to the original graph $G$. 2. Connect $s$ with vertices $v \in V$, if $b(v) > 0$, set $l(s, v) = 0$ and $u(s, v) = b(v)$. 3. Connect vertices $v \in V$ with $t$, if $b(v) < 0$, set $l(v, t) = 0$ and $u(v, t) = -b(v)$. 4. Find maximum flow $f$ in this graph by Ford-Fulkerson algorithm. 5. If $f$ saturates all outgoing edges from $s$, then disconnect $s$ and $t$ from $G$. Now, the flow $f$ is a feasible balanced flow for the original minimum-cost flow problem. — To je přesně redukce z [L4.6]; nenulové dolní meze řeší [L4.7].

Bonus k ústní: složitost $\mathcal{O}(|V| \cdot |E|^2 \cdot C \cdot U)$ (slide 34, pseudopolynomiální) a kontext cvičení: cv09 tímhle algoritmem řeší data association při sledování hráčů ve videu — přiřazovací problém jako MCF, viz [L4.12].

T02 Cycle canceling — ruční běh od startu k certifikátu zdroj: VLASTNÍ procvičovací úloha (zadání, instance i řešení vlastní — přiznáno)
Assignment (EN, vlastní — přiznáno)

Consider the minimum-cost flow instance $(G, l, u, c, b)$ below with balances $b(a) = +3$, $b(b) = b(c) = 0$, $b(d) = -3$ and the initial feasible flow $f$ (edge labels read $l, f, u$ · $c$).

(i) Verify that $f$ is feasible and compute its cost. (ii) Run the cycle canceling algorithm: in each iteration draw the residual graph $G_f$, find a cost-negative cycle, determine $\delta$ and augment. (iii) When the algorithm stops, state the minimum cost and give the certificate of optimality.

a) Co je v zadání?

Kompletní ruční běh dnešního algoritmu na malé síti: start je darovaný (tok je v zadání), takže zbývá smyčka kroků 2–3 — reziduální grafy, záporné cykly, augmentace — a na závěr certifikát, že levněji to nejde.

b) Co k tomu budeme potřebovat?

  • Tato lekce — smyčka + zastavení (takeaways).
  • [L4.10] — stavba $G_f$ s cenami (drill T02 tam je přímá rozcvička).
  • [L2.12] — kdyby cyklus nebyl vidět od oka, najde ho Bellman-Ford.

c) Jak nad úlohou uvažovat?

U malé sítě nemusíš formálně spouštět Bellman-Forda — záporné cykly hledej od oka, ale systematicky: projdi cykly v $G_f$ a sčítej ceny $c_f$. Po každé augmentaci přepočítej jen hrany cyklu ($u_f \mp \delta$), zbytek $G_f$ se nemění. Konči teprve, až součty všech cyklů vyjdou $\ge 0$ — a tuhle kontrolu napiš, to je certifikát.

d) Úplné řešení (vlastní — přiznáno)

(i) Přípustnost a cena. Meze: $3 \in [0,3]$, $3 \in [0,4]$, $0 \in [0,3]$, $0 \in [0,3]$, $0 \in [0,2]$ ✓. Bilance (out − in): $a$: $3 + 0 = 3 = b(a)$ ✓; $b$: $(3 + 0) - 3 = 0$ ✓; $c$: $0 - 0 = 0$ ✓; $d$: $0 - 3 = -3$ ✓. Cena $= 3 \cdot 1 + 3 \cdot 4 = \mathbf{15}$.

(ii) Běh (odkrokuj si):

Iterace 1: v $G_f^{(1)}$ je záporný cyklus $d \to b \to c \to d$ s cenou $-4 + 1 + 1 = -2$ a $\delta = \min(3, 2, 3) = 2$ → tok na $b \to d$ klesne $3 \to 1$ (protisměrná hrana), na $b \to c$ a $c \to d$ vzroste $0 \to 2$; cena $15 - 2 \cdot 2 = 11$. Iterace 2: v $G_f^{(2)}$ je záporný cyklus $b \to a \to c \to d \to b$ s cenou $-1 + 2 + 1 - 4 = -2$ a $\delta = \min(3, 3, 1, 1) = 1$ → $f(a \to b)\!: 3 \to 2$, $f(a \to c)\!: 0 \to 1$, $f(c \to d)\!: 2 \to 3$, $f(b \to d)\!: 1 \to 0$; cena $11 - 2 \cdot 1 = \mathbf{9}$. (Bellman-Ford může cykly najít i v jiném pořadí — skončit musí vždy na ceně 9.)

(iii) Certifikát. V $G_f^{(3)}$ projdi všechny cykly: $a \to b \to a$: $1 - 1 = 0$; $a \to c \to a$: $2 - 2 = 0$; $a \to c \to b \to a$: $2 - 1 - 1 = 0$; $a \to b \to d \to c \to a$: $1 + 4 - 1 - 2 = +2$; $b \to d \to c \to b$: $4 - 1 - 1 = +2$. Žádný záporný ⟹ tok $f^* = (a{\to}b\!: 2,\ b{\to}d\!: 0,\ a{\to}c\!: 1,\ c{\to}d\!: 3,\ b{\to}c\!: 2)$ s cenou $\mathbf{9}$ je optimální. (Nulové cykly prozrazují alternativní optima — např. poslat všechny 3 jednotky přes $a \to c \to d$ stojí také 9.)

← Předchozí L4.10 · Minimum Cost Flow + reziduální graf s cenami