L3.12 Kapitola K3 — Důkaz / teorie (Slot 3) · [MUST]

Teorie ILP/TUM (ústní opora)

Jedna nová věc Totálně unimodulární matice (každá čtvercová podmatice má determinant $0$, $+1$ nebo $-1$) + celočíselná pravá strana $b$ ⟹ všechny vrcholy LP polyedru jsou celočíselné — a proto ILP se stejnou maticí vyřeší obyčejné LP.

Tahle lekce je ústní opora: u písemky se TUM objevuje jako zdůvodňovací krok („proč LP stačí?“), u ústní jako samostatná otázka k teorii ILP. Z [L0.7] Co je ILP a LP relaxace víš, že LP relaxace obecně vrací zlomky a zaokrouhlení může skončit nepřípustně i daleko od optima (slide 18). Dnes poznáš výjimku ze třídy: rodinu matic, u kterých LP relaxace nemůže vrátit zlomek — a uvidíš, že nejkratší cesty z celé kapitoly K2 do té rodiny patří.

Záhada ze slidu 20: LP, které vrací jen nuly a jedničky

Slide 20 přepisuje nejkratší cestu (celou K2 jsi ji počítal algoritmy — [L2.4] Dijkstra, [L2.12] Bellman-Ford) jako lineární program. Klíčový nový objekt je incidence matrix (incidenční matice) — řádek pro každý vrchol, sloupec pro každou hranu. Slide 20 (EN 1:1):

Slide 20 — Example ILP2b: Shortest Paths (1:1)

Instance: digraph $G$ without a negative cycle given by incidence matrix $W : V \times E \to \{-1, 0, +1\}$ (such that $w_{ij} = +1$ when edge $e_j$ leaves vertex $i$ and $w_{kj} = -1$ when edge $e_j$ enters vertex $k$), distance vector $c \in \mathbb{R}^+$ and two nodes $s, t \in V$.

Goal: find the shortest path from $s$ to $t$ or decide that $t$ is unreachable from $s$.

LP formulation:

$$ \begin{aligned} \min \quad & \sum_{j \in 1..m} c_j \ast x_j \\ \text{subject to:} \quad & \sum_{j \in 1..m} w_{s,j} \ast x_j = 1 \quad \text{source } s \\ & \sum_{j \in 1..m} w_{i,j} \ast x_j = 0 \quad i \in V \setminus \{s, t\} \\ & \sum_{j \in 1..m} w_{t,j} \ast x_j = -1 \quad \text{sink } t \\ \text{pars:} \quad & w_{i \in 1..n, j \in 1..m} \in \{-1, 0, 1\},\ c_{j \in 1..m} \in \mathbb{R}^+ \\ \text{vars:} \quad & x_{j \in 1..m} \in \mathbb{R}^+_0 \end{aligned} $$

The returned values of $x_j$ are integers (binary) even though it is LP. Why?

Poslední věta je otázka celé lekce. Než ji vyřešíme, ujisti se, že modelu rozumíš:

Zkus sám: přečti tři skupiny podmínek „lidsky“. Co říká řádek pro $s$, pro $t$ a pro vnitřní vrchol $i$?

Řádek $i$ incidenční matice sečte $+1$ za každou vybranou hranu, která z $i$ vychází, a $-1$ za každou, která do $i$ vchází. Podmínky tedy říkají: z $s$ vyjde o jednu hranu víc, než kolik vejde ($=1$); do $t$ vejde o jednu víc, než vyjde ($=-1$); v každém jiném vrcholu se vstupy a výstupy vyrovnají ($=0$ — přesně věta ze slidu „we enter the node as many times as we leave it“). Vybrané hrany tak tvoří „jednotkový proud“ z $s$ do $t$ — cesta z $s$ do $t$ (případně plus cykly) všechny tři podmínky splňuje.

Zkus sám: proč smíme vynechat $x_j \le 1$ (slide: „due to the minimization“)?

