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

Matrix rounding přes toky

Jedna nová věc Konzistentní zaokrouhlení matice = celočíselný tok v síti $s \to$ řádky $\to$ sloupce $\to t$, kde každá zaokrouhlovaná hodnota $a$ je hrana s mezemi $[\lfloor a \rfloor, \lceil a \rceil]$. Celočíselnost toku (Dantzig-Fulkerson / TUM) pak zaručí, že tok je zaokrouhlení — a protože matice sama je přípustný frakční tok, řešení existuje pro libovolný vstup.

V [L4.5] jsi viděl, že vrstvená síť umí kódovat přiřazení („kdo koho nominuje“). Dnes stejný trik použijeme na úlohu, která na první pohled s toky nemá nic společného: zaokrouhlování matice. Je to druhý příklad ze série „Integrality and Existence of Lower Bound“ (slide 20, [AMO93]) — a zkoušková klasika: chodila v testu 2 (2013/14) i v teoretickém testu, kde po tobě chtějí formulaci, zdůvodnění celočíselnosti a feasibility (úloha T01 dole). Hodí se ti přitom skoro celá kapitola: dolní meze a přípustnost [L4.1], běh Ford-Fulkersona [L4.3], řez jako certifikát [L4.4] a počáteční tok při $l > 0$ [L4.7].

Úloha: konzistentní zaokrouhlení (slide 20)

Slide 20 — Example Flow.lower.rounding: Matrix Rounding Problem - Integrality and Existence of Lower Bound [AMO93] (text níže 1:1)

This application is concerned with consistent rounding of the elements, row sums, and column sums of a matrix. We are given a $3 \times 3$ matrix of real numbers $x_{ij}$ with row sums vector $r$ and column sums vector $c$. We can round any real number $a \in \{x_{11} \ldots x_{33}, r_1 \ldots r_3, c_1 \ldots c_3\}$ to the next smaller integer $\lfloor a \rfloor$ or to the next larger integer $\lceil a \rceil$, and the decision is completely up to us. The problem requires that we round all matrix elements and the following constraints hold:

We refer to such rounding as a consistent rounding. The objective is to maximize the sum of matrix entries (due to the constraint it is equal to the sum of the row sums and at the same time to the sum of the column sums).

Celou lekci odpracujeme na konkrétní matici z [AMO93] (Figure 6.2; tatáž čísla má i studentský souhrn, str. 8–9):

$$\begin{array}{ccc|c} x_{ij} & & & r_i \\ \hline 3.1 & 6.8 & 7.3 & 17.2 \\ 9.6 & 2.4 & 0.7 & 12.7 \\ 3.6 & 1.2 & 6.5 & 11.3 \\ \hline c_j:\ 16.3 & 10.4 & 14.5 & \end{array}$$

Každé z 15 čísel (9 prvků + 3 řádkové součty + 3 sloupcové součty) smíš nahradit dolní nebo horní celou částí — ale tak, aby zaokrouhlené řádky a sloupce pořád „seděly“ se zaokrouhlenými součty.

Zkus sám: kolik je kandidátních zaokrouhlení? A proč nepomůže „zaokrouhli každé číslo k nejbližšímu celému“?

Každé z 15 čísel má 2 možnosti → $2^{15} = 32\,768$ kandidátů (a pro matici $m \times n$ obecně $2^{mn + m + n}$ — exponenciálně). A běžné „k nejbližšímu“ konzistenci snadno rozbije: první řádek by dal $3 + 7 + 7 = 17$, ale $r_1 = 17.2$ se zaokrouhlí na $17$ — náhodou OK; jenže třetí sloupec: $7 + 1 + 7 = 15$, zatímco $c_3 = 14.5 \to 14$ nebo $15$… a druhý řádek $10 + 2 + 1 = 13$ vs. třetí prvek $0.7 \to 1$ — podmínky se navzájem svazují přes celou matici. Potřebujeme nástroj, který umí všechna lokální rozhodnutí provázat globální podmínkou „součty sedí“. V téhle kapitole takový nástroj máme: Kirchhoffův zákon.

Zkus sám: každý prvek $x_{ij}$ figuruje přesně v jedné řádkové a přesně v jedné sloupcové podmínce. Když uděláš z řádků a sloupců uzly — co bude $x_{ij}$?

