L4.14 Kapitola K4 — Toky a řezy (Slot 4) · [MUST]

Max flow s logickými omezeními (ILP)

Jedna nová věc Maximální tok umíš zapsat jako LP [L4.1]. Dnes z něj uděláš ILP a přidáš do něj logiku: indikátor použití hrany, prahy „když, tak aspoň…“, povinné hrany, liché hodnoty toku a OR/implikace — vším, co už znáš z K1 (binární přepínače [L1.5], big-M [L1.4], logické formule [L1.3]). Tedy omezení, která čistá síť (a Ford-Fulkerson) z principu neumí.

Tohle je doložená zkoušková kombinace dvou slotů: vezmi tok z K4 a modeluj nad ním jako v K1. Studentské přepisy zkoušek 2023 ji popisují takhle (obojí CZ zápisky, 1:1):

Doloženo u zkoušek 2023 (přepisy studentů, 1:1)

„5. ILP pro max flow plus extra podminky (formulace logickych podminek typu OR, implikace, atd. podobne jako u toho ILP s investicema do baraku)“ — termín 12. 6. 2023.

„1. ILP formulace max flow s extra podmínkami (např. přes množinu M, liché hodnoty, $y$ větší než 1 pokud je $x$ nenulové,...)“ — Termín A.

„ILP s investicema do baráků“ je Real Estate Investment ze slidů 02_ILP — přesně ten, na kterém stojí [L1.3]. Nic nového se tedy učit nebudeš: nová je jen kombinace — proměnné nejsou binární volby domů, ale toky $f(e)$ na hranách.

Kostra: max-flow LP z [L4.1]

Základ modelu je pořád stejný — LP ze slidu 8, které jsme odvodili v [L4.1] (tady jen připomenutí, ne nový výklad): proměnná $f(e)$ pro každou hranu, Kirchhoff [L4.1] v každém vnitřním vrcholu, meze na hranách:

$$ \begin{aligned} \max \quad & \sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e) \\ \text{s.t.} \quad & \sum_{e \in \delta^-(v)} f(e) = \sum_{e \in \delta^+(v)} f(e) \qquad & v \in V(G) \setminus \{s, t\} \\ & l(e) \le f(e) \le u(e) & e \in E(G) \end{aligned} $$

Zkus sám: tohle LP vyřeší Ford-Fulkerson [L4.3]. Které z následujících čtyř požadavků zvládne síť „sama o sobě“ (jen volbou $l, u$) — a které už ne? ① hranou $e$ musí téct aspoň jedna jednotka; ② tok na $e$ musí být lichý; ③ když se $e$ použije, musí nést aspoň 2 jednotky; ④ použije se hrana $e_1$, nebo $e_2$, ale ne obě.

Jen ①: „aspoň jedna jednotka“ je obyčejná dolní mez $l(e) = 1$ — tu má síť v definici od začátku ([L4.1], a jak s ní FF startuje, řeší [L4.7]). Zbylé tři jsou logika: ② lichost není interval, ③ je podmíněný požadavek „když…, tak…“ (množina přípustných hodnot $\{0\} \cup [2, u]$ — díra uprostřed!), ④ je XOR mezi hranami. Množiny přípustných řešení přestávají být „krabice“ $l \le f \le u$ — a přesně tam končí FF a začíná ILP.

Krok 1: prohlásit tok za ILP

První věta každého řešení: proměnné prohlásíme za celočíselné, $f(e) \in \mathbb{Z}^+_0$. U čistého max flow to nic nezmění — celočíselné optimum existuje zadarmo (Integral Flow Theorem, citovali jsme v [L4.5]; plyne z totální unimodularity incidenční matice [L3.12]). Jakmile ale přidáš binární přepínače a big-M, tahle pěkná struktura se rozbije a celočíselnost už není automatická — musí být v modelu napsaná a úlohu řeší ILP solver, ne Ford-Fulkerson.

Katalog: logika nad tokem

Teď to hlavní — překlady jednotlivých logických požadavků. Všechny jsou recyklací K1, jen za „množství“ dosazuješ tok $f(e)$.

① Indikátor: $y_e = 1 \iff$ hranou něco teče

Zkus sám: zaveď binární $y_e \in \{0,1\}$, která má hlásit „hrana $e$ je použitá“ ($f(e) > 0$). Jak ji svážeš s $f(e)$ — a jaké big-M je tady to přirozené? (Vzpomeň na aktivaci z [L1.5]: stroj se pronajme, právě když se produkt vyrábí.)