Ceny $c_j$ jsou nezáporné a minimalizujeme. Kdyby řešení posílalo po nějaké hraně víc než jednotku (nebo přidávalo cyklus navíc), dá se přebytek odebrat, podmínky zůstanou splněné a cena neklesne pod cenu cesty — optimum tedy nepotřebuje $x_j > 1$. (Stejný duch jako „cyklus s nezápornou cenou si do cesty nepřibalíš“ z [L2.1].)

Konkrétní instance ze slidu 23 — digraf se 4 vrcholy a 5 hranami:

Jeho incidenční matice, vektor proměnných a pravá strana pro $s = v_1$, $t = v_4$ (slide 23, 1:1):

$$ W = \begin{array}{c|ccccc} & e_1 & e_2 & e_3 & e_4 & e_5 \\ \hline v_1 & 1 & 0 & 1 & 0 & 1 \\ v_2 & -1 & 1 & 0 & 0 & 0 \\ v_3 & 0 & 0 & -1 & 1 & 0 \\ v_4 & 0 & -1 & 0 & -1 & -1 \end{array} \qquad x = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{pmatrix} \qquad b = \begin{pmatrix} 1 \\ 0 \\ 0 \\ -1 \end{pmatrix} $$

Proměnné jsou spojité ($x_j \in \mathbb{R}^+_0$), žádná celočíselnost se nevynucuje — a přesto solver vrátí samé nuly a jedničky. Není to náhoda té instance; je to vlastnost matice $W$.

Totálně unimodulární matice

Slide 21 nejdřív připomene, proč nás speciální případy zajímají: „Polynomial time algorithm for general ILP is not known, however there are special cases which can be solved in polynomial time.“ A pak definice (EN 1:1):

Slide 21 — Definition: Totally unimodular matrix (1:1)

Matrix $\mathbf{A} = [a_{ij}]$ of size $m/n$ is totally unimodular if the determinant of every square submatrix of matrix $\mathbf{A}$ is equal to $0$, $+1$ or $-1$.

Necessary condition: if $\mathbf{A}$ is totally unimodular then $a_{ij} \in \{0, 1, -1\}\ \forall i, j$.

Čtvercová podmatice = vyber libovolnou množinu řádků a stejně velkou množinu sloupců (nemusí sousedit!) a vezmi průnik. Podmatic je exponenciálně mnoho — definice je proto silná, ale špatně se ověřuje hrubou silou. Na to budou za chvíli postačující podmínky.

Zkus sám: odkud se bere nutná podmínka $a_{ij} \in \{0, \pm 1\}$? (Jednořádková úvaha.)

Podmatice $1 \times 1$ jsou taky čtvercové podmatice — a determinant matice $[a_{ij}]$ je prostě $a_{ij}$. Definice tedy přímo vynucuje $a_{ij} \in \{0, +1, -1\}$ pro každý prvek.

Zkus sám: je matice $\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ totálně unimodulární? (Všechny prvky jsou $\pm 1$…)

Není: $\det \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} = 1 \cdot (-1) - 1 \cdot 1 = -2$. Nutná podmínka (prvky $0/\pm 1$) tedy není postačující — o TUM rozhodují determinanty všech podmatic, ne jen prvky. Tuhle dvojřádkovou matici si zapamatuj, vrátí se jako protipříklad se zlomkovým vrcholem.

Proč TUM ⟹ celočíselné vrcholy

Hlavní věta lekce (slide 21, EN 1:1) a její důsledek pro simplex (slide 22, EN 1:1):

Slide 21 — Lemma: Integral Polyhedron (1:1)  ·  Slide 22 — Lemma: Integer solution by simplex algorithm (1:1)

Let $A$ be a totally unimodular $m/n$ matrix and let $b \in \mathbb{Z}^m$. Then each vertex of the polyhedron $P := \{x ;\ \mathbf{A}x \le b\}$ is an integer vector. (Proof: [Schrijver] Theorem 8.1.)