Hrana $R_i \to C_j$. Prvek „spojuje“ svůj řádek se svým sloupcem — a hrana v grafu spojuje přesně dva uzly. Řádková podmínka pak bude Kirchhoffova rovnice v uzlu $R_i$ (vše, co do řádku přiteče, se rozdělí mezi jeho prvky), sloupcová v uzlu $C_j$. Zbývá dodat, odkud řádkové součty přitékají a kam sloupcové odtékají: zdroj $s$ a stok $t$. Vyšla nám přesně vrstvená síť z [L4.5] — tentokrát ale omezení nekódují kapacity, nýbrž dvojice mezí.

Konstrukce sítě: meze $[\lfloor a \rfloor, \lceil a \rceil]$

Zkus sám: jak jazykem toků říct „tahle hodnota musí být $\lfloor a \rfloor$, nebo $\lceil a \rceil$ — nic jiného“?

Dej hraně dolní mez $l(e) = \lfloor a \rfloor$ a horní mez $u(e) = \lceil a \rceil$. Pro neceločíselné $a$ je v intervalu $[\lfloor a \rfloor, \lceil a \rceil]$ právě dvojice celých čísel $\lfloor a \rfloor$ a $\lceil a \rceil$ — takže celočíselný tok na té hraně nemá jinou možnost než být zaokrouhlením $a$. (Pro celé $a$ je $\lfloor a \rfloor = \lceil a \rceil = a$ a hrana je fixovaná — i to je správně, celé číslo se „zaokrouhlí“ samo na sebe.) Slovo „celočíselný“ tu nese celou váhu — vrátíme se k němu za chvíli.

Konstrukce pro matici $m \times n$ (u nás $3 \times 3$):

Tatáž konstrukce ve vzpomínce na test 2 (2013/14), přepis wiki CZ 1:1

„Zaokrouhlování prvků matice 3×3 (nahoru dolu), aby se řádková resp. sloupcová suma (pro všechny ř/s) rovnaly — probráno na přednáškách — zdroj toku → řádky → sloupce → sink — hrany maji omezení součet zaokrouhleni nahoru nebo dolu dle významu.“

Zkus sám: napiš Kirchhoffovu rovnici pro uzel $R_2$. Co přesně říká?

$f(s \to R_2) = f(R_2 \to C_1) + f(R_2 \to C_2) + f(R_2 \to C_3)$ — tedy zaokrouhlený řádkový součet $=$ součet zaokrouhlených prvků druhého řádku. To je doslova první podmínka konzistence ze zadání! A symetricky v $C_j$: vše, co do sloupcového uzlu přiteče (zaokrouhlené prvky sloupce), odteče hranou $C_j \to t$ (zaokrouhlený sloupcový součet) — druhá podmínka. Konzistence není nic, co bychom museli „hlídat“: vynucuje ji Kirchhoffův zákon [L4.1] sám od sebe. Přípustný celočíselný tok $\iff$ konzistentní zaokrouhlení.

A účelová funkce? Hodnota toku $|f| = \sum_i f(s \to R_i)$ je součet zaokrouhlených řádkových součtů = celkový součet zaokrouhlené matice. Maximalizovat součet prvků = najít maximální tok.

Proč z toho vypadne zaokrouhlení: celočíselnost

Zkus sám: tok je obecně reálné číslo — klidně $f(R_1 \to C_1) = 3.5 \in [3, 4]$. Proč se na výstupu přesto můžeme spolehnout na celá čísla?

Všechny meze $\lfloor a \rfloor, \lceil a \rceil$ jsou celé. Podle Integral Flow Theorem (Dantzig-Fulkerson, slide 17 — citovaný v [L4.5]) pak existuje celočíselný maximální tok; Ford-Fulkerson ho navíc rovnou najde, protože startuje z celočíselného toku a každé $\gamma$ vyjde celé [L4.3]. Hlubší důvod znáš z [L3.12]: incidenční matice digrafu je totálně unimodulární, takže polyedr toků má celočíselné vrcholy a LP = ILP. Celočíselný tok v mezích $[\lfloor a \rfloor, \lceil a \rceil]$ už nemá jinou možnost než být zaokrouhlením — přesně jak jsme si připravili v konstrukci.

Slide 17 — Integrality, 1:1 (věta + zdůvodnění přes TUM)

If the capacities of the network are integers, and there exists a feasible flow, then there exists an integer-valued maximum flow. This follows from total unimodularity of the incidence matrix of a digraph $G$, which is matrix $\mathbf{A}$ in LP formulation $\mathbf{A} \cdot x \le b$.