Stejná dvojice nerovností jako u stroje ze slidu 35 ($x_i \le 100 y_i$, $x_i \ge y_i$) — pozor, na rozdíl od slidu 35 druhou nerovnost $f(e) \ge y_e$ nelze vypustit: indikátor $y_e$ tu na rozdíl od onoho slidu není penalizován v účelové funkci, takže ho do jedničky musíme vynutit explicitně:

$$f(e) \le u(e) \cdot y_e, \qquad f(e) \ge y_e.$$

První říká „$y_e = 0 \Rightarrow f(e) = 0$“, tedy obměnou „$f(e) > 0 \Rightarrow y_e = 1$“ (to je přesně to zkouškové „$y$ větší než $1$ pokud je $x$ nenulové“ — přesněji $y_e \ge 1$, tj. $y_e = 1$). Druhá vynucuje opačný směr „$y_e = 1 \Rightarrow f(e) \ge 1$“; funguje, protože tok je celočíselný. A přirozené big-M je kapacita hrany $u(e)$ — víc než $u(e)$ stejně téct nemůže, takže $f(e) \le u(e) y_e$ pro $y_e = 1$ nic nepřidává a pro $y_e = 0$ vypne hranu.

② Práh: „když se hrana použije, ať nese aspoň $L$“

Stačí v indikátorové dvojici zesílit druhou nerovnost:

$$f(e) \le u(e) \cdot y_e, \qquad f(e) \ge L \cdot y_e.$$

Pro $y_e = 0$ je $f(e) = 0$, pro $y_e = 1$ je $L \le f(e) \le u(e)$. Přípustné hodnoty: $\{0\} \cup [L, u(e)]$ — nekonvexní množina s dírou, kterou LP samo popsat neumí (stejný jev jako u fixed-charge [L1.6]).

③ Tok musí projít množinou $M$

Zkus sám: „tok musí projít hranou $e_0$“ — potřebuješ na to vůbec ILP? A co „tok musí projít vrcholem $v_0$“ nebo „aspoň jednou hranou z množiny $M$“?

Povinná jedna konkrétní hrana je nejlehčí případ z celé lekce: $f(e_0) \ge 1$ — to je obyčejná dolní mez $l(e_0) = 1$, čistá síť (viz try výše). Povinný vrchol $v_0$: aspoň jednotka musí do $v_0$ vtéct, $\sum_{e \in \delta^-(v_0)} f(e) \ge 1$ (díky Kirchhoffovi pak i vytéct). Ale „aspoň jedna hrana z množiny $M$“ už je OR — přes indikátory z bodu ①:

$$\sum_{e \in M} y_e \ge 1.$$

Pozor na rozdíl: $\sum_{e \in M} f(e) \ge 1$ by povolilo „rozdrobit“ jednotku na poloviny mezi víc hran, kdyby tok nebyl celočíselný — s indikátory a celočíselností je sémantika čistá. (A „každou hranou z $M$“ = $f(e) \ge 1$ pro všechna $e \in M$, zase jen dolní meze.)

④ Liché hodnoty toku

Zkus sám: jak zapíšeš lineárně „$f(e)$ je liché“? Nápověda: lichá čísla jsou $1, 3, 5, \ldots$ — umíš je všechna vyrobit z jedné celočíselné proměnné?

Zavedeš novou celočíselnou pomocnou proměnnou $k_e$ a napíšeš lichost jako rovnost:

$$f(e) = 2k_e + 1, \qquad k_e \in \mathbb{Z}^+_0.$$

Žádná nerovnost s big-M — parita se kóduje substitucí. Klíčové je $k_e \in \mathbb{Z}$: bez celočíselnosti $k_e$ rovnost nic neříká ($k_e = 0{,}75$ by „povolilo“ $f(e) = 2{,}5$). Sudost by analogicky byla $f(e) = 2k_e$. Tohle je ukázkový příklad omezení, které síťový algoritmus nemůže umět nikdy — FF augmentuje po cestách a o paritě jednotlivé hrany nemá ponětí.

⑤ Logika mezi hranami: implikace, XOR, OR

Jakmile máš indikátory $y_e$, je zbytek doslova [L1.3] (tam s domy, tady s hranami):

Implikace „použiješ-li $e_1$, použij i $e_2$“: $y_{e_1} \le y_{e_2}$.
Zákaz kombinace „$e_1$ a $e_2$ ne současně“: $y_{e_1} + y_{e_2} \le 1$.
XOR „právě jedna z $e_1, e_2$“: $y_{e_1} + y_{e_2} = 1$.
OR mezi celými nerovnostmi (např. „$f(e_1) + f(e_2) \le 3$ nebo $f(e_3) \ge 2$“): big-M přepínač přesně podle slidu 37 a [L1.4] — ke každé nerovnosti $+M y$ resp. $+M(1-y)$.