If the ILP problem is given by a totally unimodular matrix $\mathbf{A}$ and integer vector $b$ then every feasible solution by a simplex algorithm is an integer vector. — From the Lemma on previous slide - the simplex algorithm inspects vertices that are integer vectors.

Unfortunately, the simplex algorithm does not have polynomial complexity. Fortunately, there are polynomial algorithms able to solve the LP problems and to find the vertex in the facet with optimal solutions.

Logika důsledku: LP optimum (s lineárním cílem) se vždy nabývá v některém vrcholu polyedru. Když jsou všechny vrcholy celočíselné, pak LP relaxace [L0.7] vydá celočíselné optimum — a to je zároveň optimum ILP (relaxace dává mez a tady je její řešení přípustné i celočíselně). ILP = LP, celočíselnost zadarmo.

Zkus sám: kde se v „řešení soustavy rovnic“ schovává determinant? (Nápověda: jak se počítá vrchol polyedru a co říká Cramerovo pravidlo?)

Vrchol polyedru $\{x : \mathbf{A}x \le b\}$ v $\mathbb{R}^n$ je bod, kde je $n$ lineárně nezávislých podmínek těsných (platí s rovností). Vrchol je tedy řešením čtvercové soustavy $\mathbf{A}_B\, x = b_B$, kde $\mathbf{A}_B$ je čtvercová podmatice $\mathbf{A}$ a $b_B$ příslušný kus pravé strany. Cramerovo pravidlo:

$$x_i = \frac{\det \mathbf{A}_B^{(i)}}{\det \mathbf{A}_B},$$

kde $\mathbf{A}_B^{(i)}$ vznikne nahrazením $i$-tého sloupce vektorem $b_B$. Čitatel je determinant celočíselné matice (prvky $0/\pm1$ a celé $b$) — celé číslo. A jmenovatel? $\mathbf{A}_B$ je čtvercová podmatice TUM matice, takže $\det \mathbf{A}_B \in \{0, \pm 1\}$; u vrcholu je soustava regulární, tedy $\det \mathbf{A}_B = \pm 1$. Celé číslo děleno $\pm 1$ = celé číslo — každá souřadnice vrcholu je celá. (Vlastní náčrt důkazu — slidy citují [Schrijver] Theorem 8.1; pro ústní bohatě stačí.) Teď je vidět, proč definice chce $0/\pm1$ pro všechny podmatice: nevíš dopředu, která podmnožina podmínek bude ve vrcholu těsná.

Obrázkem (vlastní mini-instance, přiznáno). Vlevo matice z try výše — řádky $x_1 + x_2 \le 3$ a $x_1 - x_2 \le 0$ obsahují podmatici $\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ s determinantem $-2$, a přesně ta vyrábí zlomkový vrchol (Cramer: jmenovatel $-2$). Vpravo TUM matice — vrcholy jen celé:

Levý polyedr má vrchol $(1{,}5;\ 1{,}5)$: LP optimum $\max x_1$ tam skončí, zaokrouhlení dá nepřípustný bod $(2,2)$ resp. $(1,1)$ mimo optimum — přesně patologie ze slidu 18 [L0.7]. Pravý polyedr (matice řádků $(1,1)$, $(-1,0)$, $(0,-1)$ — ověř: všechny $2\times 2$ podmatice mají det $0/\pm1$) má všechny vrcholy celé, LP rovnou vrací řešení ILP.

Jak TUM poznat: tři postačující podmínky

Determinanty všech podmatic nikdo nepočítá. Slidy 23–25 dávají tři postačující podmínky, které se ověřují pohledem. První je pro nás zlatá (slide 23, EN 1:1):

Slide 23 — 1st Sufficient Condition: No more than one $+1$ and no more than one $-1$ in each column (1:1)

