Relative-order ILP pro 1|prec|ΣwjCj
Tohle je doložená zkoušková otázka: na zkoušce 9. 7. 2021 padla i s b) částí o B&B; dochoval se přepis ručního řešení části a) včetně chyby ve vyjádření $C_j$, kterou za chvíli uvidíš červeně opravenou. Na zkoušce 29. 6. 2023 zněla otázka 6 doslova: „SCHED — ILP formulace pro $1|prec|\sum w_j C_j$, rict jak se LP relaxace toho ILP da pouzit pri branch and bound algoritmu.“ Dnes postavíme tu ILP formulaci (slidy 24–25); LP relaxace + B&B (slide 26) je příští lekce [L5.6b] LP relaxace jako dolní mez v B&B, která použije stroj z [L5.5] Branch & Bound pro ILP.
Proč na to potřebujeme ILP?
Zkus sám: bez precedencí, $1\,||\,\sum w_j C_j$ — úlohy s dobami $p_j$ a vahami $w_j$ na jednom stroji. Jak je seřadíš, aby vážený součet dokončení byl nejmenší? (Zkus nejdřív $w_j = 1$.)
Pro $w_j = 1$ řadíš od nejkratší: SPT (Shortest Processing Time first) — krátká úloha na začátku „zdržuje“ všechny za sebou nejméně. S vahami totéž v poměru: WSPT — neklesající $p_j / w_j$ (krátké a důležité dopředu). Obojí je greedy a běží v $O(n \log n)$ — žádné ILP. Jenže přidej precedence a greedy se rozbije: „urgentní“ úloha může být zamčená za pomalým předchůdcem a lokální prohození už nejde.
Slide 23 (EN 1:1, výběr relevantních řádků) — Scheduling on One Resource — Minimizing $\sum w_j C_j$- “$1 \,||\, \sum C_j$ — easy — SPT rule (Shortest Processing Time first) — schedule the tasks in a non-decreasing order of $p_j$”
- “$1 \,||\, \sum w_j C_j$ — easy — Weighted SPT — schedule the tasks in a non-decreasing order of $\frac{p_j}{w_j}$”
- “$1 \,|\, \mathrm{prec} \,|\, \sum C_j$ — NP-hard”
Už jen nevážené $1|prec|\sum C_j$ je NP-těžké — a přesně proto se ptáme na ILP formulaci (zápis problému z [L5.1] Grahamovy notace čteš: jeden stroj, úlohy s precedencemi z grafu $G$ jako v [L5.2] Precedence a temporální omezení, minimalizuj $\sum w_j C_j$; bez preempce — to je default prázdného $\beta$).
Rozvrh na jednom stroji = pořadí
Na jednom stroji bez release times se nevyplatí nikdy čekat: každou mezeru můžeš zavřít posunutím všeho doleva a žádné $C_j$ se nezhorší. Optimální rozvrh je tedy permutace úloh bez mezer — jediné, co hledáme, je pořadí.
Zkus sám: jak zakóduješ „pořadí $n$ úloh“ do binárních proměnných ([L0.8])? Nech se inspirovat tím, jak je v zadání zakódovaný precedenční graf: $e_{ij} = 1$, když vede hrana $T_i \to T_j$.
Stejným jazykem: binárka pro každou dvojici, $x_{ij} = 1 \iff T_i$ je v rozvrhu před $T_j$. Permutace je přesně relace „před“ na všech dvojicích — úplná (každá dvojice rozhodnutá), antisymetrická a bez cyklů. Pozor: $x_{ij}$ zavádíš pro všechny dvojice, ne jen pro hrany $G$ — i dvě precedencí nesvázané úlohy musí na jednom stroji nějaké pořadí mít.
Slide 24 (EN 1:1) — Branch and Bound with LP for $1 \,|\, \mathrm{prec} \,|\, \sum w_j C_j$- “First, we formulate the problem as an ILP:
- we use variable $x_{ij} \in \{0, 1\}$ such that $x_{ij} = 1$ iff $T_i$ precedes $T_j$ or $i = j$
- we encode precedence relations into $e_{ij} \in \{0, 1\}$ such that $e_{ij} = 1$ iff there is a directed edge from $T_i$ to $T_j$ in the precedence graph $G$ or $i = j$”
Drobnost s velkým dopadem: konvence „or $i = j$“ znamená $x_{ii} = 1$ a $e_{ii} = 1$ na diagonále — uvidíš za chvíli, že se diagonála hodí do vzorce pro $C_j$.
Omezení: precedence, antisymetrie, žádný cyklus
① Precedence: když $G$ obsahuje hranu $T_i \to T_j$, musí být $T_i$ před $T_j$ i v rozvrhu. To je implikace „$e_{ij} = 1 \Rightarrow x_{ij} = 1$“, a protože obojí jsou binárky (a $e$ je parametr), stačí nerovnost $$x_{ij} \ge e_{ij} \qquad i, j \in 1..n.$$ Pro $e_{ij} = 0$ nic nevynucuje, pro $e_{ij} = 1$ přibije $x_{ij} = 1$. (Diagonálu $x_{ii} = 1$ vynutí $e_{ii} = 1$; slide 25 ji pro jistotu uvádí i explicitně.)
② Antisymetrie: pro každou dvojici $i \ne j$ právě jeden směr: $$x_{ij} + x_{ji} = 1 \qquad i, j \in 1..n,\ i \ne j.$$ Buď $T_i$ před $T_j$, nebo naopak — nikdy obojí, nikdy nic. (Je to „buď–anebo“ bez big-M: nepotřebujeme žádné časy, jen směr. Srovnej s [L1.4] big-M: disjunkce omezení, kde se stejná disjunkce řeší přes velkou konstantu, protože tam figurují spojité starty.)
Zkus sám: stačí to? Najdi matici $x$ pro 3 úlohy, která splní antisymetrii (i precedenci s prázdným $G$) — a přesto nepopisuje žádné pořadí.
$x_{12} = x_{23} = x_{31} = 1$ (a doplněk $x_{21} = x_{32} = x_{13} = 0$). Každá dvojice je v pořádku, ale dohromady: $T_1$ před $T_2$, $T_2$ před $T_3$, $T_3$ před $T_1$ — cyklus. Žádná úloha není první, takový „rozvrh“ neexistuje. Antisymetrie hlídá dvojice; cykličnost je vlastnost trojic a víc.
③ No-cycle: pro každou trojici navzájem různých $i, j, k$: $$1 \le x_{ij} + x_{jk} + x_{ki} \le 2 \qquad i, j, k \in 1..n,\ i \ne j \ne k.$$ Součet $3$ by znamenal cyklus $T_i \to T_j \to T_k \to T_i$; součet $0$ znamená (díky antisymetrii) $x_{ji} = x_{kj} = x_{ik} = 1$, tedy tentýž cyklus obráceně. Obě hodnoty zakazujeme, povolené zůstávají jen „tranzitivní“ kombinace 1 a 2.
Zkus sám: trojice zakazují jen cykly délky 3. Co cyklus délky 4 a víc — neproklouzne?
Neproklouzne. Po antisymetrii je digraf proměnných $x$ turnaj (mezi každou dvojicí právě jedna šipka) — a v turnaji každý cyklus obsahuje cyklus délky 3: vezmi cyklus $a \to b \to c \to \cdots \to a$ délky $\ge 4$ a podívej se na šipku mezi $a$ a $c$. Je-li $x_{ca} = 1$, máš trojúhelník $a \to b \to c \to a$; je-li $x_{ac} = 1$, zkrátil jsi cyklus o vrchol $b$ — a opakuj. Nejkratší cyklus turnaje má tedy délku 3, takže zákaz trojic stačí. (Zdůvodnění vlastní — slidy to nedokazují; přiznáno.)
Kritérium: čemu se rovná $C_j$?
Zkus sám (tady se na zkoušce chybuje): máš matici $x$. Napiš lineární vyjádření completion time $C_j$. Nápověda: rozvrh nemá mezery — co všechno proběhne, než $T_j$ skončí?
Než $T_j$ skončí, proběhnou všechny úlohy, které jsou před ní (tj. všechna $T_i$ s $x_{ij} = 1$, $i \ne j$), a pak ona sama: $$C_j = p_j + \sum_{i \ne j} p_i\,x_{ij} \;=\; \sum_{i=1}^{n} p_i\,x_{ij},$$ kde druhá rovnost využila diagonálu $x_{jj} = 1$ — proto ta konvence „or $i = j$“! Žádná další proměnná ani omezení nejsou potřeba: $C_j$ je prostě lineární výraz v $x$ (sloupec $j$ matice, skalárně s vektorem $p$).
Nebezpečná polopravda: „$C_j$ svážu nerovností s $p$“V dochovaném ručním řešení této otázky ze zkoušky 9. 7. 2021 student napsal omezení „$p_i \cdot x_{ij} \le C_j$ // set $C_j$“ — a opravující k tomu červeně: „to nestačí !! $C_j$ je suma processingu“. Nerovnost $p_i x_{ij} \le C_j$ říká jen „$C_j$ je aspoň tak velké jako každý jednotlivý předchůdce“, jenže předchůdci se sčítají (stroj je jeden, běží za sebou). Správně: $C_j = \sum_i p_i\,x_{ij}$ — completion time není $p_j$ ani maximum, je to součet dob všech úloh před $j$ plus $p_j$. Tohle je ta skrytá past celé formulace.
Slide 24 (EN 1:1) — criterion“criterion — completion time of task $T_j$ consists of $p_j$ and the processing time of its predecessors:
$$\begin{aligned} C_j &= \sum_{i=1}^{n} p_i \cdot x_{ij} \\ w_j \cdot C_j &= \sum_{i=1}^{n} p_i \cdot x_{ij} \cdot w_j \\ J = \sum_{j=1}^{n} w_j \cdot C_j &= \sum_{j=1}^{n} \sum_{i=1}^{n} p_i \cdot x_{ij} \cdot w_j \end{aligned}$$from all feasible schedules $x$ we look for the one that minimizes $J(x)$, i.e. $\min_x J(x)$”
Výraz $p_i \cdot x_{ij} \cdot w_j$ vypadá jako součin tří věcí, ale $p_i$ a $w_j$ jsou parametry (čísla ze zadání) — proměnná je v každém členu jen jedna, takže kritérium je lineární a ILP je legální.
Celý model (slide 25)
Slide 25 (EN 1:1) — ILP formulation for $1 \,|\, \mathrm{prec} \,|\, \sum w_j C_j$“parameters: $w_{i \in 1..n}, p_{i \in 1..n} \in \mathbb{R}_0^+$, $e_{i \in 1..n, j \in 1..n} \in \{0, 1\}$ variables: $x_{i \in 1..n, j \in 1..n} \in \{0, 1\}$”
Velikost: $n^2$ binárek a kvůli trojicím řádově $n^3$ omezení — ale nic nezávisí na délce rozvrhu. To je přesně opačný trade-off než time-indexed model z [L5.3] Time-indexed ILP pro PS1|temp|Cmax, jehož velikost roste s horní mezí $UB$ (srovnání obou reprezentací = slide 71, citované v L5.3). Časy tu vůbec nejsou proměnné: pořadí je určuje samo.
Osahej si to: od pořadí k matici $x$ a k $J$
Mini-instance (vlastní — přiznáno): $n = 3$, $p = (2, 1, 3)$, $w = (1, 3, 2)$, precedenční graf $G$ má jedinou hranu $T_1 \to T_2$. Proklikej, jak pořadí určí matici $x$ a jak se z jejích sloupců čtou $C_j$:
Matice $x$ pro vítězné pořadí $(T_1, T_2, T_3)$ — všimni si jedničkové diagonály a toho, že $C_j$ je skalární součin vektoru $p$ se sloupcem $j$:
$$x = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}, \qquad C_j = \sum_i p_i\,x_{ij}:\quad C = (2,\ 3,\ 6), \qquad J = 1\!\cdot\!2 + 3\!\cdot\!3 + 2\!\cdot\!6 = 23.$$
Key takeaways — L5.6a- Rozvrh na jednom stroji = permutace; kódují ji pořadové proměnné $x_{ij} = 1 \iff T_i$ předchází $T_j$ (konvence $x_{ii} = 1$), zavedené pro všechny dvojice, ne jen hrany $G$.
- Tři skupiny omezení: precedence $x_{ij} \ge e_{ij}$; antisymetrie $x_{ij} + x_{ji} = 1$ ($i \ne j$); no-cycle $1 \le x_{ij} + x_{jk} + x_{ki} \le 2$ pro trojice (dolní mez vyřadí obrácený cyklus; delší cykly v turnaji vždy obsahují trojúhelník, takže trojice stačí).
- Past kritéria: $C_j$ není $p_j$ ani „$p_i x_{ij} \le C_j$“ — je to součet dob všech úloh před $j$ plus $p_j$: $C_j = \sum_i p_i\,x_{ij}$ (diagonála přidá $p_j$). Kritérium $\min \sum_j \sum_i p_i\,x_{ij}\,w_j$ je lineární, protože $p_i, w_j$ jsou parametry.
- Velikost modelu nezávisí na $UB$ ($n^2$ proměnných, ~$n^3$ omezení) — opačný trade-off než time-indexed model [L5.3].
- K čemu dál: LP relaxace tohoto ILP dává dolní mez $J^{LP}$ pro Branch & Bound — to je [L5.6b], technika větvení a mezí z [L5.5].
“a) Using ILP formulate scheduling of nonpreemptive tasks with precedence relations on one resource while minimizing weighted sum of completion times, i.e., $1\,|\text{prec}|\sum w_j C_j$. Task $T_j$ has general processing time $p_j$. Precedence relations are encoded in $e_{ij} \in \{0,1\}$ such that $e_{ij} = 1$ if there is a directed edge from $T_i$ to $T_j$ in the precedence graph $G$ or $i = j$.
b) Explain in detail, how to use relaxed LP solution in Branch and Bound method for $1\,|\text{prec}|\sum w_j C_j$?”
a) Co je v zadání?
Část a) chce celou ILP formulaci — proměnné, kritérium, všechna omezení, parametry a domény. Kódování $e_{ij}$ (včetně diagonály $e_{ii} = 1$) ti zadání dává, takže se očekává relative-order model. Část b) je o LP relaxaci jako dolní mezi v B&B — řeší ji příští lekce [L5.6b]; tady ji jen poznáme podle zadání.
b) Co k tomu budeme potřebovat?
- Tato lekce — pořadové proměnné, tři skupiny omezení, past s $C_j$ (takeaways).
- [L5.1] Grahamova notace — přečíst $1|prec|\sum w_j C_j$.
- [L0.8] Binární proměnná — $x_{ij} \in \{0,1\}$.
- [L5.2] Precedence a temporální omezení — co je precedenční graf $G$.
c) Jak nad úlohou uvažovat?
Postupuj v pořadí, v jakém jsme model stavěli: ① co je rozhodnutí? (pořadí → $x_{ij}$ pro každou dvojici) ② co ho dělá přípustným? (precedence z $e$, antisymetrie, žádný cyklus — nezapomeň, proč dvojice nestačí) ③ co měříme? ($C_j$ — a tady zpomal: je to součet, ne jednotlivá nerovnost). Nakonec deklaruj parametry a proměnné — u zkoušky se na „variables/parameters“ řádek opravdu kouká.
d) Úplné řešení (dle slidů 24–25, 1:1)
Proměnné: $x_{ij} \in \{0,1\}$ pro $i, j \in 1..n$; $x_{ij} = 1 \iff T_i$ předchází $T_j$ v rozvrhu, nebo $i = j$.
Kritérium: completion time se skládá z $p_j$ a dob všech předchůdců v rozvrhu, $C_j = \sum_{i=1}^{n} p_i\,x_{ij}$ (diagonála $x_{jj} = 1$ dodá $p_j$), tedy
$$\min \sum_{j=1}^{n} \sum_{i=1}^{n} p_i \cdot x_{ij} \cdot w_j$$Omezení:
$$\begin{aligned} & x_{i,j} \ge e_{i,j} && i, j \in 1..n && \text{(hrana } T_i \to T_j \text{ v } G \Rightarrow T_i \text{ před } T_j \text{ v rozvrhu)} \\ & x_{i,j} + x_{j,i} = 1 && i, j \in 1..n,\ i \ne j && \text{(buď } T_i \text{ před } T_j\text{, nebo naopak)} \\ & 1 \le x_{i,j} + x_{j,k} + x_{k,i} \le 2 && i, j, k \in 1..n,\ i \ne j \ne k && \text{(v digrafu } x \text{ není cyklus)} \\ & x_{i,i} = 1 && i \in 1..n \end{aligned}$$Parametry: $w_i, p_i \in \mathbb{R}_0^+$ pro $i \in 1..n$; $e_{ij} \in \{0,1\}$. Proměnné: $x_{ij} \in \{0,1\}$.
K vysvětlení (ústně/poznámkou): antisymetrie dělá z $x$ turnaj, trojicová podmínka zakáže cykly v obou orientacích (součty 3 a 0) a delší cyklus v turnaji vždy obsahuje trojúhelník; $C_j$ musí být suma — nerovnost $p_i x_{ij} \le C_j$ je doložená zkoušková chyba (červená oprava: „to nestačí !! $C_j$ je suma processingu“).
Část b) — stručně (detailně v [L5.6b]): integrální podmínku na $x$ uvolníme na $0 \le x_{ij} \le 1$; hodnota $J^{LP}$ takové LP relaxace je dolní mez hodnoty ILP (prostor řešení ILP je podmnožinou LP), takže v B&B stromu můžeme uzel s částečným řešením hodnoty $J_2$ zahodit, jakmile $J_2 + J^{LP}(\text{zbývající úlohy}) \ge J_1$, kde $J_1$ je nejlepší dosud nalezené celočíselné řešení.
“Consider $n = 3$ tasks with $p = (2, 1, 3)$, $w = (1, 3, 2)$ and a single precedence edge $T_1 \to T_2$ (i.e. $e_{12} = 1$, $e_{ii} = 1$, all other $e_{ij} = 0$).
(i) Write the matrix $x$ corresponding to the order $(T_3, T_1, T_2)$, verify all constraints of the relative-order ILP and compute the criterion value $J$.
(ii) Take $x$ with $x_{12} = x_{23} = x_{31} = 1$ (completed by antisymmetry and $x_{ii} = 1$). Is it feasible? Which constraint fails?
(iii) For general $n$: how many variables and (roughly) how many constraints does the model have? Does its size depend on the upper bound of the schedule length $UB$?”
a) Co je v zadání?
Tři rychlé kontroly porozumění: zakódovat pořadí do $x$ a spočítat $J$ ze sloupců (i), poznat nepřípustnou matici a pojmenovat porušené omezení (ii), a říct velikost modelu (iii) — přesně ten druh podotázek, kterými se u ústní části ověřuje, že formulaci nemáš jen namemorovanou.
b) Co k tomu budeme potřebovat?
- Tato lekce — vzorec $C_j = \sum_i p_i x_{ij}$ a tři skupiny omezení (takeaways).
- Stepper výše — stejná instance, jiné pořadí.
c) Jak nad úlohou uvažovat?
(i) Řádek $i$ matice říká „koho všechno $T_i$ předbíhá“: první úloha pořadí má jedničky všude, poslední jen na diagonále. $C_j$ čti po sloupcích. Zkontroluj hlavně $x_{12} \ge e_{12}$. (ii) Sečti trojici $x_{12} + x_{23} + x_{31}$. (iii) Spočítej zvlášť dvojice a trojice indexů; pak se zeptej, kde by se $UB$ vůbec mohlo objevit.
d) Úplné řešení (vlastní — přiznáno)
(i) Pořadí $(T_3, T_1, T_2)$: $T_3$ předbíhá obě ($x_{31} = x_{32} = 1$), $T_1$ předbíhá $T_2$ ($x_{12} = 1$), zbytek dvojic 0, diagonála 1:
$$x = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix}$$Kontroly: $x_{12} = 1 \ge e_{12} = 1$ ✓; antisymetrie pro všechny tři dvojice ✓; trojice: $x_{12} + x_{23} + x_{31} = 1 + 0 + 1 = 2$ ✓ a $x_{21} + x_{13} + x_{32} = 0 + 0 + 1 = 1$ ✓. Sloupce: $C_1 = p_1 + p_3 = 5$, $C_2 = p_1 + p_2 + p_3 = 6$, $C_3 = p_3 = 3$.
$$J = w_1 C_1 + w_2 C_2 + w_3 C_3 = 1 \cdot 5 + 3 \cdot 6 + 2 \cdot 3 = 29 \;(> 23 = J^* \text{ pořadí } (T_1, T_2, T_3)).$$(ii) Nepřípustná: trojicová podmínka dává $x_{12} + x_{23} + x_{31} = 3 \not\le 2$ — cyklus $T_1 \to T_2 \to T_3 \to T_1$, žádná úloha není první. Precedence i antisymetrie přitom platí — proto no-cycle omezení v modelu být musí.
(iii) Proměnných je $n^2$ (všechna $x_{ij}$). Omezení: $n^2$ precedenčních, $n^2 - n$ antisymetrií (každá neuspořádaná dvojice se v zápisu slidu objeví dvakrát — jednou by stačila), $n(n-1)(n-2)$ trojicových (zrcadlová orientace trojice je díky antisymetrii implikovaná: součty obou orientací dávají dohromady 3, takže by stačila polovina) a $n$ diagonálních — celkem řádově $\Theta(n^3)$. Na $UB$ velikost nezávisí vůbec — v modelu žádný čas nefiguruje; to je hlavní rozdíl proti time-indexed modelu [L5.3] s $n \cdot UB$ proměnnými.