Časově/pozičně indexované proměnné
Prerekvizity: [L1.2] Přiřazovací struktura; hodí se i předkrm z [L1.14] (číslo boxu hračky jako $\sum_j j \cdot x_{ij}$). Tahle lekce uzavírá K1 — je to přehledová technika, která se naplno rozjede až v rozvrhování (kapitola K5), ale na písemce z ILP modelování se objevuje už teď (úloha Penguins on ice z termínu 02.06.2021).
Od „kdo–kam“ ke „kdo–kdy“
V [L1.2] rozhodovala binárka $x_{ij}$ o tom, kam objekt $i$ patří. Co když ale úloha neřeší „kam“, nýbrž „kdy“ — kdy odstartuje úloha na stroji, ve kterém kroku se tučňák pohne? Čas je spojitý… ILP ale chce konečně mnoho proměnných.
Zkus sám: jak z času udělat „pozice“, na které jde přiřazovat? A jak pak zapsat „akce $i$ nastane právě jednou“?
Čas diskretizuješ: povolené okamžiky jsou $t \in \{0, 1, \ldots, UB-1\}$ pro nějaký horizont $UB$ (poslední start musí stihnout proběhnout do $UB$). Každý okamžik je „přihrádka“ a rozhoduješ binárkou
$$x_{i,t} \in \{0,1\}, \qquad x_{i,t} = 1 \iff \text{akce } i \text{ nastane v čase } t.$$„Akce $i$ nastane právě jednou“ je pak řádkový součet, úplně stejný trik jako $\sum_j x_{ij} = 1$ v [L1.2]:
$$\sum_{t} x_{i,t} = 1 \qquad \forall i.$$Druhý index binárky prostě přestal být „box“ a stal se „okamžik“. Nic víc v té nové věci není — všechna síla je v tom, co z těch binárek jde lineárně vyrobit.
Čtení času z binárek
Mám binárky $x_{i,0}, x_{i,1}, \ldots, x_{i,UB-1}$ a chci s časem startu počítat — třeba říct „úloha $j$ startuje aspoň o $L$ později než úloha $i$“.
Zkus sám: napiš start $s_i$ úlohy $i$ jako lineární výraz z binárek. (V [L1.14] jsme stejně četli „číslo boxu hračky“.)
Právě jeden sčítanec je nenulový, takže součet „čas × binárka“ vrátí přesně ten čas, kde sedí jednička:
$$s_i = \sum_{t} t \cdot x_{i,t}.$$A „$j$ startuje aspoň o $L$ později než $i$“ je pak obyčejná lineární nerovnost
$$\sum_{t} t \cdot x_{i,t} + L \;\le\; \sum_{t} t \cdot x_{j,t},$$tedy $s_i + L \le s_j$. Přesně takhle se v K5 píší temporální omezení time-indexed modelu $PS1|temp|C_{max}$.
Zkus sám: co kdybys zapomněl omezení $\sum_t x_{i,t} = 1$? Najdi řešení, kde výraz $\sum_t t \cdot x_{i,t}$ lže.
Bez „právě jednou“ smí být všechny binárky nulové — pak $s_i = 0$ a solver si „start v čase 0“ vyrobil zadarmo, i když akce vůbec nenastala. Nebo dvě jedničky, třeba $x_{i,1} = x_{i,4} = 1$ — pak $s_i = 5$, čas, kdy se nestalo vůbec nic. Čtení funguje jen ve dvojici s $\sum_t x_{i,t} = 1$.
Nebezpečná polopravda: „$\sum_t t \cdot x_{i,t}$ je start úlohy“Sám o sobě NENÍ. Je to start úlohy jen spolu s omezením $\sum_t x_{i,t} = 1$. Samé nuly dají $s_i = 0$ (akce „nastala“ v čase 0, ač nenastala), dvě jedničky dají součet obou časů. Kdykoli na písemce čteš číslo z indexovaných binárek, zkontroluj, že máš v modelu i „právě jednou“.
Kolize: v čase $\tau$ běží nanejvýš jedna úloha
Druhý standardní typ omezení: sdílený zdroj (resource) — stroj, kra, políčko. Dvě akce ho nesmí používat současně.
Zkus sám: akce trvají 1 časový krok (např. „tah“ tučňáka). Zakaž, aby dvě nastaly ve stejném čase.
Sloupcový součet tabulky binárek — v každém okamžiku nanejvýš jedna jednička:
$$\sum_{i} x_{i,t} \;\le\; 1 \qquad \forall t.$$Zase stejná kostra jako sloupcové součty v [L1.2] (jen s $\le$, protože okamžik smí zůstat prázdný).
Zkus sám: teď ať úloha $2$ trvá $p_2 = 2$ kroky. Najdi rozvrh, který $\sum_i x_{i,\tau} \le 1$ splní, a přesto se úlohy „potkají na stroji“.
$T_2$ odstartuje v čase 1 (běží přes okamžiky 1 a 2) a $T_1$ odstartuje v čase 2. Žádné dva starty se nepotkaly — sloupcové součty platí — ale v okamžiku $\tau = 2$ běží obě úlohy. Sloupcový součet hlídá jen starty. Správně musíš sečíst všechny úlohy, které v $\tau$ běží: úloha $i$ běží v $\tau$, právě když odstartovala v některém $t$ s $t \le \tau < t + p_i$. Resource omezení time-indexed modelu (slide 66, K5) proto zní:
$$\sum_{i=1}^{n} \;\sum_{k = \max(0,\, \tau - p_i + 1)}^{\tau} x_{i,k} \;\le\; 1 \qquad \forall \tau \in \{0, \ldots, UB - 1\}.$$Vnitřní součet posbírá celé „okno“ startů, při kterých by úloha $i$ v čase $\tau$ ještě běžela.
Nebezpečná polopravda: „kolize = stejný start“$\sum_i x_{i,\tau} \le 1$ zakazuje jen společné starty. Úloha s $p_i > 1$ ale blokuje zdroj po celé okno $[s_i,\, s_i + p_i)$ — kolizi proto hlídej součtem přes okna startů $k \in \{\tau - p_i + 1, \ldots, \tau\}$ (ořezaná zdola nulou), ne jediným sloupcem. U akcí délky 1 obě verze splývají.
Cena za celou techniku: model má $n \cdot UB$ binárek (time-indexed model v K5 k nim přidá ještě jednu spojitou proměnnou $C_{max}$, celkem tedy $n \cdot UB + 1$) — diskretizaci času platíš počtem binárek (proto se volí co nejtěsnější horizont $UB$). Krokuj si všechny tři myšlenky na tabulce binárek výše: řádkový součet, čtení startu, okno zdroje.
Pozice místo času: tentýž trik bez hodin
Index $t$ vůbec nemusí být čas. Stejně dobře funguje pozice: pořadí v řadě ([L1.14] — box $b_j$), políčko šachovnice, buňka mřížky. Říká se tomu position-indexed / position-based model — v K5 se tak modeluje $1|r_j, \tilde{d}_j|C_{max}$ („úloha $i$ je $q$-tá v pořadí“).
Zkus sám: na šachovnici $8 \times 8$ rozmísti co nejvíc koní tak, aby se nenapadali. Co je tady „index“, co je binárka a jak vypadá zákaz napadení?
Index = políčko $s$ (dvojice řádek–sloupec), binárka $x_s = 1 \iff$ na $s$ stojí kůň. Kritérium: $\max \sum_s x_s$. Napadení je párová kolize — pro každou dvojici políček $s, s'$ vzdálených o koňský skok:
$$x_s + x_{s'} \;\le\; 1.$$Žádný čas, žádná okna — „zdroj“ je tu dvojice políček. A zakázaná políčka (třeba ohrožená věží) vynuluješ: $x_s = 0$, stejně jako zákaz krajních boxů v [L1.14].
Čas × pozice dohromady: tučňáci
Vrchol techniky: akce má kdo, kde i kdy. Na zkoušce 02.06.2021: tučňáci skáčou po krách, kra se po opuštění potopí, v čase $T_{max}$ má každý stát na svém cíli.
Zkus sám: kolik indexů potřebuje binárka pro tučňáky? A co bude říkat „právě jednou“?
Tři: $x_{i,c,t} = 1 \iff$ tučňák $i$ stojí na buňce $c$ v čase $t$. „Právě jednou“ tu neznamená „v čase“, ale „na právě jednom místě“ — v každém okamžiku stojí tučňák právě na jedné kře:
$$\sum_{c} x_{i,c,t} = 1 \qquad \forall i, \forall t,$$a sdílení kry je sloupcová kolize: $\sum_i x_{i,c,t} \le 1$ pro každou kru $c$ a čas $t$. Pohyb, potápění a celý model rozebereme v úloze T01 níže.
Stejná trojindexová myšlenka se vrátí u časově expandované sítě [L2.11] Časově expandovaná síť (constrained SP) („vrchol $(v,k)$ = jsem ve $v$ v čase $k$“), v rozvrhování (K5) a u TSP — proto je dobré ji mít v ruce už teď, jako poslední nástroj kapitoly K1.
Key takeaways — L1.15- Časově/pozičně indexovaná binárka: $x_{i,t} = 1 \iff$ akce $i$ nastane v čase/pozici $t$. Je to přiřazovací struktura [L1.2], kde druhý index je diskretizovaný čas (horizont $t \in \{0, \ldots, UB-1\}$) nebo pozice.
- „Začíná právě jednou“: $\sum_t x_{i,t} = 1$; čtení času: $s_i = \sum_t t \cdot x_{i,t}$ — funguje jen spolu s „právě jednou“. Pak jsou vztahy startů lineární: $s_i + L \le s_j$.
- Kolize/zdroj: v čase $\tau$ běží nanejvýš jedna úloha — sčítej okna startů $\sum_i \sum_{k=\max(0,\tau-p_i+1)}^{\tau} x_{i,k} \le 1$, ne jen společné starty (sloupec $\sum_i x_{i,\tau} \le 1$ stačí jen pro akce délky 1).
- Pozice = čas bez hodin: tentýž aparát pro pořadí v řadě, políčka šachovnice ($x_s + x_{s'} \le 1$ pro útočné dvojice, zakázané pole $x_s = 0$) i mřížku; kombinace čas × pozice dá $x_{i,c,t}$ (Penguins on ice).
- Naplno se technika použije v rozvrhování — time-indexed model $PS1|temp|C_{max}$ v K5 ($n \cdot UB$ binárek + 1 proměnná $C_{max}$) — a u TSP; tady stačí umět tabulku binárek postavit a přečíst.
“You are given a 2D grid of size $w \times h$. Each cell represents an ice cube floating on the water. There are $n$ penguins standing at starting positions $(x_1^{(s)}, y_1^{(s)}), (x_2^{(s)}, y_2^{(s)}), \ldots, (x_n^{(s)}, y_n^{(s)})$ at time $t = 0$. The time is discretized; during each time interval, each penguin can either remain on its position or it can move (by one tile) to its 4-neighborhood tiles. When the penguin moves, the ice cube on which it was standing sinks down, i.e., it cannot be used anymore. At most one penguin at time can stand on one ice cube.
Design an ILP model deciding whether the penguins can move in such a way that at time $T_{max}$, penguin $i$ stands at ending position $\left(x_i^{(e)}, y_i^{(e)}\right) \quad \forall i \in \{1, \ldots, n\}$.”
Figure: Illustration of an instance with $5 \times 5$ grid and three penguins starting at positions $(1,1)$, $(4,2)$ and $(3,3)$, respectively. The instance is feasible for $T_{max} \geq 8$.
a) Co je v zadání?
Mřížka $w \times h$ ledových ker, $n$ tučňáků se známými starty a cíli, čas běží v krocích $0, 1, \ldots, T_{max}$. V každém kroku tučňák buď stojí, nebo se posune na 4-souseda; opuštěná kra se potopí (už nikdy nejde použít); na kře stojí nanejvýš jeden tučňák. Otázka je rozhodovací (feasibility): existuje pohyb, po kterém v čase $T_{max}$ stojí každý tučňák na svém cíli? Postav ILP, jehož přípustnost to rozhodne.
b) Co k tomu budeme potřebovat?
- Tato lekce — trojindexová binárka $x_{i,c,t}$, „právě jedno místo v každém čase“, sloupcové kolize.
- [L1.2] Přiřazovací struktura — součty $=1$ a $\le 1$.
- [L1.3] Modelování logiky — linearizace AND pro detekci „nového vstupu na kru“ ($e = x_t \wedge \neg x_{t-1}$).
c) Jak nad úlohou uvažovat?
Elementární fakt o světě je „tučňák $i$ stojí na buňce $c$ v čase $t$“ — to přímo volá po $x_{i,c,t} \in \{0,1\}$. Pak ber pravidla po jednom: start a cíl jsou fixace binárek; „každý tučňák právě někde“ a „kra nanejvýš pro jednoho“ jsou součty. Pohyb je implikace mezi sousedními časy: kde smí být $i$ v čase $t$, když v $t-1$ stál na $c$? Nejtěžší je potápění — zkus si nejdřív říct, co přesně kra zakazuje: ne „stát dlouho“, ale „vstoupit podruhé“. Jak poznáš lineárně, že tučňák na kru právě vstoupil (v $t-1$ tam nebyl, v $t$ je)? To je AND dvou binárek — a od něj je k „každá kra nanejvýš jeden vstup celkem“ už jen jeden součet. Kritérium žádné není: feasibility úloha smí mít $\min 0$. (Dobový rukopisný pokus z písemky modeloval místo toho souřadnice $x_i^{(k)}, y_i^{(k)}$ jako čísla a topil se v absolutních hodnotách a big-M — indexované binárky jsou řádově čistší cesta.)
d) Úplné řešení
Množiny a značení. $P = \{1, \ldots, n\}$ tučňáci, $C = \{(x,y) : 1 \le x \le w,\ 1 \le y \le h\}$ buňky, $\mathcal{T} = \{0, 1, \ldots, T_{max}\}$ časy. $N(c)$ jsou 4-sousedé buňky $c$ uvnitř mřížky; $s_i = (x_i^{(s)}, y_i^{(s)})$ start a $g_i = (x_i^{(e)}, y_i^{(e)})$ cíl tučňáka $i$.
Proměnné.
$$x_{i,c,t} \in \{0,1\}: \quad x_{i,c,t} = 1 \iff \text{tučňák } i \text{ stojí na buňce } c \text{ v čase } t,$$ $$e_{i,c,t} \in \{0,1\}: \quad e_{i,c,t} = 1 \iff \text{tučňák } i \text{ na buňku } c \text{ v čase } t \text{ vstoupil}.$$Kritérium. Feasibility úloha: $\min 0$.
Start a cíl — fixace binárek:
$$x_{i,s_i,0} = 1 \quad \forall i \in P, \qquad x_{i,g_i,T_{max}} = 1 \quad \forall i \in P.$$Počáteční pozice se počítá jako vstup:
$$e_{i,c,0} = x_{i,c,0} \qquad \forall i \in P, \forall c \in C.$$Každý tučňák právě na jednom místě (tahle lekce — „právě jednou“ přes pozice):
$$\sum_{c \in C} x_{i,c,t} = 1 \qquad \forall i \in P, \forall t \in \mathcal{T}.$$Na kře nanejvýš jeden tučňák (sloupcová kolize):
$$\sum_{i \in P} x_{i,c,t} \le 1 \qquad \forall c \in C, \forall t \in \mathcal{T}.$$Legální pohyb včetně čekání — implikace mezi sousedními časy, pro $t = 1, \ldots, T_{max}$:
$$x_{i,c,t-1} \;\le\; x_{i,c,t} + \sum_{d \in N(c)} x_{i,d,t} \qquad \forall i \in P, \forall c \in C.$$Stál-li $i$ v čase $t-1$ na $c$, pak v čase $t$ je buď pořád na $c$ (čekání), nebo na některém 4-sousedovi. Pro $x_{i,c,t-1} = 0$ nerovnost nic nechce.
Detekce vstupu — $e_{i,c,t} = x_{i,c,t} \wedge \neg x_{i,c,t-1}$, linearizace AND z [L1.3], pro $t = 1, \ldots, T_{max}$:
$$e_{i,c,t} \ge x_{i,c,t} - x_{i,c,t-1}, \qquad e_{i,c,t} \le x_{i,c,t}, \qquad e_{i,c,t} \le 1 - x_{i,c,t-1} \qquad \forall i \in P, \forall c \in C.$$Trojice nerovností vynutí $e_{i,c,t} = 1 \iff (x_{i,c,t-1}, x_{i,c,t}) = (0,1)$: čekání na kře vstup nevytváří, návrat po odchodu by vytvořil druhý vstup.
Potápění ker — na každou kru se smí vstoupit celkem nanejvýš jednou:
$$\sum_{i \in P} \sum_{t \in \mathcal{T}} e_{i,c,t} \;\le\; 1 \qquad \forall c \in C.$$Tím je pokryto všechno, co potopení znamená: čekání je dovoleno (není to nový vstup), návrat na opuštěnou kru zakázán (druhý vstup), vstup jiného tučňáka na použitou kru zakázán (taky druhý vstup).
Velikost modelu: $O(n \cdot w h \cdot T_{max})$ binárek — typická cena časové indexace; horizont $T_{max}$ je naštěstí dán zadáním.
“You task is to place as many Knights as possible on $8 \times 8$ chessboard such that no two Knights attack each other. Furthermore, there might be some Rooks already placed on some fixed positions on the chessboard – in that case, you have to place the Knights such that they are not attacked by the Rooks.
We remind you that Knight moves in an ‘L-shape’ as illustrated in Figure 1. In case of the presence of a Rook on the chessboard, it threatens the whole row and column of the chessboard, as shown in Figure 2. We remind that you do not come up with the positions for the Rooks, these are given to you as an input. They just restrict some of the squares for your Knights.”
a) Co je v zadání?
Šachovnice $8 \times 8$, na vstupu množina věží na pevných pozicích. Umísti co nejvíc koní tak, aby (1) se žádní dva koně nenapadali (kůň útočí L-skokem $(\pm 1, \pm 2)$ a $(\pm 2, \pm 1)$) a (2) žádný kůň nestál na poli ohroženém věží — věž ohrožuje celý svůj řádek a sloupec (a její pole je obsazené). V originále je to praktická (programovací) úloha; tady ji řešíme jako ILP model, který by program volal.
b) Co k tomu budeme potřebovat?
- Tato lekce — pozičně indexovaná binárka $x_s$ na políčko, párová kolize $x_s + x_{s'} \le 1$.
- [L1.1] Cílová funkce a základní omezení — maximalizace součtu binárek.
- [L1.3] Modelování logiky — fixace zakázaných polí na 0, NAND dvojice.
c) Jak nad úlohou uvažovat?
Index je tady pozice — políčko šachovnice. Jedna binárka na políčko, kritérium je počet jedniček. Pak dvě pravidla: která políčka jsou zakázaná úplně (věže — spočti si je předem z dat, žádné proměnné pro věže!) a které dvojice políček se vylučují (koňský skok). Vylučující se dvojice binárek = součet $\le 1$ — žádné big-M, žádný čas. Rozmysli: stačí každou útočnou dvojici napsat jednou, nebo ji musíš psát v obou směrech?
d) Úplné řešení
Množiny (z dat, ne proměnné). $S = \{1,\ldots,8\} \times \{1,\ldots,8\}$ políčka; $R \subseteq S$ pozice věží (vstup); $A \subseteq S$ = pole ohrožená nebo obsazená věžemi = všechna pole sdílející řádek nebo sloupec s některou věží (každá věž ohrožuje i své vlastní pole, takže $R \subseteq A$). Pro políčko $s = (r, c)$ je
$$N(s) = \{(r \pm 1, c \pm 2), (r \pm 2, c \pm 1)\} \cap S$$množina polí napadených koněm stojícím na $s$ (vztah je symetrický: $s' \in N(s) \iff s \in N(s')$).
Proměnné. $x_s \in \{0,1\}$ pro $s \in S$; $x_s = 1 \iff$ na $s$ stojí kůň.
Kritérium.
$$\max \; \sum_{s \in S} x_s.$$Pole zakázaná věžemi — fixace na nulu:
$$x_s = 0 \qquad \forall s \in A.$$Žádní dva koně se nenapadají — pro každou neuspořádanou útočnou dvojici stačí jedna nerovnost (vztah je symetrický; napsat ji v obou směrech není chyba, jen duplicita):
$$x_s + x_{s'} \;\le\; 1 \qquad \forall s \in S,\ \forall s' \in N(s),\ s' \text{ „za“ } s \text{ v libovolném pevném uspořádání}.$$Výstup programu: $N = \sum_s x_s$ a seznam polí s $x_s = 1$. Sanity check: na prázdné šachovnici je optimum 32 (všechna pole jedné barvy — kůň útočí vždy na opačnou barvu, takže koně na bílých polích se nikdy nenapadají; vzorový výstup testu přesně tohle vrací).