Multikomoditní tok (ILP)
Tohle je poslední lekce K4 a uzavírá rodinu toků: max flow [L4.1] → toky s bilancemi [L4.6] → minimum cost flow [L4.10] → a teď víc komodit naráz. U zkoušky se objevuje jako formulační úloha:
„3. Formulace distribuce komodit ze zdrojů do spotřebičů pomocí multicommodity network flow (byla to složitá úloha, kterou nakonec zjednodušovali).“ — Termín A, přepis studentů.
„3) takovy hodne nepovedeny kockopes – formulace distribuce komodit ze zdroju do spotrebicu pomoci multicommodity network flow; problem byl, ze Hanzalek behem testu zjistil, ze to ani sam nedokaze spravne vyresit, tak to zjednodusil…“ — týž termín, druhý přepis. A „Multikomoditní toky“ padly i u zkoušky 24. 5. 2011 (dochovaly se jen fotky zadání).
Poučení z té anekdoty: nikdo po tobě nechce multikomoditní instanci vyřešit ručně (nejde to ani autorovi zkoušky 🙂). Chce se formulace — proměnné, účelová funkce, omezení — a věta o tom, co se stalo s celočíselností. Přesně to je obsah téhle lekce.
Víc komodit v jedné síti
Dosud každá síť přepravovala jedinou „látku“. Slide 35 motivuje změnu senzorovou sítí (citace EN 1:1):
„So far, we have assumed to be transporting just one commodity. Let $M$ be the commodity set transported through the network. Every commodity has several sources and several sinks. Variable $f^m(e) \in \mathbb{R}^+_0$ is the flow of commodity $m \in M$ along edge $e \in E(G)$.“
„Example: sensor network with two commodities and one sink for every commodity: source nodes are measuring temperature (green) and/or humidity (blue) and sending the data to one concentrator (sink) for temperature and one for humidity; flow = amount of data per time unit. Communication links: capacity (amount of data per time unit).“
Klíčové slovo je commodity (komodita): data o teplotě a data o vlhkosti jsou dvě různé „látky“ — nesmí se cestou smíchat (každá musí dorazit do svého koncentrátoru), ale tečou stejnými dráty.
Zkus sám: síť má hrany $E(G)$ a komodity $M$. Kolik tokových proměnných bude mít model? A proč nestačí jedna proměnná $f(e)$ na hranu jako dosud?
$|M| \cdot |E(G)|$ — proměnná $f^m(e)$ pro každou dvojici (komodita, hrana). Jedna proměnná na hranu nestačí, protože by model nevěděl, čí jednotky hranou tečou: tok 3 na hraně může být „3 teploty“, „3 vlhkosti“ nebo „2+1“ — a jen některé z těchto kombinací správně doručí každou komoditu do jejího spotřebiče. Komodity se nesmí cestou „přebarvit“.
Tady je miniaturní instance, na které je vidět to podstatné — sdílené úzké hrdlo:
Zkus sám: komodita ① potřebuje dopravit 2 jednotky $s_1 \to t_1$, komodita ② dvě jednotky $s_2 \to t_2$. Každou komoditu zvlášť umíš vyřešit jako minimum cost flow [L4.10] — obě projdou ($2 \le 3$). Proč ti dvě oddělená řešení nedají řešení celé úlohy?
Obě oddělená optima si naplánují hranu $x \to y$ pro sebe: dohromady by jí teklo $2 + 2 = 4 > 3 = u(x{\to}y)$. Kapacita hrany je sdílená — omezuje součet přes komodity, ne každou komoditu zvlášť. Komodity se tedy o hrany přetahují a model je musí koordinovat: tahle instance jako celek přípustná není (každá jednotka obou komodit musí přes $x \to y$), i když každá komodita sama o sobě projde. Přesně tahle vazba dělá z multikomoditního toku novou úlohu, ne $|M|$ kopií staré.
Definice: Minimum Cost Multicommodity Flow
„Instance: 5-tuple $(G, l, u, c, b^1 \ldots b^m \ldots b^{|M|})$ where $G$ is a digraph with upper bounds $u : E(G) \to \mathbb{R}^+_0$, lower bounds $l : E(G) \to \mathbb{R}^+_0$ and costs $c : E(G) \to \mathbb{R}$ and with: vectors $b^m : V(G) \to \mathbb{R}$ that express supply/consumption of nodes by commodity $m$. $\sum_{v \in V(G)} b^m(v) = 0$ for all commodities $m \in M$.“
„Goal: Find the feasible flow $f$ whose cost $\sum_{e \in E(G)} \sum_{m \in M} f^m(e) \cdot c(e)$ is minimal (we want to transport the flow as cheap as possible) or decide that such a flow does not exist. Feasible flow satisfies $\sum_{e \in \delta^+(v)} f^m(e) - \sum_{e \in \delta^-(v)} f^m(e) = b^m(v)$ for all $v \in V(G)$ and all $m \in M$.“
Porovnej s pěticí $(G, l, u, c, b)$ z [L4.10]: jediná změna je, že místo jednoho bilančního vektoru $b$ je jich $|M|$ kusů — každá komodita má vlastní zdroje ($b^m(v) > 0$), vlastní spotřebiče ($b^m(v) < 0$) a vlastních „kolik kam“. Žádné jediné $s$ a $t$: vícero zdrojů i spotřebičů na komoditu je v definici od začátku (stejný princip bilancí jako v [L4.6]).
Zkus sám: proč definice chce $\sum_v b^m(v) = 0$ pro každou komoditu zvlášť, a ne jen v součtu přes všechny komodity dohromady?
Protože komodity se nepřeměňují jedna v druhou. Kirchhoffova bilance platí per komodita: co komodita $m$ kde vyrobí, musí táž komodita jinde spotřebovat — přebytek teploty nezaplní poptávku po vlhkosti. Kdyby se nulovala jen suma přes komodity, „vyrobených +5 komodity 1 a spotřebovaných −5 komodity 2“ by prošlo kontrolou, ale fyzikálně je to nesmysl. (Sečti bilanční rovnice komodity $m$ přes všechna $v$: každá hrana se objeví jednou s $+$, jednou s $-$, takže nutně $\sum_v b^m(v) = 0$ — pro každé $m$.)
LP formulace: $|M|$ Kirchhoffů + jedno sdílené lano
$$ \begin{aligned} \min \quad & \sum_{e \in E(G)} \sum_{m \in M} f^m(e) \cdot c(e) \\ \text{s.t.} \quad & \sum_{e \in \delta^+(v)} f^m(e) - \sum_{e \in \delta^-(v)} f^m(e) = b^m(v) \qquad & v \in V(G),\ m \in M \\ & l(e) \le \sum_{m \in M} f^m(e) \le u(e) & e \in E(G) \end{aligned} $$
„1st Kirchhoff's law is satisfied in every node for every commodity.“
Zkus sám: které omezení v té formulaci komodity spojuje? A co by se stalo, kdybys ho vypustil?
Jen to poslední: $l(e) \le \sum_{m} f^m(e) \le u(e)$ — kapacita omezuje součet toků všech komodit na hraně. Všechno ostatní (bilanční rovnice i cena) se rozpadá po komoditách: rovnice komodity $m$ obsahují jen proměnné $f^m(\cdot)$ a účelová funkce je prostý součet. Bez sdílených kapacit by úloha byla $|M|$ nezávislých minimum cost flow [L4.10] — vyřešíš každou zvlášť a hotovo. Matice modelu je bloková diagonála (jeden blok = jedna komodita, každý blok sám o sobě TUM) a teprve kapacitní řádky bloky „svážou“. A přesně ty řádky, jak hned uvidíš, rozbijí totální unimodularitu.
U zkoušky („distribuce komodit ze zdrojů do spotřebičů“) tedy odevzdáváš: (1) proměnné $f^m(e) \ge 0$ pro každou komoditu a hranu, (2) Kirchhoffovu bilanci s $b^m(v)$ pro každý vrchol a každou komoditu, (3) sdílené kapacity $l(e) \le \sum_m f^m(e) \le u(e)$, (4) cenu $\min \sum_e \sum_m f^m(e)\, c(e)$ — a (5) větu o celočíselnosti. Tu teď odvodíme.
Co se rozbilo: celočíselnost
- „Multicommodity flow can be solved by LP — in polynomial time.“
- „Integer-valued flow is not assured since matrix $A$ in LP is not totally unimodular (see $l(e) \le \sum_{m \in M} f^m(e) \le u(e)$).“
- „Practical experience: ILP formulation which guarantees integer-valued solution can be solved even for big instances in acceptable time.“
U jednokomoditních toků jsme celočíselnost dostávali zadarmo — incidenční matice je TUM [L3.12], takže vrcholy LP polytopu jsou celé a stačilo LP (nebo rovnou Ford-Fulkerson). Sdílené kapacitní řádky tuhle strukturu zničí. Že to není jen teoretická obava, ukazuje následující instance — orientovaná adaptace klasického protipříkladu se dvěma komoditami (vlastní překreslení, přiznáno; všechny kombinace ověřeny strojově hrubou silou):
Zkus sám (po projití stepperu): každá komodita sama o sobě projde celočíselně. Proč spolu celočíselně neprojdou, ale „na půlky“ ano?
Spočítej, kolik sdílených hran (A, B, C, D, každá $u = 1$) musí každá komodita použít: ① se dostane z $s_1$ do $t_1$ jen přes $\{A, B\}$ nebo $\{D, C\}$, ② z $s_2$ do $t_2$ jen přes $\{B, C\}$ nebo $\{A, D\}$ (delší trasy používají sdílených hran ještě víc). Celočíselně si každá komodita musí vybrat jednu dvojici — a každá volba ① se s každou volbou ② srazí přesně na jedné hraně s kapacitou 1 (zkontroluj všechny 4 kombinace: srážka na B, A, C, resp. D). Zlomkově se ale komodita vybírat nemusí: pošle půl jednotky oběma svými trasami. Pak každou sdílenou hranou teče $\frac12 + \frac12 = 1 \le u$ — LP je přípustné, ILP ne. Zlomky tu nejsou kosmetická vada, kterou „zaokrouhlíš“: žádné celočíselné řešení neexistuje.
Nebezpečné polopravdy1) „Toky vyjdou celočíselně zadarmo“ platí jen pro JEDNU komoditu. Integral Flow Theorem a TUM argument [L3.12] se opírají o čistou incidenční matici; kapacitní řádky $\sum_m f^m(e) \le u(e)$ sčítají přes bloky komodit a TUM zničí. LP relaxace multikomoditního toku může mít jediné optimum/přípustné řešení ve zlomcích (viz instance výše — half-integral, samé poloviny). 2) Zlomkové LP řešení nelze obecně „zaokrouhlit“. V instanci výše celočíselné řešení vůbec neexistuje, přestože LP přípustné je — zaokrouhlování nemá co najít. 3) Ford-Fulkerson ani cycle canceling tady nepoužiješ — to jsou algoritmy pro jednu komoditu. Multikomoditní tok řešíš jako LP (zlomky OK, polynomiálně), a chceš-li celočíselný tok, deklaruješ $f^m(e) \in \mathbb{Z}^+_0$ a řešíš ILP (solver; dle slidu v praxi zvládnutelné i pro velké instance).
Key takeaways — L4.15- Multikomoditní tok: instance $(G, l, u, c, b^1, \ldots, b^{|M|})$ — proměnná $f^m(e)$ pro každou komoditu a hranu, Kirchhoffova bilance $\sum_{\delta^+(v)} f^m - \sum_{\delta^-(v)} f^m = b^m(v)$ per komodita (každá má vlastní zdroje/spotřebiče, $\sum_v b^m(v) = 0$ pro každé $m$).
- Komodity spojuje jediné omezení — sdílené kapacity: $l(e) \le \sum_{m \in M} f^m(e) \le u(e)$. Bez něj by úloha byla $|M|$ nezávislých MCF [L4.10].
- Cena: $\min \sum_e \sum_m f^m(e)\,c(e)$; jako LP řešitelné polynomiálně (ve zlomcích).
- Matice NENÍ TUM [L3.12] (kvůli kapacitním řádkům se součtem přes komodity) → LP může vracet zlomky a celočíselné řešení nemusí vůbec existovat, i když zlomkové ano (klasický protipříklad: 2 komodity, 2 trasy na komoditu, vše půlkové). Pro celočíselný tok deklaruj $f^m(e) \in \mathbb{Z}^+_0$ a řeš ILP.
- U zkoušky je to formulační úloha: proměnné → bilance per komodita → sdílené kapacity → cena → věta o celočíselnosti. Nikdo nechce ruční výpočet.
So far, we have assumed to be transporting just one commodity. Let $M$ be the commodity set transported through the network. Every commodity has several sources and several sinks. Variable $f^m(e) \in \mathbb{R}_0^+$ represents the flow of commodity $m \in M$ along edge $e \in E(G)$.
Instance: A 5-tuple $(G, l, u, c, b^1, \ldots, b^m, \ldots, b^{|M|})$ where $G$ is a digraph with upper bounds $u : E(G) \to \mathbb{R}_0^+$, lower bounds $l : E(G) \to \mathbb{R}_0^+$, costs $c : E(G) \to \mathbb{R}$, and vectors $b^m : V(G) \to \mathbb{R}$ that express supply/consumption of nodes by commodity $m$ and satisfy $\sum_{v \in V(G)} b^m(v) = 0$ for all commodities $m \in M$.
Goal: Find the feasible flow $f$ whose cost $\sum_{e \in E(G)} \sum_{m \in M} f^m(e)\, c(e)$ is minimal, or decide that such a flow does not exist. Feasible flow satisfies $\sum_{e \in \delta^+(v)} f^m(e) - \sum_{e \in \delta^-(v)} f^m(e) = b^m(v)$ for all $v \in V(G)$, all $m \in M$.
Give the LP formulation. Is an integer-valued optimal flow assured? Why?
a) Co je v zadání?
Formulační úloha: zapsat minimum cost multicommodity flow jako LP a vysvětlit, co je s celočíselností. Pozn. ke zdroji: banka přiznává, že přesné originální znění zkoušky se nedochovalo („distribuce komodit ze zdrojů do spotřebičů“, Termín A / fotky 24.5.2011) — tohle je její kanonická rekonstrukce ze slidů 35–37, vedená jako Unsolved; poslední věta zadání (pokyn „Give the LP formulation…“) je naše dopsání, přiznáno. Formulace v řešení je dle banky/slidů 1:1.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice, LP formulace, celočíselnost (takeaways).
- [L4.10] Minimum Cost Flow — jednokomoditní pětice $(G,l,u,c,b)$, na kterou se odkazuješ.
- [L3.12] Teorie ILP/TUM — proč TUM dává celé vrcholy a proč tady chybí.
c) Jak nad úlohou uvažovat?
Postupuj po pěti odevzdávkách z lekce: proměnné (kolik a jaké?), bilance (per komodita!), kapacity (kde je součet přes $m$?), účelová funkce, věta o celočíselnosti. Nejčastější chyba: napsat kapacitu $f^m(e) \le u(e)$ pro každou komoditu zvlášť — tím by sis vyrobil $|M|$ nezávislých úloh a model by dovolil hranu přetížit součtem. U celočíselnosti neříkej jen „není zaručena“ — řekni proč (která část matice rozbíjí TUM) a co s tím (ILP).
d) Úplné řešení (formulace dle banky #26 / slidů 36–37)
Proměnné: $f^m(e) \in \mathbb{R}^+_0$ pro každé $e \in E(G)$ a $m \in M$ (celkem $|M| \cdot |E(G)|$ proměnných).
$$ \begin{aligned} \min \quad & \sum_{e \in E(G)} \sum_{m \in M} f^m(e)\, c(e) \\ \text{s.t.} \quad & \sum_{e \in \delta^+(v)} f^m(e) - \sum_{e \in \delta^-(v)} f^m(e) = b^m(v) \qquad & v \in V(G),\ m \in M \\ & l(e) \le \sum_{m \in M} f^m(e) \le u(e) & e \in E(G) \\ & f^m(e) \ge 0 & e \in E(G),\ m \in M \end{aligned} $$
Komentář k omezením: 1. Kirchhoffův zákon platí v každém vrcholu pro každou komoditu (komodity se nesmí přeměňovat jedna v druhou); kapacita hrany je sdílená — omezuje součet toků všech komodit.
Celočíselnost: NENÍ zaručena. Matice $A$ tohoto LP není totálně unimodulární — bilanční bloky jednotlivých komodit samy o sobě TUM jsou (incidenční matice), ale kapacitní řádky $l(e) \le \sum_m f^m(e) \le u(e)$ sčítají proměnné napříč bloky a TUM rozbijí. LP je řešitelné polynomiálně, ale optimum může vyjít ve zlomcích — a dokonce může existovat zlomkové přípustné řešení, i když žádné celočíselné neexistuje (protipříklad viz T02). Chceme-li zaručeně celočíselný tok, přidáme $f^m(e) \in \mathbb{Z}^+_0$ a řešíme ILP — dle slidu 37 v praxi zvládnutelné i pro velké instance v přijatelném čase.
Consider the network from the figure above (lesson stepper): all arcs have $l(e) = 0$, $u(e) = 1$, $c(e) = 1$. Commodity ① must ship 1 unit from $s_1$ to $t_1$ (i.e. $b^1(s_1) = 1$, $b^1(t_1) = -1$, zero otherwise); commodity ② must ship 1 unit from $s_2$ to $t_2$.
(i) List all routes of each commodity and the shared arcs (A, B, C, D) they use. (ii) Show that no integer-valued feasible multicommodity flow exists. (iii) Find a feasible fractional flow. (iv) What does (ii)+(iii) prove about the constraint matrix of the multicommodity-flow LP?
a) Co je v zadání?
Konkrétní dvanáctivrcholová instance ze stepperu lekce: dvě komodity po jedné jednotce, všechny kapacity 1. Úkol: rozborem tras dokázat, že celočíselně to nejde, zlomkově ano — a vyvodit z toho důsledek pro TUM.
b) Co k tomu budeme potřebovat?
- Tato lekce — sdílené kapacity a sekce o celočíselnosti (takeaways).
- [L3.12] — TUM + celočíselná pravá strana $\Rightarrow$ celé vrcholy polytopu.
c) Jak nad úlohou uvažovat?
(i) Jdi od konce: kterými hranami se dá vstoupit do $t_1$? Do $t_2$? Zpětným trasováním vyjdou trasy. (ii) Spočítej minimum sdílených hran na trasu a projdi všechny kombinace voleb — hledej srážku na hraně s $u = 1$. (iii) Komodita nemusí poslat celou jednotku jednou trasou. (iv) Vzpomeň, co přesně garantuje lemma o TUM z [L3.12] — a co tedy plyne z toho, že tady polytop celočíselný vrchol nemá.
d) Úplné řešení (vlastní — přiznáno; ověřeno strojově hrubou silou)
(i) Trasy. Do $t_1$ vedou jen hrany $b' \to t_1$ a $c' \to t_1$, tedy poslední sdílená hrana komodity ① je B, nebo C. Zpětným trasováním: ① má dvě minimální trasy — $s_1 \to a \xrightarrow{A} a' \to b \xrightarrow{B} b' \to t_1$ (sdílené $\{A, B\}$) a $s_1 \to d \xrightarrow{D} d' \to c \xrightarrow{C} c' \to t_1$ (sdílené $\{D, C\}$); delší varianty ($\{A,B,C\}$, $\{A,D,C\}$) používají sdílené hrany tři. Symetricky ② : $s_2 \to b \xrightarrow{B} b' \to c \xrightarrow{C} c' \to t_2$ ($\{B, C\}$) a $s_2 \to a \xrightarrow{A} a' \to d \xrightarrow{D} d' \to t_2$ ($\{A, D\}$). Každá trasa každé komodity používá aspoň 2 ze čtyř sdílených hran A, B, C, D.
(ii) Celočíselně to nejde. Celočíselný tok komodity = volba jedné trasy (kapacity jsou 1). Projdi všechny kombinace minimálních tras: $\{A,B\} \cap \{B,C\} = \{B\}$, $\{A,B\} \cap \{A,D\} = \{A\}$, $\{D,C\} \cap \{B,C\} = \{C\}$, $\{D,C\} \cap \{A,D\} = \{D\}$ — každá kombinace se srazí na jedné sdílené hraně, kde by muselo téct $1 + 1 = 2 > u = 1$. Delší trasy mají sdílených hran víc, takže srážce také neuniknou (formálně: obě komodity dohromady potřebují $\ge 4$ průchodů sdílenými hranami a kapacita všech čtyř dohromady je přesně 4, takže každá komodita musí použít právě 2 — tedy jen minimální trasy, a ty se vždy protnou). Celočíselné přípustné řešení neexistuje. (Ověřeno i hrubou silou přes všechny 0/1 toky obou komodit.)
(iii) Zlomkově to jde. Každá komodita pošle $\frac12$ jednotky oběma svými trasami: ① půl přes $\{A,B\}$, půl přes $\{D,C\}$; ② půl přes $\{B,C\}$, půl přes $\{A,D\}$. Bilance sedí (z $s_1$ odteče $\frac12 + \frac12 = 1$, do $t_1$ přiteče 1; stejně ②) a každou sdílenou hranou teče $\frac12 + \frac12 = 1 = u(e)$, spojkami $\frac12 \le 1$. Přípustné.
(iv) Důsledek pro matici. Vstupní data jsou celá ($u \equiv 1$, $b^m \in \{0, \pm 1\}$), polytop je neprázdný, ale neobsahuje žádný celočíselný bod. Podle lemmatu z [L3.12] má polyedr $\{x : Ax \le b\}$ s TUM maticí $A$ a celočíselným $b$ všechny vrcholy celočíselné — tady vrchol celočíselný není (jediná přípustná struktura je půlková), takže matice multikomoditního LP totálně unimodulární není. Viníkem jsou kapacitní řádky $\sum_m f^m(e) \le u(e)$, které sčítají přes komoditní bloky.