TSP jako ILP s eliminací podtras (MTZ)
V [L3.3] Hamiltonovská kružnice a NP-úplnost jsme viděli, že okruh přes všechna města je těžký problém — ale taky že NP-úplnost neznamená „prakticky neřešitelné“: konkrétní instance TSP se optimálně řeší přes ILP. Dnes ten ILP model postavíme. Uvidíš, že „snadná“ část modelu (každé město právě jednou) nestačí a nejzajímavější je právě boj s podtrasami — řešeními rozpadlými na několik menších okruhů. To je přesně modelovací dovednost, kterou zkouší úloha banky T11 i zkouškové téma „TSP s time windows“.
TSP formálně
V [L3.3] byl TSP jen slovně („najdi nejlevnější Hamiltonovskou kružnici“). Teď přesně, ve dvou variantách, jak je uvádějí slidy:
Traveling Salesman Problem — TSP
- Instance: A complete undirected graph $K_n$ ($n \ge 3$) and weights $c : E(K_n) \to \mathbb{R}^+$.
- Goal: Find a Hamiltonian circuit $T$ whose weight $\sum_{e \in E(T)} c(e)$ is minimum.
Slide dodává: tohle je symmetric TSP (úplný neorientovaný graf). Pokud se cena z A do B liší od ceny z B do A, použijeme úplný digraf a mluvíme o asymmetric TSP.
Zkus sám: proč definice chce úplný graf $K_n$? V [L3.3] jsme přece pracovali s obecným grafem $G$.
Protože TSP je optimalizační problém — aby „najdi nejlevnější okruh“ vždy mělo řešení, musí aspoň jeden okruh existovat, a v úplném grafu existuje vždy (libovolné pořadí měst je okruh). Existenční otázku „je v obecném grafu $G$ vůbec nějaká Hamiltonovská kružnice?“ jsme oddělili jako rozhodovací problém HC [L3.3]. Obecný graf do TSP „zúplníš“ tak, že chybějícím hranám dáš prohibitivně velkou cenu — přesně tenhle trik budou dělat redukce v [L3.5] a [L3.6].
ILP model stavějí slidy (02_ILP, slide 9) pro asymetrickou verzi — úplný digraf $K_n$ s maticí vzdáleností $c : V \times V \to \mathbb{Q}^+$. Symetrický TSP je speciální případ ($c_{i,j} = c_{j,i}$), takže model pokrývá obojí.
První pokus: každé město právě jednou
Zkus sám: navrhni binární proměnné pro „okruh v digrafu“ a zapiš účelovou funkci. (Vzpomeň na [L0.8] Binární proměnná a indexované rodiny proměnných [L1.15].)
Pro každou uspořádanou dvojici měst zaveď $x_{i,j} \in \{0,1\}$ s významem ze slidu 9 (EN 1:1): „$x_{i,j} = 1$ iff node $i$ is in the cycle just before node $j$“ — tedy „okruh jede z $i$ přímo do $j$“. Účelová funkce: minimalizuj cenu vybraných hran, $$\min \sum_{i \in 1..n} \sum_{j \in 1..n} c_{i,j} \cdot x_{i,j}.$$
Zkus sám: jaká omezení zaručí, že vybrané hrany „projdou každým městem právě jednou“?
Na okruhu má každé město právě jednoho následníka a právě jednoho předchůdce:
$$\sum_{i \in 1..n} x_{i,j} = 1 \quad j \in 1..n \quad \text{(enter once — do každého města právě jednou vstoupíš)},$$ $$\sum_{j \in 1..n} x_{i,j} = 1 \quad i \in 1..n \quad \text{(leave once — každé město právě jednou opustíš)}.$$
A drobnost, na kterou se zapomíná: zakázat smyčky $x_{i,i} = 0$ pro všechna $i$ (jinak by „$i$ před $i$“ triviálně splnilo oba součty).
Vypadá hotově, že? Minimalizujeme cenu, každé město má vstup i výstup. Jenže…
Zkus sám (klíčový moment lekce): najdi pro $n = 6$ množinu hran, která splňuje všechna omezení výše (enter once, leave once, žádné smyčky), a přitom to není okruh přes všechna města.
Stačí vybrat dva oddělené menší okruhy: třeba $1 \to 2 \to 3 \to 1$ a $4 \to 5 \to 6 \to 4$ (viz obrázek pod boxem). Každé město má právě jeden vstup a právě jeden výstup — oba součty sedí, smyčka žádná. Ale obchodní cestující by se musel rozdvojit. Takovým kusům se říká sub-tours (podtrasy). Slide 9 (EN 1:1): „The enter and leave constraints do not capture the TSP completely, since any disjoint cycle (i.e. consisting of several sub-tours) will satisfy them.“
A pozor — nejde o kosmetickou vadu. Dva malé okruhy bývají levnější než jeden velký (ušetříš drahé „přejezdy“ mezi skupinami měst), takže optimum děravého modelu bude typicky právě podtrasové. Model musíme doplnit o subtour elimination — eliminaci podtras.
Eliminace podtras: čas vstupu $s_i$ (MTZ)
Zkus sám: vymysli, jak podtrasy zakázat polynomiálně mnoha omezeními. Nápověda: představ si, že cestující nosí hodinky — co platí o časech, ve kterých vstupuje do měst podél okruhu?
Podél okruhu čas jen roste: když jedu z $i$ rovnou do $j$ a cesta trvá $c_{i,j}$, vstoupím do $j$ nejdřív v čase (vstup do $i$) $+\, c_{i,j}$. Zavedeme tedy pro každé město spojitou proměnnou $s_i \ge 0$ — slide 9 (EN 1:1): „We use $s_i$, the 'time' of entering node $i$, to eliminate the sub-tours.“ Jenže každý okruh se nakonec musí uzavřít — někde se čas vrátit musí. Trik: rostoucí čas vyžadujeme všude kromě návratu do města 1. Hlavní okruh se smí uzavřít jen přes město 1; podtrasa, která město 1 neobsahuje, by potřebovala čas rostoucí pořád dokola — a to nejde. Přesné znění hned pod boxem.
$$s_i + c_{i,j} - (1 - x_{i,j}) \cdot M \le s_j \qquad i \in 1..n,\ j \in 2..n \qquad \text{cycle indivisibility}$$
kde $M \in \mathbb{Z}^+$ je dostatečně velká konstanta a $s_{i \in 1..n} \in \mathbb{R}^+_0$ jsou nové spojité proměnné.
Čti ji jako přepínač [L1.4] big-M:
- $x_{i,j} = 1$ (hrana v okruhu): podmínka zní $s_i + c_{i,j} \le s_j$ — do $j$ vstoupíš aspoň o dobu jízdy později než do $i$.
- $x_{i,j} = 0$ (hrana mimo okruh): podmínka zní $s_i + c_{i,j} - M \le s_j$ — pro velké $M$ je splněna vždy, tedy vypnutá.
Zkus sám: proč podmínka běží jen přes $j \in 2..n$? Co by se stalo, kdybychom ji napsali i pro $j = 1$?
Model by se stal nesplnitelným i pro správné okruhy! Sečti podmínky podél celého okruhu $1 \to v_2 \to \cdots \to v_n \to 1$ (všechny hrany mají $x = 1$, takže $s_i + c_{i,j} \le s_j$): proměnné $s$ se po obvodu vykrátí a zbyde $\sum_{\text{okruh}} c_{i,j} \le 0$ — spor s kladnými cenami. Proto se hrana vstupující do města 1 z podmínky vynechává ($j \ge 2$): město 1 je „depo“, kde se hodinky smí přetočit. Každý jiný vrchol takové privilegium nemá.
Zkus sám: a teď hlavní otázka — proč tahle podmínka zabije každou podtrasu? Zkus to formálně na podtrase $4 \to 5 \to 6 \to 4$.
Podtrasové řešení se skládá z aspoň dvou okruhů — nanejvýš jeden z nich obsahuje město 1. Vezmi libovolný okruh bez města 1, třeba $4 \to 5 \to 6 \to 4$: všechny jeho hrany končí ve vrcholech $\ge 2$, takže všechny tři podmínky jsou „zapnuté“: $$s_4 + c_{4,5} \le s_5, \qquad s_5 + c_{5,6} \le s_6, \qquad s_6 + c_{6,4} \le s_4.$$ Sečtením se $s_4, s_5, s_6$ vykrátí a zbyde $c_{4,5} + c_{5,6} + c_{6,4} \le 0$ — spor, ceny jsou kladné. Žádné hodnoty $s$ takovou podtrasu nezachrání → řešení s podtrasou je nepřípustné. Naopak pro jediný okruh přes všechna města přípustné $s$ existuje (nasčítej časy podél okruhu od $s_1 = 0$; návrat do 1 podmínku nemá). Přesně to znamená „cycle indivisibility“ — okruh je nedělitelný.
Oba případy si přehraj na konkrétních číslech:
Dohromady dostáváme celý model ze slidu 9:
$x_{i,j} = 1$ iff node $i$ is in the cycle just before node $j$.
$$\begin{aligned} \min \quad & \sum_{i \in 1..n} \sum_{j \in 1..n} c_{i,j} \cdot x_{i,j} \\ \text{subject to:} \quad & x_{i,i} = 0 \quad && i \in 1..n && \text{avoid self-loop} \\ & \sum_{i \in 1..n} x_{i,j} = 1 \quad && j \in 1..n && \text{enter once} \\ & \sum_{j \in 1..n} x_{i,j} = 1 \quad && i \in 1..n && \text{leave once} \\ & s_i + c_{i,j} - (1 - x_{i,j}) \cdot M \le s_j \quad && i \in 1..n,\ j \in 2..n && \text{cycle indivisibility} \\ \text{parameters:} \quad & M \in \mathbb{Z}^+,\ n \in \mathbb{Z}^+,\ c \in \mathbb{Q}^+ \\ \text{variables:} \quad & x_{i,j} \in \{0,1\},\ s_i \in \mathbb{R}^+_0 \end{aligned}$$
Zkus sám: jak velké musí být $M$? (Vzpomeň na zásadu z [L1.4]: dost velké, aby nic neořízlo — ale ne zbytečně.)
Vypnutá podmínka ($x_{i,j}=0$) zní $s_i + c_{i,j} - M \le s_j$; nesmí nic zakazovat pro žádné rozumné hodnoty $s$. Časy podél okruhu nepřesáhnou součet všech ujetých cen, takže bezpečně stačí např. $M$ rovné součtu maxima ceny a horní meze na $s$, konkrétně třeba $M = n \cdot \max_{i,j} c_{i,j}$ nebo $M = \sum_{i,j} c_{i,j}$. Příliš malé $M$ by ořízlo přípustné okruhy (model by lhal), zbytečně velké $M$ zhoršuje LP relaxaci a numeriku — přesně dilema z [L1.4].
Podmínkám tohoto typu se v literatuře říká MTZ subtour elimination podle autorů (Miller, Tucker, Zemlin, 1960). Slidy kurzu jméno neuvádějí — používají variantu s „časem vstupu“ $s_i$ a big-M a říkají jí cycle indivisibility. Počítej s oběma názvy. (Dovysvětlení jména je vlastní doplněk nad rámec slidů.)
Spočítej si velikost modelu: $n^2$ binárek $x_{i,j}$, $n$ spojitých $s_i$, a omezení $O(n^2)$ — celý model je polynomiálně velký. To neodporuje NP-těžkosti TSP: ILP samo je NP-těžké [L0.7], jen jsme těžkost přestěhovali do řešení ILP (B&B [L5.5]).
Alternativa: množinové podmínky a lazy constraints
MTZ není jediná cesta. Cvičení 10 (Lab 10) používá podmínky, které podtrasy zakazují přímo — bez pomocných proměnných:
$$\sum_{i,j \in S\,:\, i \ne j} x_{i,j} \le |S| - 1, \qquad S \subset V,\ S \ne \emptyset \tag{4}$$
Cv10 (EN 1:1): „It requires that in each proper non-empty subset of vertices $S$ there are at most $|S|-1$ edges between them. Indeed, having a subset of vertices with $|S|$ edges if $S \ne V$ means that there are subtours in the solution, for instance if $S = \{1,2,3\}$ then $\sum_{i,j \in S : i \ne j} x_{i,j} = 3 > |S| - 1$.“
Zkus sám: kolik podmínek typu (4) model má? Spočítej pro $n = 10$.
Jedna podmínka pro každou neprázdnou vlastní podmnožinu $S \subset V$: celkem $2^n - 2$. Pro $n = 10$ to je $1022$ podmínek (cv10 uvádí pro $n=10$ hodnotu 1022, ve zdroji zapsanou s překlepem jako $2^{n-2}$; korektní počet neprázdných vlastních podmnožin je $2^n - 2 = 1022$) — a pro $n = 50$ už $\approx 10^{15}$. Exponenciálně mnoho — takhle naplno model nikdy nevypíšeš. MTZ vyhrává kompaktností ($O(n^2)$); množinová verze ale jde použít chytře…
…a to je nápad lazy constraints (líně generovaná omezení) z cv10 (EN 1:1): „The basic idea is to initially formulate the problem only with the most essential constraints, omitting those that are only rarely violated. These other constraints are checked and added one-by-one to the model only if the current solution violates any of them.“ Pro TSP: začni jen s „enter once / leave once“; kdykoli B&B najde celočíselné řešení, najdi v něm okruh — je-li to podtrasa ($|S| < n$), přidej podmínku (4) pro její množinu vrcholů $S$ a pokračuj. Opakuj, dokud řešením není okruh délky $n$.
Moderní solvery (Gurobi) na to mají callbacky: tvoje funkce se zavolá při každém nalezeném celočíselném řešení (událost MIPSOL), zkontroluje podtrasy a případně přidá addLazy(...) / cbLazy(...). Detailní kód (Java/Python/C++) je v cv10 — u písemky ho nepotřebuješ, ale princip „přidávej porušená omezení za běhu“ se hodí umět vysvětlit. Líné generování subtour-elimination podmínek je standardní součástí moderních exaktních TSP řešičů (Concorde apod.), které stojí za rekordy z [L3.3].
Pozor: časté chyby v TSP modelu- „Enter once + leave once stačí.“ NE — připouští podtrasy (dva oddělené okruhy je splní taky). Subtour elimination je povinná část modelu; bez ní u zkoušky přijdeš o podstatu úlohy.
- Zapomenuté $x_{i,i} = 0$ — smyčka „$i$ před $i$“ jinak lacino splní oba součty.
- MTZ napsané i pro $j = 1$ — model je pak nesplnitelný pro každý okruh (součet podél okruhu dá $\sum c \le 0$). Vstup do města 1 podmínku mít nesmí.
- $M$ příliš malé — vypnutá podmínka začne ořezávat přípustné okruhy a model lže; $M$ zbytečně obří zase kazí relaxaci a numeriku [L1.4].
- Množinové podmínky (4) vypsané všechny — je jich $2^n - 2$; buď je generuj líně, nebo použij MTZ.
Key takeaways — L3.4- Model okruhu: $x_{i,j} = 1$ ⟺ $i$ těsně před $j$; $\min \sum c_{i,j} x_{i,j}$; $x_{i,i}=0$; $\sum_i x_{i,j} = 1$ (enter once), $\sum_j x_{i,j} = 1$ (leave once). Samy o sobě nestačí — splní je i řešení rozpadlé na podtrasy.
- MTZ / cycle indivisibility: $s_i + c_{i,j} - (1 - x_{i,j}) \cdot M \le s_j$ pro $i \in 1..n$, $j \in 2..n$; $s_i$ = „čas vstupu do $i$“. Podtrasa bez města 1 dá po sečtení $\sum c \le 0$ — spor; návrat do města 1 ($j=1$) je z podmínky vyňat, aby se hlavní okruh směl uzavřít. Model má polynomiální velikost: $n^2$ binárek + $n$ spojitých $s_i$.
- Množinová alternativa: $\sum_{i,j \in S : i \ne j} x_{i,j} \le |S| - 1$ pro každou $\emptyset \ne S \subset V$ — exponenciálně mnoho ($2^n - 2$) → generovat lazy: přidávej jen podmínky porušené aktuálním celočíselným řešením, dokud řešení není okruh délky $n$.
- $s_i$ má reálný význam času — proto model přirozeně rozšíříš o time windows ($a_j \le s_j \le b_j$, úloha T02).
The source slide states the asymmetric Traveling Salesman Problem as follows. Instance: complete digraph $K_n$ with distance matrix $c : V \times V \to \mathbb{Q}_+$. Goal: find the shortest Hamiltonian cycle, i.e. a closed directed walk visiting every vertex exactly once.
Study task: formulate the ILP from the slide using binary variables $x_{ij} = 1 \iff$ node $i$ is in the cycle just before node $j$. Include self-loop avoidance, enter-once constraints, leave-once constraints, and subtour-elimination constraints using variables $s_i$ and a sufficiently large constant $M$.
a) Co je v zadání?
Vypsat zpaměti kompletní ILP model asymetrického TSP — přesně ten ze slidu 9, včetně eliminace podtras. Tohle je „katová“ modelovací úloha: každé z pěti pater modelu (účelová funkce, smyčky, enter, leave, MTZ) má svoje body a nejvíc se ztrácí na MTZ podmínce (rozsah indexů!).
b) Co k tomu budeme potřebovat?
- Tato lekce — celý model + proč enter/leave nestačí.
- [L0.8] Binární proměnná, [L1.4] big-M — přepínání podmínky přes $(1-x_{i,j}) \cdot M$.
c) Jak nad úlohou uvažovat?
Stav model po vrstvách a u každé si řekni, jaké „podvodné“ řešení zakazuje: bez $x_{i,i}=0$ vyhrají smyčky; bez enter/leave nic nedrží pohromadě; bez MTZ vyhrají podtrasy. U MTZ si vždy zkontroluj: (1) je tam $(1-x_{i,j})\cdot M$ se správným znaménkem? (2) běží $j$ od 2 (město 1 vyňato)? (3) řekl(a) jsi, co je $s_i$ a jak velké má být $M$?
d) Úplné řešení
Proměnné: $x_{i,j} \in \{0,1\}$ ($x_{i,j} = 1$ iff node $i$ is in the cycle just before node $j$), pomocné $s_i \in \mathbb{R}^+_0$ — „čas vstupu“ do města $i$. Parametry: $n$, matice $c \in \mathbb{Q}^+$, konstanta $M \in \mathbb{Z}^+$ dostatečně velká (např. $M = n \cdot \max_{i,j} c_{i,j}$).
$$\begin{aligned} \min \quad & \sum_{i \in 1..n} \sum_{j \in 1..n} c_{i,j} \cdot x_{i,j} \\ \text{s.t.} \quad & x_{i,i} = 0 && i \in 1..n && \text{avoid self-loop} \\ & \sum_{i \in 1..n} x_{i,j} = 1 && j \in 1..n && \text{enter once} \\ & \sum_{j \in 1..n} x_{i,j} = 1 && i \in 1..n && \text{leave once} \\ & s_i + c_{i,j} - (1 - x_{i,j}) \cdot M \le s_j && i \in 1..n,\ j \in 2..n && \text{cycle indivisibility} \end{aligned}$$
Vysvětlení podmínek (u zkoušky napiš aspoň větu ke každé):
- avoid self-loop: hrana $i \to i$ nesmí být v okruhu.
- enter once / leave once: každé město má v okruhu právě jednoho předchůdce a právě jednoho následníka → vybrané hrany tvoří disjunktní sjednocení orientovaných cyklů pokrývající všechna města.
- cycle indivisibility (MTZ): pro $x_{i,j} = 1$ vynucuje $s_i + c_{i,j} \le s_j$, pro $x_{i,j} = 0$ je díky $M$ neaktivní. Cyklus neobsahující město 1 by sečtením svých podmínek dal $\sum c_{i,j} \le 0$ — spor s $c > 0$; proto zůstane jediný cyklus, uzavřený přes město 1 (vstup do města 1 je z podmínky vyňat, $j \ge 2$). Podtrasy jsou eliminovány. $\blacksquare$
Consider the asymmetric TSP on a complete digraph $K_n$ where $c_{i,j} \in \mathbb{Q}^+$ now denotes the travel time from city $i$ to city $j$. The salesman starts in city 1 at time 0. Each city $j \in 2..n$ has a time window $[a_j, b_j]$: the salesman must enter city $j$ no earlier than $a_j$ and no later than $b_j$ (waiting is allowed). Formulate the problem as an ILP.
a) Co je v zadání?
Rozšíření modelu z T01: ceny jsou teď doby jízdy a každé město má povolené okno vstupu. Pointa úlohy: všiml(a) sis, že MTZ proměnné $s_i$ už jsou časy vstupu? Pak je rozšíření skoro zadarmo — přesně proto se tohle téma zkouší spolu se základním modelem.
b) Co k tomu budeme potřebovat?
- Úloha T01 v této lekci — základní model s MTZ.
- [L1.15] Časově/pozičně indexované proměnné — srovnání: tam byl čas diskrétní index proměnné, tady je čas spojitá hodnota proměnné $s_i$.
c) Jak nad úlohou uvažovat?
Polož si tři otázky. (1) Co přesně znamená $s_j$ v MTZ modelu a sedí to s „časem vstupu do města $j$“? (2) Jak se zapíše „vstup do okna“ pro proměnnou? (3) Dovolí nerovnost $s_i + c_{i,j} \le s_j$ čekání (přijet dřív a počkat před městem)? Nakonec zkontroluj $M$ — okna mění horní mez na $s$.
d) Úplné řešení (vlastní)
Vezmi celý model z T01 a doplň:
$$s_1 = 0 \qquad \text{(start v městě 1 v čase 0)},$$ $$a_j \le s_j \le b_j \qquad j \in 2..n \qquad \text{(time windows)}.$$
Proč to stačí: MTZ podmínka $s_i + c_{i,j} - (1-x_{i,j}) M \le s_j$ pro hrany okruhu vynucuje $s_j \ge s_i + c_{i,j}$ — vstup do $j$ nejdřív po dojezdu. Protože je to nerovnost, smí být $s_j$ i později než dojezd: to přesně modeluje povolené čekání (přijedu před otevřením okna $a_j$ a počkám). Okno pak ohraničí $s_j$ z obou stran. V základním modelu byly $s_i$ jen „pomocné hodinky“ na zabití podtras a jejich konkrétní hodnoty nikoho nezajímaly; tady dostaly fyzikální význam, proto musíme přibít start $s_1 = 0$.
Volba $M$: musí pokrýt největší možný rozdíl $s_i + c_{i,j} - s_j$, např. $M = \max_j b_j + \max_{i,j} c_{i,j}$ (vypnutá podmínka pak nikdy neořezává).
Subtilita (k ústní): návrat do města 1 žádnou MTZ podmínku nemá ($j \ge 2$), takže „deadline návratu do depa“ tenhle model nehlídá; kdyby ho zadání chtělo, přidala by se zvláštní proměnná $s_{n+1}$ pro čas návratu s podmínkou $s_i + c_{i,1} - (1-x_{i,1})M \le s_{n+1}$ a oknem na $s_{n+1}$. Pozor také: s okny už nemusí být optimum „okruh bez čekání“ — účelová funkce pořád minimalizuje jen součet dob jízdy.
TSP can be modeled as follows (Figure 1: ILP formulation of TSP, suitable for lazy constraints):
$$\min \sum_{(i,j) \in E} c_{i,j} \cdot x_{i,j} \tag{1}$$ $$\text{s.t.} \quad \sum_{(i,j) \in E} x_{i,j} = 1, \quad j \in V \tag{2}$$ $$\sum_{(i,j) \in E} x_{i,j} = 1, \quad i \in V \tag{3}$$ $$\sum_{i,j \in S : i \ne j} x_{i,j} \le |S| - 1, \quad S \subset V,\ S \ne \emptyset \tag{4}$$ $$x_{i,j} \in \{0,1\} \tag{5}$$
Explain: (a) why Constraints (4) eliminate subtours; (b) why the model cannot be written down explicitly for larger $n$; (c) how Constraints (4) can be generated in a lazy manner.
a) Co je v zadání?
Druhý způsob eliminace podtras — místo pomocných časů $s_i$ se podtrasy zakazují přímo po množinách vrcholů. Úkol je vysvětlit mechaniku (proč $|S|-1$), spočítat, že podmínek je exponenciálně, a popsat líné generování.
b) Co k tomu budeme potřebovat?
- Tato lekce — sekce „Alternativa: množinové podmínky a lazy constraints“.
- [L5.5] Branch & Bound — lazy podmínky se přidávají při nalezení celočíselného řešení během větvení.
c) Jak nad úlohou uvažovat?
(a) Kolik hran má okruh na množině $S$ a kolik jich podmínka povoluje? (b) Kolik je neprázdných vlastních podmnožin $V$? (c) Která řešení podtrasu vůbec můžou obsahovat a kdy je tedy potřeba podmínku kontrolovat? Projdi si stepper „lazy“ ve výkladu.
d) Úplné řešení (dle textu cv10)
(a) Podtrasa na vrcholech $S$ ($S \ne V$) je orientovaný cyklus, který uvnitř $S$ použije přesně $|S|$ hran. Podmínka (4) ale uvnitř $S$ povoluje nejvýš $|S|-1$ hran — cyklus uvnitř vlastní podmnožiny tedy zakazuje. Cv10 (EN 1:1): „having a subset of vertices with $|S|$ edges if $S \ne V$ means that there are subtours in the solution, for instance if $S = \{1,2,3\}$ then $\sum_{i,j \in S : i \ne j} x_{i,j} = 3 > |S|-1$.“ Hlavnímu okruhu přes všechna města podmínky nevadí: do žádné vlastní podmnožiny $S$ se nevejde celý — vždy z ní aspoň jednou „vyjede“, takže uvnitř $S$ má nejvýš $|S|-1$ hran.
(b) Podmínka (4) existuje pro každou neprázdnou vlastní podmnožinu $S \subset V$ — je jich $2^n - 2$, tedy exponenciálně mnoho (cv10: pro $n = 10$ to je 1022 podmínek). Explicitně vypsat je pro větší $n$ nelze.
(c) Líné generování (dle cv10): na začátku formuluj model jen s podmínkami (2), (3) a (5). Pokaždé, když B&B najde nové celočíselné řešení, najdi v něm cyklus; nechť $S$ je množina jeho vrcholů. Je-li $|S| < n$ (řešení obsahuje podtrasu), přidej do modelu odpovídající podmínku (4) — tím toto řešení vyloučíš z dalšího prohledávání. Podmínky se přidávají, dokud řešením není cyklus délky $n$. V Gurobi se to dělá callbackem volaným při události „nalezeno celočíselné řešení“ (MIPSOL) přes addLazy/cbLazy. $\blacksquare$
Srovnání s MTZ (k ústní): MTZ = kompaktní model $O(n^2)$, který napíšeš celý předem (a u písemky na papír); množinové podmínky = exponenciální rodina generovaná líně, v praxi často efektivnější. Obě verze jsou „subtour elimination“.