Příklad: co logika udělá s optimem

Zkouškové znění se nedochovalo s konkrétním grafem (viz T01) — následující čtyřvrcholová síť je naše vlastní, abychom efekt logických omezení viděli na číslech:

Zkus sám: než kliknutím projdeš stepper — čistý max flow je 5. Oč klesne optimum, když přidáš ③-styl podmínku „když se $a \to b$ použije, ať nese aspoň 2“? Rozeber obě hodnoty přepínače $y_{ab}$.

Na 4. Větev $y_{ab} = 0$ ($f(a{\to}b) = 0$): přes $a$ proteče nejvýš $u(a{\to}t) = 2$, přes $b$ nejvýš $u(s{\to}b) = 2$, celkem 4. Větev $y_{ab} = 1$ ($f(a{\to}b) \ge 2$): do $a$ vteče nejvýš 3, z toho aspoň 2 odbočí do $b$, takže $f(a{\to}t) \le 1$; do $b$ vteče $f(s{\to}b) + f(a{\to}b) \le 2 + 2$, ale ven smí jen $u(b{\to}t) = 3$ — celkem $1 + 3 = 4$. Maximum z obou větví: $\mathbf{4}$. Jediná hodnota, kterou logika zakázala, je přitom $f(a{\to}b) = 1$ — a přesně na ní stálo optimum 5.

Nebezpečné polopravdy

1) Ostrá nerovnost „$f(e) > 0$“ v (I)LP neexistuje. Piš $f(e) \ge 1$ (celočíselný tok), resp. $f(e) \ge \varepsilon$ u spojitého — viz [L1.5]. 2) Big-M u toků není „libovolně velké číslo“: přirozená a nejtěsnější volba je $M = u(e)$. Když je $u(e) = \infty$, musíš $M$ stejně konečně omezit (např. $\sum_{e \in \delta^+(s)} u(e)$ — víc než celý tok hranou nepoteče). 3) „Tok vyjde celočíselně zadarmo“ po přidání logiky UŽ NEPLATÍ. Integralita z TUM [L3.12] se týká čisté tokové matice; big-M řádky a pomocné proměnné ji rozbijí — celočíselnost $f$, $y$, $k$ deklaruj a počítej s tím, že LP relaxace může vyjít zlomkově. 4) Tohle už neřeší Ford-Fulkerson. FF je správný pro čistý max flow; s logikou je úloha obecné ILP (a obecné ILP je NP-těžké) — u zkoušky se chce formulace, ne běh algoritmu.

Key takeaways — L4.14

Tok jako ILP: kostra = max-flow LP [L4.1] (Kirchhoff + meze) + deklarace $f(e) \in \mathbb{Z}^+_0$. Bez logiky se nic nemění (integralita zadarmo [L3.12]), s logikou je celočíselnost povinná a řeší se solverem, ne FF.
Indikátor použití hrany: $f(e) \le u(e)\,y_e$ a $f(e) \ge y_e$, $y_e \in \{0,1\}$ — kapacita $u(e)$ je přirozené big-M. Práh „když, tak aspoň $L$“: $f(e) \ge L\,y_e$.
Průchod množinou $M$: povinná hrana = dolní mez $f(e) \ge 1$ (to umí i čistá síť!); povinný vrchol = $\sum_{\delta^-(v)} f \ge 1$; „aspoň jedna z $M$“ = $\sum_{e \in M} y_e \ge 1$.
Lichý tok: $f(e) = 2k_e + 1$, $k_e \in \mathbb{Z}^+_0$ — parita se kóduje substitucí s novou celočíselnou proměnnou, ne big-M.
Logika mezi hranami = [L1.3] nad indikátory ($y_{e_1} \le y_{e_2}$, XOR $y_{e_1}+y_{e_2}=1$, …); OR mezi nerovnostmi = big-M [L1.4].

T01 Maximum flow with additional logical constraints zdroj: banka #2 (zkoušky 2023, Termín A) — kanonické znění, EN 1:1

Assignment (task bank #2, EN 1:1)

Canonical practice task: Given a directed network $(G, l, u, s, t)$, formulate the maximum $s$-$t$ flow problem as an ILP/LP. Extend the formulation with additional logical constraints such as:

flow must pass through a specified set of arcs or vertices $M$;
selected arc flows must be odd integer values;
a binary variable $y_e$ must indicate whether $f(e) > 0$;
if an arc is used, its flow must be at least a given positive threshold.

State all additional variables and big-$M$ constants needed.

a) Co je v zadání?