Feasibilita pro libovolný vstup: certifikát zadarmo

Věta nahoře má předpoklad: „and there exists a feasible flow“. U sítí s $l > 0$ přípustný tok existovat nemusí (drill [L4.1] T02) — tady ale ano, a to vždy:

Zkus sám: najdi přípustný (klidně neceločíselný) tok v naší síti — bez jediného výpočtu. Nápověda: máš ho celou dobu před očima.

Matice sama. Polož $f(R_i \to C_j) = x_{ij}$, $f(s \to R_i) = r_i$, $f(C_j \to t) = c_j$. Meze platí triviálně ($\lfloor a \rfloor \le a \le \lceil a \rceil$) a Kirchhoff je definice řádkových a sloupcových součtů: $r_i = \sum_j x_{ij}$, $c_j = \sum_i x_{ij}$. Přípustný frakční tok tedy existuje pro každý přípustný vstup — a Integral Flow Theorem z něj vyrobí existenci celočíselného: konzistentní zaokrouhlení existuje vždy. To je celá odpověď na otázku c) zkouškové úlohy.

Běh: od počátečního toku k maximálnímu součtu

Síť má nenulové dolní meze, takže $f \equiv 0$ není přípustný start — Ford-Fulkerson potřebuje počáteční přípustný celočíselný tok. Ten dodá transformace z [L4.7] (cirkulační hrana $t \to s$, substituce $f = f' + l$, bilance, max flow na redukci); její provedení tu přeskočíme a rovnou použijeme výsledek (konkrétní počáteční tok je vlastní dopočet — přiznáno). Pak už běží klasická smyčka augmentací [L4.3]:

Z posledního framu čteš zaokrouhlenou matici přímo z toků na vnitřních hranách:

$$\begin{array}{ccc|c} \hat{x}_{ij} & & & \hat{r}_i \\ \hline 4 & 6 & 8 & 18 \\ 10 & 3 & 0 & 13 \\ 3 & 2 & 7 & 12 \\ \hline \hat{c}_j:\ 17 & 11 & 15 & \end{array}$$

Každá hodnota je $\lfloor a \rfloor$ nebo $\lceil a \rceil$ svého originálu, řádky i sloupce sedí a celkový součet $43 = |f|$ je maximální možný — certifikátem je řez $A = \{s\}$ s kapacitou $18 + 13 + 12 = 43$ [L4.4].

Nebezpečné polopravdy

1) „Tok vyjde celočíselný vždycky.“ Ne — celočíselnost máš zaručenou jen pro celočíselné meze (Dantzig-Fulkerson; pro neceločíselné kapacity nemusí F-F ani skončit, slide 18). Tady meze celé jsou, protože jsme je tak postavili — to je potřeba u zkoušky říct, ne mlčky předpokládat. 2) Feasibilita má dva kroky. „Je to vždy řešitelné“ zdůvodníš (i) frakčním certifikátem = matice sama a (ii) Integral Flow Theorem, který z frakčního udělá celočíselný. Bez kroku (ii) jsi dokázal jen existenci neceločíselného toku — a ten zaokrouhlením není. 3) Dolní meze nejsou nula. $l(e) = \lfloor a \rfloor > 0$ skoro všude → start F-F není zadarmo, potřebuješ konstrukci z [L4.7]. Věta „begin with zero flow“ je tu chyba. 4) Celočíselný prvek = fixovaná hrana. Pro celé $a$ je $\lfloor a \rfloor = \lceil a \rceil = a$, tedy $l = u = a$ — žádné $[a, a+1]$. Zaokrouhlení nesmí celé číslo změnit.

Key takeaways — L4.8
T01 Matrix Rounding Problem zdroj: teoretický test (final), str. 1 — zadání EN 1:1; řešení ve zdroji není, sepsáno vlastní dle slidů 17 a 20 — přiznáno
Assignment (original, EN 1:1)

This application is concerned with consistent rounding of the elements, row sums, and column sums of a matrix. We are given a $3 \times 3$ matrix of real numbers $x_{ij}$ with row sums vector $r$ and column sums vector $c$. We can round any real number $a \in \{x_{11} \ldots x_{33}, r_1 \ldots r_3, c_1 \ldots c_3\}$ to the next smaller integer $\lfloor a \rfloor$ or to the next larger integer $\lceil a \rceil$, and the decision is completely up to us. The problem requires that we round all matrix elements and the following constraints hold:

  • the sum of the rounded elements in each row is equal to the rounded row sum $r_i$
  • the sum of the rounded elements in each column is equal to the rounded column sum $c_i$

