LP relaxace jako dolní mez v B&B
Dokončujeme zkouškovou otázku z 9. 7. 2021: část a) — relative-order ILP — jsme postavili v [L5.6a] Relative-order ILP pro 1|prec|Σw_jC_j, část b) zní „Explain in detail, how to use relaxed LP solution in Branch and Bound method for $1\,|\text{prec}|\sum w_j C_j$?“. Obecný stroj Branch & Bound už máš z [L5.5] Branch & Bound pro ILP; dnes (slide 26) ho napojíme na rozvrhovací model — a protože jde o minimalizaci, všechno se oproti maximalizačnímu pseudokódu zrcadlí.
Kterým směrem mez ukazuje?
Zkus sám: model z L5.6a minimalizuje $J = \sum_j \sum_i p_i\,x_{ij}\,w_j$. Když binárky uvolníš na $0 \le x_{ij} \le 1$ a vyřešíš LP, je $J^{LP}$ horní, nebo dolní mez optimální hodnoty ILP? A proč?
Dolní. Každé celočíselné přípustné $x$ splňuje i uvolněná omezení, takže množina řešení ILP je podmnožinou množiny řešení LP ([L0.7] Co je ILP a LP relaxace). Minimum přes větší množinu nemůže být větší: $J^{LP} \le J^*$. U maximalizace (jak běžel pseudokód v [L5.5]) je to zrcadlově horní mez — směr si u zkoušky vždycky odvoď z „větší množina → lepší nebo stejné optimum“, ne z paměti.
Slide 26 (EN 1:1) — Branch and Bound with LP Bounding“We relax on the integrality of variable $x$:
- $0 \le x_{ij} \le 1$ and $x_{i \in 1..n, j \in 1..n} \in \mathbb{R}$
- This does not give us the right solution, however we can use the $J^{LP}$(remaining tasks) value of this LP formulation as a lower bound on the “amount of remaining work””
Všimni si formulace „does not give us the right solution“: LP ti vrátí bod, kde klidně $x_{23} = 0{,}5$ — „$T_2$ je napůl před $T_3$“. Jako rozvrh nesmysl, jako certifikovaná hodnota zlato: levněji než $J^{LP}$ to nejde.
Strom nad pořadími a test $J_2 + J^{LP} \ge J_1$
B&B strom tu nebudeme stavět větvením na souřadnicích jako v [L5.5], ale rovnou nad pořadími: uzel = rozhodnutý prefix rozvrhu (která úloha běží první, která druhá, …), větvení = volba další úlohy. Prefix má pevnou hodnotu $J_2 = \sum_{j \in \text{prefix}} w_j C_j$ (časy prefixu jsou určené) a zbytek je menší instance téhož problému.
Zkus sám: nejhloupější ořez je „zahoď uzel, když už samotný prefix má $J_2 \ge J_1$“ ($J_1$ = nejlepší dosud nalezené úplné řešení). Jak ořez zesílit pomocí $J^{LP}$ — a proč je to pořád korektní (nikdy nezahodíš optimum)?
Každé úplné dokončení uzlu stojí $J_2$ plus příspěvek zbývajících úloh, a ten je aspoň $J^{LP}(\text{zbývající úlohy})$ — LP je dolní mez i pro zbytek. Nejlepší list pod uzlem má tedy hodnotu $\ge J_2 + J^{LP}(\text{zbývající})$. Když už tohle je $\ge J_1$, nemůže dole být nic ostře lepšího než incumbent → celý podstrom zahoď. Korektnost stojí přesně na tom, že mez je dolní (optimistická): nikdy si zbytek nenamlouvá levnější, než opravdu je… naopak, namlouvá si ho levnější — a právě proto, když ani optimistický odhad nestačí, realita nestačí tím spíš.
Slide 26 (EN 1:1) — pravidlo ořezu“The Branch and Bound algorithm creates a similar tree as Bratley’s algorithm.
- Let $J_1$ be the value of the best solution known up to now
- We discard the partial solution of value $J_2$ not only when $J_2 \ge J_1$, but also when $J_2 + J^{LP}\text{(remaining tasks)} \ge J_1$.
Since the solution space of ILP is a subspace of LP we know: $J\text{(remaining tasks)} \ge J^{LP}\text{(remaining tasks)}$.”
Bratleyho algoritmus rozebíráme v [L5.9].
Test je neostrý ($\ge$, ne $>$): při rovnosti už pod uzlem nemůže být nic ostře lepšího než $J_1$, takže ho taky zavíráme — stejná logika jako u [L5.5]. A druhá volba designu: na zlomkovém $x_{ij}$ se tu nevětví. Obecné schéma z L5.5 by větvilo $x_{ij} \le 0 / x_{ij} \ge 1$ (u binárky jsou to přesně větve „$T_j$ před $T_i$“ / „$T_i$ před $T_j$“ — i to je legální odpověď); strom nad prefixy dělá totéž po balících a každý podproblém zůstává rozvrhovací úlohou.
Nebezpečné polopravdy: zaokrouhlení a směr ořezu① „LP řešení zaokrouhlím a mám rozvrh.“ Ne — zaokrouhlené $x$ může porušit antisymetrii i no-cycle (z $x_{ij} = 0{,}5$ uděláš snadno cyklus) a hlavně nic negarantuje o kvalitě. Z LP relaxace se v B&B používá jen hodnota $J^{LP}$ jako mez, ne bod. ② Směr: minimalizujeme, takže LP je mez dolní a ořezává se při $J_2 + J^{LP} \ge J_1$. Kdo si z maximalizačního pseudokódu L5.5 mechanicky přenese $z^{LP} \le z^b$, ořezává podle špatné strany.
Osahej si to: B&B s LP boundem na instanci z L5.6a
Stejná mini-instance jako v L5.6a (vlastní — přiznáno): $p = (2, 1, 3)$, $w = (1, 3, 2)$, precedence $T_1 \to T_2$. Připomeň si: přípustná pořadí jsou $(T_1,T_2,T_3)$ s $J = 23$, $(T_1,T_3,T_2)$ s $J = 30$ a $(T_3,T_1,T_2)$ s $J = 29$. Projdi DFS běh — sleduj hlavně uzly, kde samotné $J_2$ na ořez nestačí a LP mez ano:
Zkus sám: v kořeni vyšla LP relaxace celočíselně ($J^{LP} = 23$ v bodě pořadí $(T_1,T_2,T_3)$). Co by to znamenalo pro obecný B&B ve stylu L5.5, který kontroluje celočíselnost LP řešení?
Skončil by hned v kořeni: celočíselné LP optimum je přípustné pro ILP a má hodnotu rovnou dolní mezi → je to optimum. U $n = 3$ to tahle formulace udělá vždy; pro větší $n$ má polytop pořadí i zlomkové vrcholy a $J^{LP} < J^*$ klidně ostře (pozorování vlastní — slidy ho neuvádějí; přiznáno). Schéma ze slidu 26 celočíselnost LP bodu vůbec nezkoumá — LP mu dodává jen čísla $J^{LP}(\text{zbývající})$ a úplná řešení sbírá v listech stromu pořadí. Oba pohledy jsou korektní; u zkoušky popisuj ten ze slidu.
Position-based varianta: úloha na pozici $q$
Zkus sám: relace „před“ je jeden způsob, jak binárkami zakódovat permutaci. Napadne tě druhý — takový, který nepotřebuje žádná trojicová omezení?
Přiřazení úloha → pozice: $x_{iq} = 1 \iff$ úloha $i$ stojí v pořadí na $q$-tém místě. Permutaci pak vynutí dvě sady přiřazovacích rovností (každá úloha právě jednu pozici, každá pozice právě jednu úlohu) — žádné cykly nehrozí, takže $n^3$ trojic odpadá. Cenou je, že „kdo je přede mnou“ už není vidět ze sloupce — completion times se musí dopočítat přes proměnné startů pozic.
Přesně tohle dělá position-based ILP ze slidu 16 — formulovaný pro $1|r_j, \tilde{d}_j|C_{max}$, problém, který později vyřešíme i kombinatoricky Bratleyho B&B [L5.9]. Vedle matice $x_{iq}$ má spojité proměnné $t_q$ (start pozice $q$): pozice na sebe navazují, start nesmí předběhnout release time přiřazené úlohy a její deadline $\tilde{d}_i$ musí stihnout. Celý model si rozebereš v úloze T02 — slide k němu poznamenává „more efficient than relative order ILP“.
Key takeaways — L5.6b- LP relaxace relative-order modelu ($0 \le x_{ij} \le 1$, $x \in \mathbb{R}$) dává $J^{LP} \le J^*$ — dolní mez, protože řešení ILP jsou podmnožinou řešení LP ([L0.7]); u minimalizace je mez dolní, zrcadlově k maximalizaci z [L5.5].
- Strom nad pořadími (jako u Bratleyho [L5.9]): uzel = prefix s pevnou hodnotou $J_2$; ořež, jakmile $J_2 + J^{LP}(\text{zbývající úlohy}) \ge J_1$ (nejlepší známé úplné řešení) — i při rovnosti. Alternativa dle L5.5: větvit na zlomkové $x_{ij} = 0/1$ a řezat při $J^{LP}(\text{uzel}) \ge J_1$.
- LP bod není rozvrh: zlomkové $x_{ij}$ („napůl před“) nelze zaokrouhlit — z relaxace se používá jen hodnota $J^{LP}$.
- Position-based varianta: $x_{iq}$ (úloha $i$ na pozici $q$) + starty $t_q$ — permutace přes dvě přiřazovací rovnosti místo $n^3$ trojic; pro $1|r_j, \tilde{d}_j|C_{max}$ „more efficient than relative order ILP“ (slide 16, úloha T02).
“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) je formulace z minulé lekce — vyřešená v [L5.6a] T01. Tady řešíme část b): „explain in detail“ znamená, že nestačí věta „LP dá mez“ — chtějí relaxaci (co přesně se uvolní), směr meze se zdůvodněním, tvar stromu a přesné pravidlo ořezu.
b) Co k tomu budeme potřebovat?
- Tato lekce — relaxace, dolní mez, test $J_2 + J^{LP} \ge J_1$ (takeaways).
- [L5.6a] Relative-order ILP pro 1|prec|Σw_jC_j — model, který relaxujeme.
- [L5.5] Branch & Bound pro ILP (grafické řezání) — obecné schéma větvení a mezí.
- [L0.7] Co je ILP a LP relaxace — argument podmnožinou.
c) Jak nad úlohou uvažovat?
Odpověz ve čtyřech krocích a každý zdůvodni: ① co relaxuji (jen integralitu $x$); ② proč je výsledek dolní mez (kam se poděla množina řešení?); ③ jak vypadá strom (co je uzel, co je $J_2$, co znamená „remaining tasks“); ④ kdy uzel zahodím — a proč ten test nikdy nezahodí optimum. Bonusový bod za poznámku, že LP bod se nepoužívá (není to rozvrh), jen hodnota.
d) Úplné řešení (dle slidu 26, 1:1)
① Relaxace. V ILP z části a) uvolníme integralitu proměnných: $0 \le x_{ij} \le 1$, $x_{ij} \in \mathbb{R}$ (kritérium i všechna omezení — precedence, antisymetrie, no-cycle trojice, diagonála — zůstávají). Výsledek je LP, řešitelné polynomiálně.
② Směr meze. Každé přípustné řešení ILP splňuje i omezení LP, takže prostor řešení ILP je podprostorem LP („Since the solution space of ILP is a subspace of LP“); minimum přes nadmnožinu je nejvýš tak velké: $J^{LP} \le J$. LP samo „does not give us the right solution“ (typicky zlomkové $x$, žádný rozvrh), ale jeho hodnota je korektní dolní mez množství zbývající práce.
③ Strom. B&B staví strom podobný Bratleyho algoritmu: uzel = částečné řešení (prefix pořadí) s hodnotou $J_2 = \sum_{j \in \text{prefix}} w_j C_j$; potomci = volby další úlohy (respektující precedence). Pro neserazený zbytek uzlu spočítáme $J^{LP}(\text{remaining tasks})$ — LP relaxaci modelu zbývajících úloh (navazujících za prefixem).
④ Ořez. Nechť $J_1$ je hodnota nejlepšího dosud nalezeného úplného řešení. Částečné řešení hodnoty $J_2$ zahodíme nejen když $J_2 \ge J_1$, ale už když $$J_2 + J^{LP}(\text{remaining tasks}) \ge J_1,$$ protože skutečné dokončení stojí $J_2 + J(\text{remaining}) \ge J_2 + J^{LP}(\text{remaining}) \ge J_1$ — pod uzlem nemůže být nic ostře lepšího než $J_1$, optimum tedy ořezem nikdy neztratíme. List (úplné pořadí) případně aktualizuje $J_1$; algoritmus končí, když jsou všechny větve uzavřené, a vrátí $J_1$.
“The source slide gives the following position-based ILP formulation. Study it and be able to reproduce/explain it.
Let $x_{iq} = 1$ iff task $i$ is at the $q$-th position in the sequence of tasks, and let $t_q$ be the start time of the task on the $q$-th position.”
(Otázky vlastní — přiznáno:) (i) Write down the full model and explain the role of every constraint. (ii) Which constraints encode the permutation and which the time windows $[r_i, \tilde{d}_i]$? (iii) Compare the model size with the relative-order ILP — why does the slide note “more efficient than relative order ILP”?
a) Co je v zadání?
Studijní úloha z banky: umět reprodukovat a vysvětlit druhé kódování pořadí — přiřazení úloh na pozice. Problém je $1|r_j, \tilde{d}_j|C_{max}$: jeden stroj, release times a deadliny, minimalizuj makespan (tentýž problém řeší kombinatoricky Bratleyho B&B [L5.9]).
b) Co k tomu budeme potřebovat?
- Tato lekce — myšlenka „úloha na pozici $q$“ (takeaways).
- [L5.6a] — relative-order model pro srovnání velikostí.
- [L5.1] Grahamova notace — čtení $1|r_j, \tilde{d}_j|C_{max}$ ($\tilde{d}_j$ = deadline, tvrdé omezení).
c) Jak nad úlohou uvažovat?
Rozděl model na tři vrstvy: ① permutace (co zaručí, že $x$ je matice přiřazení?), ② časy (jak na sebe pozice navazují a kde se vezme $r$ a $\tilde{d}$ úlohy přiřazené na pozici $q$ — všimni si triku $\sum_i r_i x_{iq}$: suma s právě jednou jedničkou „vybere“ parametr), ③ kritérium ($C_{max}$ = konec poslední pozice). U (iii) spočítej omezení obou modelů.
d) Úplné řešení (formulace dle slidu 16 / banky #36, 1:1; komentáře vlastní — přiznáno)
“variables: $x_{i \in 1..n, q \in 1..n} \in \{0,1\}$, $C_{\max} \in \langle 0, UB \rangle$, $t_{q \in 1..n} \in \langle 0, UB \rangle$ … more efficient than relative order ILP”
(i)–(ii) Po vrstvách:
- Permutace = první dvě rovnosti: každá úloha právě na jedné pozici a každá pozice obsazena právě jednou úlohou ($x$ je permutační matice). Žádné no-cycle trojice nejsou potřeba.
- Časy: $t_q \ge \sum_i r_i x_{iq}$ — start pozice $q$ nesmí předběhnout release time přiřazené úlohy (suma s jedinou jedničkou vybere její $r_i$); $t_q \ge t_{q-1} + \sum_i p_i x_{i,q-1}$ — pozice $q$ začne až po doběhnutí pozice $q-1$ (jeden stroj, navazování); $t_q \le \sum_i \tilde{d}_i x_{iq} - \sum_i p_i x_{iq}$ — úloha na pozici $q$ musí stihnout svůj deadline: start $\le \tilde{d}_i - p_i$. To jsou přesně okna $[r_i, \tilde{d}_i]$.
- Kritérium: $C_{\max} \ge t_n + \sum_i p_i x_{in}$ — makespan je aspoň konec poslední pozice; minimalizace ho přitlačí na rovnost.
(iii) Srovnání (vlastní rozbor — přiznáno): oba modely mají $n^2$ binárek, ale relative-order model z [L5.6a] potřebuje $\Theta(n^3)$ trojicových omezení proti cyklům; tady permutaci hlídá $2n$ přiřazovacích rovností a časům stačí $O(n)$ řádků navíc (plus $n+1$ spojitých proměnných $t_q$, $C_{max}$ s doménou $\langle 0, UB \rangle$ — $UB$ je jen mez domény, počet proměnných na něm nezávisí, na rozdíl od time-indexed modelu [L5.3]). Proto slide: „more efficient than relative order ILP“. Relative-order naopak umí přímo lineárně vyjádřit $\sum w_j C_j$ ze sloupců — každé kódování se hodí na jiné kritérium.