Formulační úloha bez konkrétního grafu: napsat max-flow ILP a pak po jednom přeložit čtyři logické požadavky. Pozn. ke zdroji: banka přiznává, že přesné originální znění zkoušky se nedochovalo — tohle je její kanonická rekonstrukce podle přepisů termínů 2023 („přes množinu M, liché hodnoty, $y$ … pokud je $x$ nenulové“); řešení níže je naše vlastní (banka úlohu vede jako Unsolved).

b) Co k tomu budeme potřebovat?

Tato lekce — celý katalog ①–⑤ (takeaways).
[L4.1] Síť, tok, Kirchhoffův zákon — max-flow LP.
[L1.5] Navázání binární na spojitou (aktivace) — dvojice $f \le M y$, $f \ge y$.
[L1.4] big-M: disjunkce omezení — kdyby padlo i OR mezi nerovnostmi.

c) Jak nad úlohou uvažovat?

Drž pevné pořadí: ① kostra (proměnné, účelová funkce, Kirchhoff, meze) + věta o celočíselnosti; ② ke každému požadavku nejdřív řekni, jaké nové proměnné zavádíš a co znamenají, pak napiš nerovnosti a u každé jednou větou ověř oba směry (co dělá pro $y = 0$, co pro $y = 1$). Big-M nikdy nenech „nějaké velké“ — pojmenuj ho: $M = u(e)$. A nezapomeň na poslední větu zadání — výčet všech pomocných proměnných a konstant je explicitní odevzdávka.

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

① Kostra (max flow jako ILP). Proměnná $f(e)$ = tok hranou $e$, pro každé $e \in E(G)$:

Bez dalších omezení by stačilo LP (celočíselné optimum existuje díky totální unimodularitě [L3.12]); s logickými omezeními níže je celočíselnost nutné deklarovat.

② Indikátor $y_e \iff f(e) > 0$. Nová proměnná $y_e \in \{0,1\}$ pro každou sledovanou hranu:

$$f(e) \le u(e) \cdot y_e, \qquad f(e) \ge y_e.$$

První nerovnost: $f(e) > 0 \Rightarrow y_e = 1$ (big-M je tu kapacita, $M = u(e)$; pro $u(e) = \infty$ vezmi $M = \sum_{e' \in \delta^+(s)} u(e')$). Druhá: $y_e = 1 \Rightarrow f(e) \ge 1$ (platí díky celočíselnosti $f$). Dohromady $y_e = 1 \iff f(e) \ge 1$.

③ Práh při použití hrany. Pro hranu $e$ s prahem $L_e > 0$ (tatáž $y_e$):

$$f(e) \le u(e) \cdot y_e, \qquad f(e) \ge L_e \cdot y_e.$$

Přípustné hodnoty $f(e) \in \{0\} \cup [L_e, u(e)]$: buď hrana neteče vůbec, nebo aspoň $L_e$.

④ Průchod množinou $M$. Tři varianty podle čtení zadání:

každou hranou $e \in M$: $f(e) \ge 1$ pro všechna $e \in M$ (jen dolní meze, $l(e) := 1$);
aspoň jednou hranou z $M$: $\sum_{e \in M} y_e \ge 1$ s indikátory z bodu ②;
vrcholem $v \in M$: $\sum_{e \in \delta^-(v)} f(e) \ge 1$ (Kirchhoff pak zaručí i výtok).

⑤ Liché hodnoty toku. Pro každou vybranou hranu $e$ nová celočíselná proměnná $k_e$:

$$f(e) = 2k_e + 1, \qquad k_e \in \mathbb{Z}^+_0.$$

Výčet (poslední věta zadání): pomocné proměnné $y_e \in \{0,1\}$ (indikátory použití, body ②③④) a $k_e \in \mathbb{Z}^+_0$ (parita, bod ⑤); konstanty $M = u(e)$ u každé indikátorové nerovnosti (u nekonečné kapacity $M = \sum_{e' \in \delta^+(s)} u(e')$), prahy $L_e$ ze zadání. Úloha se po přidání těchto omezení řeší jako obecné ILP — Ford-Fulkerson na ni nestačí.

T02 Logic drill — kolik stojí logika zdroj: VLASTNÍ procvičovací instance (zkouškové zadání graf nedává)

Assignment (EN, vlastní — přiznáno)

Consider the network in the figure above (lesson example): source $s$, sink $t$, arc labels are capacities $u(e)$, all lower bounds are $l(e) = 0$.