Let $\mathbf{A}$ be matrix of size $m/n$ such that

  1. $a_{ij} \in \{0, 1, -1\}$, $i = 1, \dots, m$, $j = 1, \dots, n$
  2. each column in $\mathbf{A}$ contains one non-zero element or exactly two non-zero elements $+1$ and $-1$

Then the matrix $\mathbf{A}$ is totally unimodular. (Proof: [Ahuja] Theorem 11.12. [KorteVygen] Theorem 5.26.)

Example: ILP constraints of the Shortest Paths problem are: $W \ast x = b$.

Zkus sám: proč incidenční matice každého digrafu splňuje podmínku 2? (Co je sloupec incidenční matice?)

Sloupec = jedna hrana. Hrana $e_j$ má právě jeden počáteční vrchol (tam je $+1$) a právě jeden koncový vrchol (tam je $-1$); ve všech ostatních řádcích je $0$. Každý sloupec tedy obsahuje přesně jeden $+1$ a přesně jeden $-1$ — silnější, než podmínka žádá. Incidenční matice libovolného digrafu je TUM, žádný determinant netřeba.

Projdi si to sloupec po sloupci na instanci ze slidu 23:

Rozuzlení záhady ze slidu 20. Matice podmínek nejkratší cesty je incidenční matice $W$ → splňuje 1. postačující podmínku → je TUM. Pravá strana $b = (1, 0, \dots, 0, -1)^T$ je celočíselná. Podle lemmatu jsou všechny vrcholy polyedru celočíselné, LP optimum leží ve vrcholu — proto solver vrací $x_j \in \{0, 1\}$, i když o celočíselnost nikdo nežádal. (Drobnost k poctivosti: lemma je vysloveno pro $\mathbf{A}x \le b$; rovnosti $Wx = b$ a $x \ge 0$ na ten tvar převedeš jako $Wx \le b$, $-Wx \le -b$, $-x \le 0$ — a TUM se při násobení řádků $-1$ a přidání jednotkové matice zachová, viz operace níže.)

Zbylé dvě podmínky stačí znát na úrovni „poznám, kdy se hodí“ (obě EN 1:1 zkráceně):

Slide 24 — 2nd Sufficient Condition: Partitioned Rows (1:1)

Let $\mathbf{A}$ be matrix of size $m/n$ such that: 1. $a_{ij} \in \{0, 1\}$; 2. each column in $\mathbf{A}$ contains at most two entries of value $1$; 3. the rows of $\mathbf{A}$ can be partitioned into two sets $\mathcal{V}_1$ and $\mathcal{V}_2$ such that every column of $\mathbf{A}$ has at most one entry of value $1$ in the rows of $\mathcal{V}_1$ and at most one entry of value $1$ in the rows of $\mathcal{V}_2$. Then the matrix $\mathbf{A}$ is totally unimodular.

Example: bipartite graph related to assignment problem (lecture on Flows). — řádky = vrcholy, rozdělené přesně na dvě partity bipartitního grafu [L0.6]; každá hrana (sloupec) má jeden konec v každé partitě. Proto assignment/bipartitní matching řeší LP celočíselně — detaily v kapitole K4 ([L4.9] Bipartitní matching přes max flow, [L4.12]).

Slide 25 — 3rd Sufficient Condition: Consecutive-Ones (1:1)

Definition (Consecutive-Ones, a.k.a. Interval Matrix): Matrix $\mathbf{A}$ of size $m/n$ has the consecutive-ones property if: 1. $a_{ij} \in \{0, 1\}$; 2. there exists a permutation of its rows such that for any column $j$, $a_{ij} = a_{kj} = 1$ with $i < k$ implies $a_{lj} = 1$ for $i < l < k$.

Lemma: The matrix $\mathbf{A}$ with the consecutive-ones property is totally unimodular.

