Minimum Cost Flow + reziduální graf s cenami
Celá kapitola zatím řešila otázku kolik: maximální tok [L4.3], přípustnost s bilancemi [L4.6] a dolními mezemi [L4.7]. Dnes přidáme otázku za kolik — každá jednotka toku po hraně něco stojí. Dostaneme minimum cost flow (MCF, tok s minimální cenou): nejobecnější tokovou úlohu kapitoly, do které se schová max flow, nejkratší cesta i listonoš. A protože algoritmus pro MCF (cycle canceling, příští lekce [L4.11]) pracuje v reziduálním grafu, doplníme do reziduálního grafu z [L4.2] poslední chybějící ingredienci: ceny $c_f$. Přes MCF se v [L4.12] vyřeší i assignment problem — Maďarský (Hungarian) algoritmus je ze zkoušky vyloučen.
Za kolik? Nová otázka pro starou síť
Vezmi síť ze slidu 32 (přednáška ji používá pro celé MCF). Hrany mají kromě mezí $l, u$ a toku $f$ nově i cenu $c(e)$ za jednotku toku; uzly nemají $s$ a $t$, ale bilance $b(v)$ přesně jako v [L4.6]: uzel $u$ vyrábí 4 jednotky, uzel $x$ je spotřebuje.
Zkus sám: nakreslený tok bilance splňuje (ověř Kirchhoffa s bilancemi!) a stojí $3 \cdot 2 + 1 \cdot 2 + 0 \cdot 1 + 3 \cdot 3 + 1 \cdot 1 = 18$. Umíš ty 4 jednotky z $u$ do $x$ dopravit levněji? Kolik nejméně?
Spočítej cenu tras za jednotku: přímo $u \to x$ stojí 1 (ale kapacita jen 2), přes $w$ stojí $2 + 1 = 3$ (kapacita $\min(2,5) = 2$), přes $v$ stojí $2 + 3 = 5$. Nejlevnější mix: 2 jednotky přímo + 2 jednotky přes $w$ = $2 \cdot 1 + 2 \cdot 3 = \mathbf{8}$. Bilance sedí stejně dobře jako u nakresleného toku za 18 — přípustnost o ceně nic neříká. Max flow by mezi oběma toky nerozlišoval; potřebujeme novou úlohu, která mezi přípustnými toky vybírá ten nejlevnější. (Že je 8 opravdu minimum, dnes jen tušíme — certifikát dodá příští lekce [L4.11]: žádný záporný cyklus v reziduálním grafu.)
Definice (slide 28)
Extension of the Maximum flow problem – we consider the edge costs and the supply/consumption of the nodes.
Instance: 5-tuple $(G, l, u, c, b)$ where $G$ is a digraph, $u: E(G) \to \mathbb{R}^+_0$ represents the upper and $l: E(G) \to \mathbb{R}^+_0$ the lower bounds and:
- cost of arcs $c: E(G) \to \mathbb{R}$
- balance $b: V(G) \to \mathbb{R}$ that represents the supply/consumption of the nodes and satisfies $\sum_{v \in V(G)} b(v) = 0$.
Goal: Find the feasible flow $f$ that minimizes $\sum_{e \in E(G)} f(e) \cdot c(e)$ (we want to transport the flow through the network at the lowest possible cost) and satisfies $\sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = b(v)$ for all $v \in V(G)$, or decide that it does not exist.
Všimni si tří věcí. ① Síť nemá $s$ ani $t$ — roli „odkud kam“ hrají bilance $b(v)$ z [L4.6] (kladná = zdroj/výroba, záporná = spotřeba, a $\sum_v b(v) = 0$ je nutná podmínka). ② Cena smí být i záporná: $c: E(G) \to \mathbb{R}$, žádné $\mathbb{R}^+_0$ — za poslání jednotky můžeš i „dostat zaplaceno“. ③ Úloha má dvě možná vyústění: nejlevnější přípustný tok, nebo zjištění, že přípustný tok vůbec neexistuje — to už umíš rozhodnout redukcí z [L4.6]/[L4.7].
LP formulace (slide 29)
Zkus sám: LP napiš dřív, než ho uvidíš. Proměnné a omezení už všechny znáš — z max-flow LP [L4.1] a bilančních rovnic [L4.6]. Co se změní v účelové funkci?
Proměnné zůstávají $f(e)$ pro každou hranu, meze $l(e) \le f(e) \le u(e)$ taky. Kirchhoffa nahradí bilanční rovnice $\sum_{\delta^+} - \sum_{\delta^-} = b(v)$ — pro každý uzel (žádné výjimky pro $s, t$, ty tu nejsou). Jediná skutečná novinka: účelová funkce už nemaximalizuje velikost toku, ale minimalizuje cenu $\sum_e c(e) f(e)$ — lineární funkci proměnných, takže pořád LP.
Variable $f(e) \in \mathbb{R}^+_0$ represents the flow on edge $e \in E(G)$.
$$ \begin{aligned} \min \quad & \sum_{e \in E(G)} c(e) \cdot f(e) \\ \text{s.t.} \quad & \sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = b(v) & v \in V(G) \\ & l(e) \le f(e) \le u(e) & e \in E(G) \end{aligned} $$
MCF je nejobecnější úloha kapitoly (slidy 29–30)
Slidy předvádějí, že do pětice $(G, l, u, c, b)$ se vejdou tři úlohy, které už znáš. Pokaždé jde jen o chytré nastavení pětice.
Zkus sám: jak nastavit $(G, l, u, c, b)$, aby MCF spočítal maximum flow ze $s$ do $t$? Nápověda: MCF minimalizuje — tak ať „víc toku“ znamená „menší cena“.
Žádný uzel nesmí nic vyrábět: $b(v) = 0$ všude (tok jen krouží — cirkulace). Aby vůbec kroužil, přidej hranu $t \to s$ s $u = \infty$ — a té dej cenu $-1$, všem ostatním cenu 0. Každá jednotka, která proteče sítí z $s$ do $t$, se musí vrátit hranou $t \to s$ a „vydělá“ $-1$. Minimalizace ceny pak žene tok hranou $t \to s$ co nejvýš — tedy maximalizuje tok sítí. Optimální cena je $-|f_{max}|$.
The Maximum Flow problem can be polynomially reduced to the Minimum Cost Flow problem:
- Add an edge from $t$ to $s$ with the upper bound equal to $\infty$ and the cost $-1$.
- Set the cost of every other edge to $0$.
- Set $b(v) = 0$ for all nodes including $s$ and $t$.
- Minimum cost circulation (it will be negative) maximizes the flow on the added edge.
The Shortest Path from $s$ to $t$ can be reduced to the Min-Cost Flow:
- Use LP formulation of Min-Cost Flow.
- Set $b(s) = 1$ and $b(t) = -1$. Set $b(v) = 0 \ \forall v \in V \setminus \{s, t\}$.
- Set $l(e) = 0$, $u(e) = \infty$ and $c(e)$ is weight of edge $\forall e \in E$.
- You obtain (primal) LP formulation of the Shortest Path Problem (see the example of totally unimodular matrix $A$ in the ILP lecture).
The Chinese Postman Problem (…go along each street at least once…) can be reduced to the Min-Cost Flow:
- Set $b(v) = 0 \ \forall v \in V$.
- Set $l(e) = 1$, $u(e) = \infty$ and $c(e)$ is weight of edge $\forall e \in E$.
Čti ty pětice jako „rukopisy“: nejkratší cesta = pošli jedinou jednotku z $s$ ($b(s) = 1$) do $t$ ($b(t) = -1$) a plať za vzdálenost — nejlevnější doprava jednotky teče po nejkratší cestě (LP tu má celočíselné optimum díky TUM matici, viz [L3.12]). Listonoš (Chinese postman) = cirkulace ($b \equiv 0$), ale dolní mez $l(e) = 1$ vynutí projet každou ulici aspoň jednou; z výsledného toku se pak skládá Eulerovský tah [L3.8c] — celou úlohu rozebereme v [L4.13].
Reziduální graf dostává ceny (slide 32)
Jak se MCF řeší kombinatoricky (bez LP solveru)? Stejnou filozofií jako max flow: vezmi nějaký přípustný tok a vylepšuj ho v reziduálním grafu. Kapacitní část $G_f$ znáš z [L4.2] — dopředná hrana s rezervou $u - f$, zpětná s rezervou $f - l$. Jenže teď nevylepšujeme velikost, ale cenu — takže každá reziduální hrana musí říkat, kolik její použití stojí.
Zkus sám: dopředná reziduální hrana znamená „pošli po $e$ jednotku navíc“ — ta logicky stojí $c(e)$. Co znamená zpětná hrana a kolik má stát?
Zpětná hrana $(j, i)$ znamená „zruš jednotku toku na $e = (i, j)$“. Za tu jednotku jsi platil $c(e)$ — když ji zrušíš, peníze se vrátí: cena zpětné hrany je $c_f(j, i) = -c(i, j)$. Přesně tahle znaménka dovolí počítat cenu úpravy toku jako obyčejný součet cen podél cesty či cyklu v $G_f$: kladné položky = nově poslané jednotky, záporné = vrácené.
The residual graph shows where an extra capacity might be found. The residual graph $G_f$ is constructed from network $(G, l, u, b, c)$ and specific feasible flow $f$ as follows:
$$ \begin{aligned} G_f &= (V, E_f, u_f, c_f) \\ \bar{E} &= E \cup \{(j, i) : (i, j) \in E\} \\ 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 \\ E_f &= \{(i, j) \in \bar{E} : u_f(i, j) > 0\} \\ 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} $$
Postav teď $G_f$ pro síť a tok z úvodu (ten za 18). Projdi hranu po hraně — u každé vznikne nejvýš dvojice reziduálních hran a do $E_f$ se dostanou jen ty s $u_f > 0$:
Zkus sám: najdi v hotovém $G_f$ cyklus se zápornou součtovou cenou. Co by se stalo, kdybys podél něj poslal tolik jednotek, kolik dovolí nejmenší $u_f$ na cyklu?
Třeba $u \to x \to v \to u$: ceny $1 + (-3) + (-2) = -4 < 0$, kapacity $\min(2, 3, 3) = 2$. Pošli po něm $\gamma = 2$ jednotky: na $u \to x$ tok vzroste o 2, na zpětných úsecích se tok vrátí — $f(v \to x)$ klesne $3 \to 1$ a $f(u \to v)$ klesne $3 \to 1$. Bilance se nezmění (cyklus do žádného uzlu nic nepřidá ani neodebere!), ale cena klesne o $4 \cdot 2 = 8$: z 18 na 10. A v novém $G_f$ je další záporný cyklus ($u \to w \to x \to v \to u$, cena $2 + 1 - 3 - 2 = -2$, $\gamma = 1$) — po něm jsi na ceně $\mathbf{8}$ z prvního try. Záporný cyklus v $G_f$ = sleva beze změny bilancí. Opakovat, dokud nějaký existuje — to je celý algoritmus cycle canceling, příští lekce [L4.11] (záporné cykly najde Bellman-Ford, srov. [L2.12]).
Nebezpečné polopravdy1) Zpětná hrana má cenu $-c(e)$ — ne $0$ a ne $+c(e)$. Bez minusu ti „vrácení jednotky“ účtuje peníze dvakrát a záporné cykly nenajdeš. 2) $u_f(j, i) = f - l$, ne $f$. Stará past z [L4.2] platí dál: vrátit jde jen to, co je nad dolní mezí. 3) Hrany s $u_f = 0$ v $G_f$ nejsou. Nasycená hrana ($f = u$) ztratí dopřednou kopii, nevyužitá ($f = l$) zpětnou — nekresli je „pro jistotu“ s nulou, zkreslí hledání cyklů. 4) Zkontroluj $\sum_v b(v) = 0$ a znaménka: bilanční rovnice je out − in $= b(v)$, takže $b > 0$ je zdroj (výroba), $b < 0$ spotřeba. Když součet nevyjde nula, přípustný tok neexistuje a žádné MCF se nekoná. 5) Cena toku se počítá v původním grafu: $\sum_{e \in E(G)} f(e) c(e)$. Ceny $c_f$ v reziduálním grafu slouží jen k ocenění úprav toku (cest a cyklů) — nesčítej je s tokem.
Key takeaways — L4.10- MCF (slide 28): pětice $(G, l, u, c, b)$, $\sum_v b(v) = 0$; najdi přípustný tok minimalizující $\sum_e f(e) \cdot c(e)$ při bilancích $\sum_{\delta^+(v)} f - \sum_{\delta^-(v)} f = b(v)$ a mezích $l \le f \le u$ — nebo rozhodni, že neexistuje. Ceny smí být záporné.
- LP formulace (slide 29): proměnné $f(e) \ge 0$, lineární cena, bilanční rovnice pro každý uzel, meze na hranách — max-flow LP [L4.1] s vyměněnou účelovou funkcí a bilancemi místo $s$/$t$.
- Reziduální graf s cenami (slide 32): kapacity jako v [L4.2] ($u - f$ dopředně, $f - l$ zpětně, hrany s $u_f = 0$ vypadnou); ceny $c_f(i,j) = c(i,j)$ dopředně a $c_f(j,i) = -c(i,j)$ zpětně — zrušená jednotka cenu vrací.
- MCF je obecný (slidy 29–30): max flow = cirkulace s hranou $t \to s$ ($u = \infty$, $c = -1$, jinde $c = 0$, $b \equiv 0$); shortest path = $b(s) = 1$, $b(t) = -1$, $c$ = váhy; Chinese postman = $b \equiv 0$, $l \equiv 1$.
- Záporný cyklus v $G_f$ = zlevnění toku beze změny bilancí (o $|{\sum c_f}| \cdot \gamma$). Augmentace podél záporných cyklů až do optima = cycle canceling → [L4.11].
Minimum cost flow is an extension of the Maximum Flow problem where we consider the edge costs and the supply/consumption of the nodes.
Instance: A 5-tuple $(G, l, u, c, b)$ where $G$ is a digraph, $u : E(G) \to \mathbb{R}_0^+$ represents the upper bounds, $l : E(G) \to \mathbb{R}_0^+$ the lower bounds, and: cost of arcs $c : E(G) \to \mathbb{R}$, balance $b : V(G) \to \mathbb{R}$ represents the supply/consumption of the nodes and satisfies $\sum_{v \in V(G)} b(v) = 0$.
Goal: Find the feasible flow $f$ that minimizes $\sum_{e \in E(G)} f(e) c(e)$ and satisfies $\sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = b(v)$ for all $v \in V(G)$, or decide that it does not exist.
Studijní otázky (vlastní — přiznáno): (i) Give the LP formulation of the Minimum Cost Flow problem. (ii) Show how the Maximum Flow problem can be polynomially reduced to MCF. (iii) Show how the Shortest Path problem (from $s$ to $t$) and the Chinese Postman Problem can be reduced to MCF.
a) Co je v zadání?
Formulační/teoretická úloha přesně v rozsahu této lekce: definice MCF je dána, po tobě se chce LP model a tři redukce — tedy umět pětici $(G, l, u, c, b)$ „naprogramovat“ tak, aby řešila jinou úlohu. Žádné počítání, jen přesné formulace.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice, LP, redukce (takeaways).
- [L4.1] — max-flow LP pro srovnání.
- [L4.6] — bilance $b(v)$ a podmínka $\sum b = 0$.
- [L3.12] — proč LP nejkratší cesty vrací celočíselné optimum (TUM).
c) Jak nad úlohou uvažovat?
U LP si polož tři otázky: co jsou proměnné, co minimalizuju, jaká omezení mám (bilance + meze). U redukcí hledej, kterým knoflíkem pětice se cílová úloha vynutí: max flow potřebuje zápornou cenu (aby se minimalizaci „vyplatilo“ hnát tok), nejkratší cesta potřebuje bilance $\pm 1$ (jediná jednotka), listonoš potřebuje dolní meze (každá ulice aspoň jednou). Vždycky dopiš i jak z výsledku přečíst odpověď původní úlohy.
d) Úplné řešení (dle textu banky #24, 1:1)
(i) LP formulace. Variable $f(e) \in \mathbb{R}_0^+$ represents the flow on edge $e \in E(G)$:
$$ \begin{aligned} \min \quad & \sum_{e \in E(G)} c(e) f(e) \\ \text{s.t.} \quad & \sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = b(v) & v \in V(G), \\ & l(e) \le f(e) \le u(e) & e \in E(G). \end{aligned} $$
(ii) Max flow → MCF. Add an edge from $t$ to $s$ with upper bound $\infty$ and cost $-1$; set the cost of every other edge to 0; set $b(v) = 0$ for all nodes including $s$ and $t$. The minimum cost circulation (its cost will be negative) maximizes the flow on the added edge — optimální cena je $-|f_{max}|$ a max flow přečteš jako tok na hraně $t \to s$.
(iii) Shortest path → MCF. Set $b(s) = 1$, $b(t) = -1$, $b(v) = 0$ for all $v \in V \setminus \{s, t\}$; set $l(e) = 0$, $u(e) = \infty$ and $c(e)$ equal to the edge weight for all $e \in E$. Vznikne (primární) LP formulace nejkratší cesty — jediná jednotka teče z $s$ do $t$ nejlevněji, tedy po nejkratší cestě; celočíselnost optima zaručuje totální unimodularita matice ([L3.12]).
Chinese postman → MCF. Set $b(v) = 0$ for all $v \in V$; set $l(e) = 1$, $u(e) = \infty$ and $c(e)$ equal to the edge weight for all $e \in E$. Cirkulace s $l = 1$ projede každou hranu aspoň jednou; $f(e)$ říká, kolikrát se hrana projede, a trasa se z toku složí jako Eulerovský tah v multigrafu s $f(e)$ kopiemi hran ([L3.8c]; detailně [L4.13]).
Consider the network $(G, l, u, c, b)$ below with balances $b(a) = +2$, $b(b) = 0$, $b(c) = -2$ and a flow $f$ (edge labels read $l, f, u$ · $c$).
(i) Verify that $f$ is feasible and compute its cost. (ii) Construct the residual graph $G_f$, i.e. list all edges of $E_f$ with their residual capacities $u_f$ and residual costs $c_f$. (iii) Is there a negative-cost cycle in $G_f$? If yes, determine $\gamma$ and the cost of the flow after augmenting along the cycle.
a) Co je v zadání?
Ruční drill dnešní konstrukce: ověřit přípustnost (meze + bilanční rovnice), postavit $G_f$ se dvěma čísly na hraně ($u_f$ a $c_f$) a najít záporný cyklus — tedy přesně ty kroky, které u zkoušky předcházejí cycle cancelingu [L4.11].
b) Co k tomu budeme potřebovat?
- Tato lekce — vzorce $u_f$, $c_f$ a čtení záporného cyklu (takeaways).
- [L4.2] — kapacitní část reziduálního grafu.
- [L4.6] — bilanční rovnice.
c) Jak nad úlohou uvažovat?
Jdi hranu po hraně: každá hrana $E$ vyrobí nejvýš dvě hrany $E_f$ — dopřednou ($u - f$, cena $+c$) a zpětnou ($f - l$, cena $-c$); nulové kapacity škrtni. U cyklu sčítej ceny (rozhodují o znaménku) a z kapacit ber minimum ($\gamma$). Změna ceny toku = (součet cen cyklu) $\times\ \gamma$.
d) Úplné řešení (vlastní — přiznáno)
(i) Přípustnost a cena. Meze: $2 \in [0,3]$, $2 \in [0,2]$, $0 \in [0,2]$ ✓. Bilance (out − in): $a$: $2 + 0 = 2 = b(a)$ ✓; $b$: $2 - 2 = 0$ ✓; $c$: $0 - (2 + 0) = -2$ ✓. Cena $\sum f \cdot c = 2 \cdot 1 + 2 \cdot 4 + 0 \cdot 2 = \mathbf{10}$.
(ii) Reziduální graf. $a \to b$: dopředná $u_f = 3 - 2 = 1$, $c_f = +1$; zpětná $b \to a$: $u_f = 2 - 0 = 2$, $c_f = -1$. $b \to c$: dopředná $u_f = 2 - 2 = 0$ → v $E_f$ není; zpětná $c \to b$: $u_f = 2$, $c_f = -4$. $a \to c$: dopředná $u_f = 2$, $c_f = +2$; zpětná $u_f = 0 - 0 = 0$ → není. Celkem $E_f = \{a \to b\ (1, +1),\ b \to a\ (2, -1),\ c \to b\ (2, -4),\ a \to c\ (2, +2)\}$:
(iii) Záporný cyklus. $a \to c \to b \to a$: cena $2 + (-4) + (-1) = -3 < 0$, $\gamma = \min(2, 2, 2) = 2$. Augmentací tok na $a \to c$ vzroste na 2 a na zpětných úsecích klesne: $f(b \to c): 2 \to 0$, $f(a \to b): 2 \to 0$. Nová cena $= 10 - 3 \cdot 2 = \mathbf{4}$ (kontrola: $2 \cdot 2 = 4$ ✓ — obě jednotky tečou přímo $a \to c$). V novém $G_f$ už záporný cyklus není, takže 4 je optimum — přesně tohle z nás v [L4.11] udělá algoritmus.