The objective is to maximize the sum of rounded matrix entries.

a) Formulate as the maximum flow problem.
b) Are the resulting flows integers? Why yes/no?
c) Is the problem feasible for any admissible input?

a) Co je v zadání?

Teoretická formulační úloha — přesně obsah téhle lekce. Tři podotázky odpovídají třem sekcím: konstrukce sítě (formulace), celočíselnost (proč tok = zaokrouhlení) a feasibilita (proč existuje řešení pro každý vstup). Žádné konkrétní počítání; hodnotí se úplnost zdůvodnění.

b) Co k tomu budeme potřebovat?

  • Tato lekce — vzor sítě, meze $[\lfloor a \rfloor, \lceil a \rceil]$, oba argumenty (takeaways).
  • [L4.5] — Integral Flow Theorem (Dantzig-Fulkerson).
  • [L3.12] — totální unimodularita incidenční matice (alternativa pro b)).
  • [L4.1] — přípustnost $l \le f \le u$ a Kirchhoff.

c) Jak nad úlohou uvažovat?

U a) odevzdej čtyři věci jako vždy u tokových formulací: uzly, hrany, meze, čtení výsledku — a navíc větu „Kirchhoff v $R_i$/$C_j$ = podmínky konzistence, $|f|$ = celkový součet, tedy max flow“. U b) nestačí „ano“: musíš říct proč (celočíselné meze + věta / TUM / celočíselné $\gamma$ ve F-F). U c) hledej přípustný tok, který nemusíš počítat — a nezapomeň, že frakční certifikát sám o sobě nestačí (polopravda 2).

d) Úplné řešení (vlastní dle slidů 17 + 20 — přiznáno)

a) Formulace. Uzly: $s$, $R_1, R_2, R_3$ (řádky), $C_1, C_2, C_3$ (sloupce), $t$. Hrany a meze $[l, u]$:

  • $s \to R_i$: $[\lfloor r_i \rfloor, \lceil r_i \rceil]$ pro $i = 1, 2, 3$,
  • $R_i \to C_j$: $[\lfloor x_{ij} \rfloor, \lceil x_{ij} \rceil]$ pro všech 9 dvojic $(i, j)$,
  • $C_j \to t$: $[\lfloor c_j \rfloor, \lceil c_j \rceil]$ pro $j = 1, 2, 3$.

Celočíselný přípustný tok odpovídá konzistentnímu zaokrouhlení: hodnota na hraně je zaokrouhlení příslušného čísla (celé číslo v $[\lfloor a \rfloor, \lceil a \rceil]$) a Kirchhoffův zákon v $R_i$ resp. $C_j$ říká přesně „součet zaokrouhlených prvků řádku/sloupce = zaokrouhlený řádkový/sloupcový součet“. Hodnota toku $|f| = \sum_i f(s \to R_i)$ je celkový součet zaokrouhlené matice → maximalizace součtu = maximum flow problem. (Kvůli $l > 0$ se počáteční přípustný tok najde transformací z [L4.7].)

b) Ano, jsou celočíselné. Všechny meze jsou celá čísla. Podle Integral Flow Theorem (Dantzig and Fulkerson [1956], slide 17) existuje celočíselný maximální tok; důvodem je totální unimodularita incidenční matice digrafu ([L3.12]) — polyedr má celočíselné vrcholy. Algoritmicky: Ford-Fulkerson startuje z celočíselného toku a augmentuje vždy o celé $\gamma$, takže celočíselný max tok přímo vrátí. Celé číslo v $[\lfloor a \rfloor, \lceil a \rceil]$ je nutně $\lfloor a \rfloor$ nebo $\lceil a \rceil$ — tok je tedy přímo zaokrouhlení.

c) Ano, pro libovolný vstup. Původní (nezaokrouhlená) matice definuje přípustný frakční tok: $f(R_i \to C_j) = x_{ij}$, $f(s \to R_i) = r_i$, $f(C_j \to t) = c_j$. Meze platí triviálně ($\lfloor a \rfloor \le a \le \lceil a \rceil$) a Kirchhoffovy rovnice jsou přesně definice řádkových a sloupcových součtů. Existuje tedy přípustný tok — a protože meze jsou celočíselné, existuje dle věty z b) i celočíselný (maximální) tok, tj. konzistentní zaokrouhlení vždy existuje.