Lidsky: jedničky v každém sloupci tvoří (po vhodné permutaci řádků) souvislý interval. Typický zdroj: směny pokrývající po sobě jdoucí bloky — workforce scheduling ze slidu 26 (řádky = bloky dne, sloupce = směny; směna „Morning+Afternoon“ má jedničky v sousedních řádcích).

Zkus sám (otázka ze slidu 26): „What happens when we introduce »split shifts« (breaking the consecutive ones property)?“

Dělená směna (např. „Morning+Night“ s dírou uprostřed) udělá ve svém sloupci jedničky, mezi kterými je nula — a žádná permutace řádků nemusí umět spravit všechny sloupce najednou. Matice pak může ztratit totální unimodularitu: LP relaxace smí vrátit zlomkové počty zaměstnanců (např. „2,5 člověka na směně“) a na celočíselné řešení už potřebuješ skutečné ILP (B&B). Záruka „LP stačí“ padá s podmínkou, která ji nesla. (Odpověď vlastní — slide ji nechává jako otázku k zamyšlení.)

A nakonec praktický nástroj, který jsme už potřebovali u rozuzlení záhady — operace zachovávající TUM (slide 27, EN 1:1): když je $\mathbf{A}$ totálně unimodulární, pak i

  1. every matrix obtained from $\mathbf{A}$ by permuting some rows and/or columns,
  2. every matrix obtained from $\mathbf{A}$ by multiplying some rows and/or columns by $-1$,
  3. $\mathbf{A}^T$,
  4. the matrix $(\mathbf{A}, \mathbf{I})$,
  5. the matrix $\begin{pmatrix} \mathbf{A} \\ \mathbf{I} \end{pmatrix}$.

Ústní opora: kam TUM patří v mapě ILP teorie

U ústní se otázky na teorii ILP točí kolem čtyř témat. Tři z nich už máš vyložená jinde — tady jen mapa, nic se nevykládá znovu:

Pozor: nebezpečné polopravdy
Key takeaways — L3.12
T01 Example ILP2a: Shortest Paths — LP s délkovými proměnnými zdroj: banka #4 EN 1:1 (study task ze slidu 8, 02_ILP); řešení dle slidu 8, výklad „proč to kóduje vzdálenosti“ vlastní rozepsání přes [L2.2] (přiznáno)
Assignment (EN 1:1, banka #4)

The source slide states the shortest-path instance as a directed graph with $n$ nodes, a distance matrix $c : V \times V \to \mathbb{R}_+$, and two nodes $v_1, v_n \in V$. The goal is to find the shortest path from $v_1$ to $v_n$ or decide that $v_n$ is unreachable from $v_1$.

Study task: formulate the LP from the slide using distance labels $l_i$, with $l_1 = 0$ and constraints of the form $l_j \le l_i + c_{ij}$. State the objective and explain how the formulation encodes shortest-path distances.

a) Co je v zadání?

Druhá (úplně jiná!) LP formulace nejkratší cesty: proměnné nejsou indikátory hran jako ve slidu 20, ale přímo vzdálenostní hodnoty $l_i$ na vrcholech. Tři podúkoly: napsat model, určit cílovou funkci (pozor — je to maximalizace) a vysvětlit, proč optimum dává vzdálenosti.

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Slide nabízí fyzikální analogii: vrchol = kulička, hrana = provázek délky $c_{ij}$ (symetrická matice $c$), kuličku $v_1$ přidržíš a zbytek necháš viset — napnuté provázky jsou nejkratší cesty. „Viset“ = každý $l_j$ se chce co největší, ale provázek nedovolí víc než $l_i + c_{ij}$. Odtud cíl i podmínky. U vysvětlení dokazuj dvě strany: (i) každé přípustné $l$ má $l_n \le$ délka nejkratší cesty, (ii) hodnoty „skutečné vzdálenosti“ jsou přípustné. Nakonec si rozmysli, proč tady žádné TUM nepotřebuješ.

d) Úplné řešení (model dle slidu 8; zdůvodnění rozepsáno)