(i) Formulate the maximum flow problem as an ILP and find the maximum flow value. (ii) Add the constraint „if arc $(a,b)$ carries any flow, it must carry at least 2 units“ — write the constraints and find the new optimum. (iii) Instead, add the constraint „the flow on arc $(s,b)$ must be an odd integer“ — write the constraints and find the new optimum. (iv) For both cases explain why Ford-Fulkerson cannot be used directly.

a) Co je v zadání?

Konkrétní pětihranná síť z lekce. Postupně: čistý max flow (i), prahová logika na $a \to b$ (ii), parita na $s \to b$ (iii) a zdůvodnění, proč je to po přidání logiky jiná třída úloh (iv).

b) Co k tomu budeme potřebovat?

Tato lekce — katalog ②④ a příklad (takeaways).
[L4.1] — LP kostra a hodnota toku $|f|$.
[L4.4] — řez jako horní mez (rychlá kontrola optim).

c) Jak nad úlohou uvažovat?

(i) najdi tok i řez stejné hodnoty. (ii) rozeber obě hodnoty přepínače $y_{ab}$ zvlášť — v každé větvi je to zase obyčejný max flow s upravenými mezemi, vyhraje lepší větev. (iii) jaké hodnoty vůbec smí $f(s{\to}b)$ mít při $u = 2$? Zbude jediná. (iv) vzpomeň, co přesně FF garantuje a nad jakou množinou přípustných toků pracuje.

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

(i) Kostra: $\max f(s{\to}a) + f(s{\to}b)$ za Kirchhoffů $f(s{\to}a) = f(a{\to}t) + f(a{\to}b)$ (vrchol $a$), $f(s{\to}b) + f(a{\to}b) = f(b{\to}t)$ (vrchol $b$), mezí $0 \le f(e) \le u(e)$ a $f(e) \in \mathbb{Z}^+_0$. Optimum $|f| = \mathbf{5}$: $f(s{\to}a) = 3$, $f(a{\to}t) = 2$, $f(a{\to}b) = 1$, $f(s{\to}b) = 2$, $f(b{\to}t) = 3$. Certifikát: řez $A = \{s\}$ má kapacitu $u(s{\to}a) + u(s{\to}b) = 3 + 2 = 5 = |f|$ [L4.4].

(ii) Nové: $y_{ab} \in \{0,1\}$, $f(a{\to}b) \le 2 y_{ab}$, $f(a{\to}b) \ge 2 y_{ab}$ (zde práh $L = 2 = u(a{\to}b)$, takže se obě slijí do $f(a{\to}b) = 2y_{ab}$, tj. $f(a{\to}b) \in \{0, 2\}$). Větev $y_{ab} = 0$: přes $a$ nejvýš $u(a{\to}t) = 2$, přes $b$ nejvýš $u(s{\to}b) = 2$, celkem 4 (dosažitelné: $2{+}2$). Větev $y_{ab} = 1$: $f(a{\to}t) \le 3 - 2 = 1$ a $f(b{\to}t) \le 3$, celkem $\le 4$ (dosažitelné: $f(s{\to}a)=3$, $f(a{\to}b)=2$, $f(a{\to}t)=1$, $f(s{\to}b)=1$, $f(b{\to}t)=3$). Nové optimum $\mathbf{4}$ — logika stojí jednotku toku, protože zakázala přesně hodnotu $f(a{\to}b) = 1$, na které stálo optimum 5.

(iii) Nové: $f(s{\to}b) = 2k + 1$, $k \in \mathbb{Z}^+_0$. Protože $u(s{\to}b) = 2$, jediná lichá přípustná hodnota je $f(s{\to}b) = 1$ (tj. $k = 0$). Pak $|f| = f(s{\to}a) + f(s{\to}b) \le 3 + 1 = 4$, a 4 se dosáhne: $f(s{\to}a) = 3$, $f(a{\to}t) = 2$, $f(a{\to}b) = 1$, $f(s{\to}b) = 1$, $f(b{\to}t) = 2$. Nové optimum $\mathbf{4}$.

(iv) FF je korektní pro přípustné toky tvaru $l \le f \le u$ s Kirchhoffem — augmentace po cestě zachovává přípustnost a věta o maximalitě stojí na reziduálním grafu [L4.2]. V (ii) je množina přípustných hodnot $f(a{\to}b)$ nekonvexní ($\{0, 2\}$ — augmentace o $\gamma = 1$ by z přípustného toku udělala nepřípustný), v (iii) totéž s paritou ($\{1\}$ z intervalu $[0,2]$). Takové množiny síťový model nepopíše; úloha se řeší jako obecné ILP (a obě naše optima jsme našli rozborem větví binárního přepínače — přesně to dělá branch & bound).

Lekci mám hotovou