T02 Matrix rounding — celá konstrukce a běh na matici 2×2 zdroj: VLASTNÍ drill (instance, otázky i řešení vlastní — přiznáno)
Assignment (EN — vlastní drill, přiznáno)

Consider the $2 \times 2$ matrix with row sums $r$ and column sums $c$: $$\begin{array}{cc|c} 1.4 & 2.7 & 4.1 \\ 3.3 & 0.6 & 3.9 \\ \hline 4.7 & 3.3 & \end{array}$$ (i) Formulate the consistent rounding problem as a maximum flow problem: draw the network and label every edge with its bounds $[l, u]$. (ii) Starting from the initial feasible integer flow $f$ given by $\hat{x} = \begin{pmatrix}1 & 3\\ 3 & 1\end{pmatrix}$, $\hat{r} = (4, 4)$, $\hat{c} = (4, 4)$, verify its feasibility and run the Ford-Fulkerson algorithm to maximize the sum of the rounded entries. (iii) Give the resulting consistent rounding, its total sum, and a minimum cut certifying optimality.

a) Co je v zadání?

Stejná konstrukce jako v lekci, ale v nejmenším netriviálním formátu $2 \times 2$ — 4 prvky + 2 řádkové + 2 sloupcové součty = 8 hran. Počáteční přípustný tok je darovaný (v plné zkouškové verzi by ses k němu dostal přes [L4.7]), tvoje práce je formulace, kontrola přípustnosti, augmentace a certifikát řezem.

b) Co k tomu budeme potřebovat?

  • Tato lekce — vzor sítě a meze (takeaways).
  • [L4.3] — smyčka Ford-Fulkersona (každou iteraci vypsat).
  • [L4.4] — min řez z posledního značkování + kontrola $C(A) = |f|$.

c) Jak nad úlohou uvažovat?

① Meze: $\lfloor a \rfloor$ a $\lceil a \rceil$ všech osmi čísel. ② Přípustnost startu: meze na všech hranách + Kirchhoff v $A_1, A_2, B_1, B_2$. ③ Augmentuj, dokud v reziduálním grafu vede cesta $s \to t$ (pozor, zpětné hrany existují jen při $f > l$ — tady je $l$ vysoko!). ④ Když cesta není, vypiš označkované uzly = $A$ a spočti $C(A) = \sum u(\delta^+(A)) - \sum l(\delta^-(A))$.

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

(i) Síť. $s \to A_1\ [4, 5]$, $s \to A_2\ [3, 4]$ (řádkové součty $4.1, 3.9$); $A_1 \to B_1\ [1, 2]$, $A_1 \to B_2\ [2, 3]$, $A_2 \to B_1\ [3, 4]$, $A_2 \to B_2\ [0, 1]$ (prvky); $B_1 \to t\ [4, 5]$, $B_2 \to t\ [3, 4]$ (sloupcové součty $4.7, 3.3$) — viz obrázek u zadání.

(ii) Start a běh. Kontrola startu: meze $1 \in [1,2]$, $3 \in [2,3]$, $3 \in [3,4]$, $1 \in [0,1]$, $4 \in [4,5]$ (2×), $4 \in [4,5]$, $4 \in [3,4]$ ✓; Kirchhoff: $A_1$: $4 = 1 + 3$ ✓, $A_2$: $4 = 3 + 1$ ✓, $B_1$: $1 + 3 = 4$ ✓, $B_2$: $3 + 1 = 4$ ✓. $|f| = 8$. Běh:

(iii) Výsledek. Zaokrouhlení $\hat{x} = \begin{pmatrix}2 & 3\\ 3 & 1\end{pmatrix}$, $\hat{r} = (5, 4)$, $\hat{c} = (5, 4)$, celkový součet $|f| = 9$. Minimální řez z posledního značkování: obě hrany ze $s$ jsou nasycené, takže $A = \{s\}$ a $C(A) = u(s \to A_1) + u(s \to A_2) = 5 + 4 = 9 = |f|$ → tok je maximální [L4.4]. Kontrola konzistence: řádek 1: $2 + 3 = 5$ ✓, řádek 2: $3 + 1 = 4$ ✓, sloupec 1: $2 + 3 = 5$ ✓, sloupec 2: $3 + 1 = 4$ ✓ — a každá hodnota je $\lfloor a \rfloor$ nebo $\lceil a \rceil$ svého originálu ✓.

← Předchozí L4.7 · Počáteční přípustný tok při nenulových dolních mezích