Model (slide 8, 1:1):

$$ \begin{aligned} \max \quad & l_n \\ \text{subject to:} \quad & l_1 = 0 \\ & l_j \le l_i + c_{i,j} \quad i \in 1..n,\ j \in 1..n \\ \text{parameters:} \quad & n \in \mathbb{Z}^+,\ c_{i \in 1..n, j \in 1..n} \in \mathbb{R}^+ \\ \text{variables:} \quad & l_{i \in 1..n} \in \mathbb{R}^+ \end{aligned} $$

Proč to kóduje vzdálenosti (vlastní rozepsání). (i) Horní odhad: vezmi libovolnou cestu $v_1 = u_0, u_1, \dots, u_k = v_n$ a sečti podmínky podél jejích hran: $l_{u_1} \le l_{u_0} + c_{u_0 u_1}$, …, $l_{u_k} \le l_{u_{k-1}} + c_{u_{k-1} u_k}$. Teleskopicky $l_n \le l_1 + \sum c = 0 + $ délka cesty. Platí to pro každou cestu, tedy $l_n \le \operatorname{dist}(v_1, v_n)$ pro každé přípustné $l$. (ii) Dosažitelnost: volba $l_i := \operatorname{dist}(v_1, v_i)$ je přípustná — $l_1 = 0$ a $\operatorname{dist}(v_1, v_j) \le \operatorname{dist}(v_1, v_i) + c_{ij}$ je přesně trojúhelníková nerovnost / Bellmanova rovnice [L2.2] (nezáporné $c$, žádné záporné cykly). Maximalizace $l_n$ tedy „napne provázky“ a optimum je rovno $\operatorname{dist}(v_1, v_n)$. Proto max, ne min: s minimalizací by se model zhroutil do $l \equiv 0$.

Nedosažitelnost: pokud do $v_n$ žádná cesta nevede (v matici $c$ reprezentováno zakázanými/„nekonečnými“ položkami), není $l_n$ shora omezeno řetězem podmínek z $l_1$ a LP je neomezené — neomezenost signalizuje „unreachable“. (Vlastní poznámka.)

Vazba na lekci: tady se celočíselnost vůbec neřeší — proměnné jsou vzdálenosti, žádné 0/1 rozhodování. TUM je potřeba až u hranové formulace ze slidu 20 (T02), kde spojitá $x_j$ mají vyjít binárně. Dvě LP na tutéž úlohu, dva úplně jiné důvody, proč fungují.

T02 Shortest Paths jako LP — proč vrací celočíselné řešení (TUM) zdroj: model + otázka „Why?“ = slide 20 EN 1:1 (02_ILP); znění study tasku vlastní (přiznáno); řešení dle slidů 21–23 + 27, Cramerův náčrt vlastní (slidy citují [Schrijver])
Assignment (model + otázka EN 1:1, slide 20; study task vlastní)

Shortest path in a graph. Instance: digraph $G$ without a negative cycle given by incidence matrix $W : V \times E \to \{-1, 0, +1\}$, distance vector $c \in \mathbb{R}^+$ and two nodes $s, t \in V$. Consider the LP formulation

$$\min \sum_{j} c_j x_j \quad \text{s.t.} \quad \sum_j w_{s,j} x_j = 1,\quad \sum_j w_{i,j} x_j = 0 \ (i \ne s,t),\quad \sum_j w_{t,j} x_j = -1,\quad x_j \in \mathbb{R}^+_0.$$

„The returned values of $x_j$ are integers (binary) even though it is LP. Why?“

Study task (vlastní): Define a totally unimodular matrix, state the integral-polyhedron lemma, prove that the incidence matrix $W$ is totally unimodular using the 1st sufficient condition, and conclude why the LP returns integer values.

a) Co je v zadání?

Hlavní teoretická otázka lekce v ústním formátu: čtyřkrokový řetěz definice → lemma → ověření podmínky pro $W$ → závěr. Body se ztrácejí typicky na dvou místech: zapomenutá celočíselnost $b$ a tvrzení „prvky $\pm1$ ⟹ TUM“ (to je jen nutná podmínka!).

b) Co k tomu budeme potřebovat?

  • Tato lekce — definice TUM, lemma, 1. postačující podmínka, operace zachovávající TUM.
  • [L0.7] Co je ILP a LP relaxace — proč je celočíselný vrchol LP zároveň optimem ILP.

c) Jak nad úlohou uvažovat?

Vyprávěj řetěz od konce: chci, aby LP optimum bylo celé → optimum sedí ve vrcholu → stačí, aby všechny vrcholy byly celé → to dává lemma (TUM + celé $b$) → takže potřebuju TUM pro $W$ → a tu dává 1. postačující podmínka, protože sloupec incidenční matice = hrana = jeden $+1$ (odkud) a jeden $-1$ (kam). Na ústní přidej Cramerovu intuici, proč determinant $\pm1$ znamená celé souřadnice.

d) Úplné řešení

1) Definice (slide 21). Matice $\mathbf{A}$ je totálně unimodulární, pokud determinant každé její čtvercové podmatice je $0$, $+1$ nebo $-1$. (Nutně pak $a_{ij} \in \{0, \pm 1\}$ — podmatice $1\times1$; obráceně to neplatí, $\det\begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix} = -2$.)

2) Lemma (slide 21). Je-li $\mathbf{A}$ TUM a $b \in \mathbb{Z}^m$, pak každý vrchol polyedru $\{x : \mathbf{A}x \le b\}$ je celočíselný vektor. Náčrt proč (vlastní; slidy citují [Schrijver] Thm 8.1): vrchol je řešením čtvercové regulární soustavy z těsných podmínek, Cramerovo pravidlo dělí celočíselný determinant determinantem $\pm 1$.

3) $W$ je TUM (slide 23). 1. postačující podmínka: prvky v $\{0, \pm1\}$ a každý sloupec má nejvýše jeden $+1$ a nejvýše jeden $-1$. Sloupec incidenční matice odpovídá hraně $e_j$: obsahuje $+1$ v řádku vrcholu, který hrana opouští, $-1$ v řádku vrcholu, do něhož vstupuje, jinde nuly — tedy přesně jeden $+1$ a jeden $-1$. Podmínka platí ⟹ $W$ je TUM.

4) Závěr. Soustavu $Wx = b$, $x \ge 0$ převedeme na tvar lemmatu: matice $\begin{pmatrix} W \\ -W \\ -\mathbf{I} \end{pmatrix}$ s pravou stranou $(b; -b; 0)$ — vznikla z $W$ násobením řádků $-1$ a přidáním jednotkové matice, což TUM zachovává (slide 27, operace 2 a 5). Pravá strana $b = (1, 0, \dots, 0, -1)^T$ je celočíselná. Podle lemmatu jsou všechny vrcholy přípustného polyedru celočíselné; LP s lineárním cílem nabývá optima ve vrcholu, takže vrácené $x_j$ jsou celá čísla — a díky minimalizaci s $c \ge 0$ konkrétně $0/1$ indikátory hran nejkratší cesty (jednotky navíc by jen zdražovaly). Proto smíme nejkratší cestu řešit jako LP a celočíselnost dostáváme zadarmo. $\blacksquare$

Kontrolní otázka navíc (ústní klasika): proč stejný trik nefunguje pro TSP model [L3.4]? Jeho matice (big-M podmínky se $s_i$, koeficienty $M \notin \{0,\pm1\}$) nesplňuje už nutnou podmínku TUM — a fundamentálněji: kdyby LP relaxace řešila TSP přesně, řešili bychom silně NP-těžký problém [L3.5] polynomiálně.

← Předchozí L3.11 · Knapsack: fractional greedy + 2-aproximace