L5.5 Kapitola K5 — Rozvrhování (Slot 5) · [MUST] · FOTO checkpoint kapitoly

Branch & Bound pro ILP (grafické řezání)

Jedna nová věc Strom podproblémů nad LP relaxací: v každém uzlu vyřeš LP graficky; vyjde-li proměnná necelá ($x_i = k \notin \mathbb{Z}$), větvi na $x_i \le \lfloor k \rfloor$ a $x_i \ge \lfloor k \rfloor + 1$; uzly, jejichž LP mez není lepší než dosud nejlepší celočíselné řešení $z^b$, ořež.

Pauza od rozvrhů — ale jen zdánlivá. Branch & Bound (metoda větví a mezí) je obecná technika řešení ILP a kapitola K5 ji potřebuje dvakrát: jako bounding LP relaxací pro $1|prec|\sum w_j C_j$ [L5.6b] a jako kostru Bratleyho algoritmu (B&B nad permutacemi úloh) [L5.9]. Zároveň je to samostatná zkoušková úloha: na zápočtovém testu 16. 3. 2021 padla v obou variantách (jednou minimalizace, jednou maximalizace — obě níže jako T01 a T02) a doložená je i z testu 8. 3. 2011 a zkoušky 24. 5. 2011. Teorie = slidy 13–16 přednášky o ILP.

Mez, kterou už máš: LP relaxace

Z [L0.7] Co je ILP a LP relaxace víš dvě klíčové věci: zaokrouhlení LP optima nefunguje (může být infeasible i daleko od optima) a LP relaxace dává mez na ILP optimum — horní u maximalizace, dolní u minimalizace. Celou lekci budeme stavět na příkladu ze slidu 16:

$$\begin{aligned} \max \quad & -x_1 + 2x_2 \\ & 2x_1 + x_2 \le 5 \\ & -4x_1 + 4x_2 \le 5 \\ & x_1, x_2 \ge 0, \quad x_1, x_2 \in \mathbb{Z} \end{aligned}$$

LP relaxaci vyřešíš graficky (přesně jak to chce zkouškové zadání: “use graphical method to find the solution of such LP”): nakresli obě poloroviny do mřížky, vrstevnici $-x_1 + 2x_2 = \text{konst}$ posouvej směrem růstu (doleva nahoru) — optimum padne do vrcholu, tj. průsečíku $2x_1 + x_2 = 5$ a $-4x_1 + 4x_2 = 5$: $x^{LP} = (1{,}25;\ 2{,}5)$, $z^{LP} = 3{,}75$.

Zkus sám: LP relaxace dala $z^{LP} = 3{,}75$. Co přesně teď víš o optimu ILP — a co ti k jistotě chybí?

Každé celočíselné přípustné řešení je i přípustným řešením relaxace, takže ILP optimum je nejvýš $3{,}75$ (horní mez). Jakmile najdeš jakékoli celočíselné přípustné řešení, jeho hodnota je naopak dolní mez — optimum je sevřené mezi nimi. Chybí ti systematický způsob, jak necelé LP optimum „rozbít“ na celočíselné kandidáty, aniž bys nějaké řešení ztratil — to je větvení níže.

Bonus: tady mají všechna celočíselná řešení celočíselnou hodnotu $-x_1 + 2x_2$, takže mez jde zostřit na $\lfloor 3{,}75 \rfloor = 3$. B&B na tomhle triku nestojí, ale u zkoušky se hodí jako rychlá kontrola výsledku.

Větvení: vyřízni pás bez celých bodů (slide 13)

Zkus sám: LP optimum má $x_1 = 1{,}25$. Jak rozdělíš přípustnou množinu na dvě části tak, abys neztratil žádné celočíselné řešení — a zároveň se bodu $(1{,}25;\ 2{,}5)$ zbavil?

Požaduj $x_1 \le 1$ nebo $x_1 \ge 2$. Každé celočíselné $x_1$ splňuje právě jednu z těch podmínek (mezi $1$ a $2$ žádné celé číslo neleží), takže žádného kandidáta jsme nepřišli. Vyříznutý otevřený pás $1 < x_1 < 2$ obsahuje jen necelé body — včetně toho otravného LP optima $(1{,}25;\ 2{,}5)$, které se už v žádném podproblému nevrátí. Proto „grafické řezání“: do mřížky přibude svislá (či vodorovná) čára a oblast se rozpadne na dvě menší.

Slide 13 (EN 1:1) — Branch and Bound Method

“The method is based on splitting the solution space into disjoint sets.”
“It starts by relaxing on the integrality of the variables and solves the LP problem.”
“If all variables $x_i$ are integers, the computation ends. Otherwise one variable $x_i \notin \mathbb{Z}$ is chosen and its value is assigned to $k$.”
“Then the solution space is divided into two sets — in the first one we consider $x_i \le \lfloor k \rfloor$ and in the second one $x_i \ge \lfloor k \rfloor + 1$.”
“The algorithm recursively repeats computation for both new sets till a feasible integer solution is found.”

Takhle vypadají oba podproblémy po větvení na $x_1$ — všimni si, že sjednocení zelených bodů obou obrázků je přesně množina zelených bodů z obrázku výše:

Pozn. pro binární proměnné: má-li proměnná doménu $\{0,1\}$ ([L0.8] Binární proměnná), větvení $x_i \le 0$ / $x_i \ge 1$ znamená prostě zafixuj $x_i = 0$ nebo $x_i = 1$ — strom pak větví po rozhodnutích. Stejná myšlenka „rozhodnutí = větev“ pohání Bratleyho B&B nad permutacemi úloh [L5.9].

Bounding: kdy celou větev zahodit (slidy 14–15)

Zkus sám: máš už celočíselné řešení se $z^b = 3$ (maximalizace). Rozvětvil jsi a v novém uzlu vyšla LP relaxace $z^{LP} = 2{,}5$ — necelá. Větvíš dál?

Ne — uzel zahodíš. LP relaxace je horní mez pro všechna (i celočíselná) řešení v celém podstromu toho uzlu: nic pod ním nemůže být lepší než $2{,}5 < 3 = z^b$. To je „bound“ v Branch & Bound — bez něj by metoda degenerovala na úplnou enumeraci (slide 11: „inspecting all possible solutions“).

Slide 14 (EN 1:1) — Branch and Bound Method

“By branching the algorithm creates a solution space which can be depicted as a tree.”
“A node represents the partial solution.”
“A leaf determines some (integer) solution or ‘bounded’ branch (infeasible solution or the solution which does not give a better value than the best solution found up to now).”
“As soon as the algorithm finds an integer solution, its objective function value can be used for bounding — the node is discarded whenever $z$, its (integer or real) objective function value, is worse than $z^*$, the value of the best known solution.”
“The ILP algorithm often uses an LP simplex method because after adding a new constraint it is not needed to start the algorithm again, but it allows one to continue the previous LP computation while solving the dual simplex method.” (U nás na papíře hraje roli simplexu grafická metoda.)

Slide 15 (EN 1:1) — Branch and Bound Algorithm — ILP maximization problem

function z,x = ILP(A,b,c,zᵇ,xᵇ)

  z^LP, x^LP := solution to LP problem

  is the solution to LP infeasible?
    yes → z,x := -∞, [ ]; return
    no  → continue

  if z^LP <= zᵇ ?
    yes → z,x := zᵇ, xᵇ; return
    no  → continue

  if all variables integer?
    yes → z,x := z^LP, x^LP; return
    no  →
      select some non-integer x_i
      k := x_i
      solve recursively two problems:
        the first one extended with x_i <= ⌊k⌋
          z',x' := ILP(A',b',c,zᵇ,xᵇ)
          if z' > zᵇ then zᵇ,xᵇ := z',x'
        the second one extended with x_i >= ⌊k+1⌋
          z'',x'' := ILP(A'',b'',c,zᵇ,xᵇ)
          if z'' > zᵇ then zᵇ,xᵇ := z'',x''
      z,x := zᵇ, xᵇ
      return

Čtení: $z^b, x^b$ je dosud nejlepší celočíselné řešení (incumbent), které se předává rekurzí. Uzel má tři způsoby, jak se stát listem: ① LP infeasible, ② ořezán testem $z^{LP} \le z^b$ (podstrom nemůže pomoci), ③ LP optimum vyšlo celé (kandidát — možná nový incumbent). Jinak se větví.

Nebezpečné polopravdy kolem B&B

„První nalezené celočíselné řešení = optimum.“ NE. Pseudokód končí u prvního celého řešení jen v daném uzlu; algoritmus musí dořešit/ořezat všechny větve stromu. V běhu níže je první nalezené řešení $z = 2$, optimum je $3$.
Minimalizace obrací nerovnosti! Slide 15 je psán pro maximalizaci ($z^{LP}$ = horní mez, ořež když $z^{LP} \le z^b$). U minimalizace (zkouškové T01!) je LP relaxace dolní mez a ořezáváš, když $z^{LP} \ge z^b$. Test je neostrý schválně: při rovnosti už podstrom nemůže být ostře lepší.
Větve jsou $x_i \le \lfloor k \rfloor$ a $x_i \ge \lfloor k \rfloor + 1$ — nikdy ne „$x_i < k$ / $x_i > k$“ (s reálnou hranicí nic nevyřízneš a LP optimum se vrací) ani zaokrouhlení $k$ na nejbližší celé číslo. Protože $k \notin \mathbb{Z}$, je $\lfloor k \rfloor + 1 = \lceil k \rceil$.
„LP vyšlo necelé → zaokrouhlím.“ NE — to je přesně past z [L0.7] (infeasible bod / úplně jiné optimum). Jediná legální cesta od necelého LP je větvení.

Běh na příkladu slidu 16

Proklikej celý strom (DFS, vždy nejdřív levá větev „$\le$“). U každého uzlu si představ obrázek: stejná mřížka, jen oblast seříznutá podmínkami na cestě od kořene — přesně tohle budeš u zkoušky kreslit:

Jak to vypadá u testu (přepis z wiki, test 8. 3. 2011, CZ 1:1)

„Zadane nerovnice a kriterium a vyresit tento ILP problem pomoci metody vetvi a mezi. Byla tam nakreslena mrizka, kde jsme si to meli kreslit. Takze si zopaknout jak se zakresluji nerovnice do roviny :-)“ — tedy: dostaneš mřížku a kreslíš. Stejná úloha („Větve a meze pro ILP“) je doložená i na zkoušce 24. 5. 2011 (dochovaly se jen fotky zadání).

Key takeaways — L5.5

B&B = strom podproblémů nad LP relaxací. V uzlu vyřeš LP graficky (oblast v mřížce + vrstevnice kritéria → vrchol). Celé řešení → list a kandidát na $z^b$; necelé $x_i = k$ → větvi $x_i \le \lfloor k \rfloor$ / $x_i \ge \lfloor k \rfloor + 1$ — vyříznutý pás neobsahuje žádný celý bod, takže o nic nepřijdeš.
Bounding: LP relaxace je mez pro celý podstrom ([L0.7]: horní u max, dolní u min). Uzel zahoď, když LP je nepřípustné, nebo když $z^{LP} \le z^b$ (max) resp. $z^{LP} \ge z^b$ (min) — i při rovnosti.
První celé řešení jen inicializuje $z^b$ — optimum máš potvrzené, až jsou všechny větve uzavřené (celé / nepřípustné / ořezané).
U zkoušky odevzdej: mřížku s oblastí (a čarami větvení), u každého uzlu $x^{LP}$, $z^{LP}$ a důvod uzavření listu; strom s podmínkami na hranách; nakonec $x^*, z^*$.
Dál v K5: stejný stroj pohání B&B pro $1|prec|\sum w_j C_j$ s LP boundem [L5.6b] a Bratleyho B&B nad permutacemi [L5.9].

T01 Branch and Bound Method for ILP (minimization)

FOTO checkpoint zdroj: zápočtový test 16. 3. 2021, varianta 1 (zadání EN 1:1)

Assignment (original, EN)

“Solve the following ILP instance by Branch and Bound Algorithm, where each vertex of the search tree represents one LP problem (use graphical method to find the solution of such LP).

$$\begin{aligned} \min z = \;& -x_1 + 2x_2 \\ \text{s.t.} \;& 2x_1 + x_2 \ge 4 \\ & -4x_1 + 4x_2 \ge -5 \\ & x_1, x_2 \in \mathbb{Z}_0^+ \text{”} \end{aligned}$$

a) Co je v zadání?

ILP se dvěma proměnnými — přesně formát z výkladu, ale minimalizace a omezení s „$\ge$“. Každý uzel stromu = jedno LP řešené graficky (to je v zadání explicitně). Pozor: přípustná oblast je neomezená (otevřená doprava nahoru) — minimum přesto existuje.

b) Co k tomu budeme potřebovat?

Tato lekce — větvení $\lfloor k \rfloor / \lfloor k \rfloor + 1$ a bounding (takeaways); u minimalizace ořezávej při $z^{LP} \ge z^b$!
[L0.7] Co je ILP a LP relaxace — kreslení nerovnic do roviny, LP optimum ve vrcholu.

c) Jak nad úlohou uvažovat?

Nakresli mřížku a obě hranice: $2x_1 + x_2 = 4$ (přípustná je strana nad ní) a $x_2 = x_1 - 1{,}25$ (přípustná je strana nad ní). Kritérium $z = -x_1 + 2x_2$ klesá směrem doprava dolů — kam až tě oblast pustí? Najdi vrchol, urči necelou proměnnou, větvi a u každého uzlu se ptej: je LP nepřípustné? Je $z^{LP} \ge z^b$? Je řešení celé? Nezapomeň: první celé řešení ($z^b = 3$ hned v první větvi!) není konec.

d) Úplné řešení (postup vlastní — k zadání se oficiální řešení nedochovalo; přiznáno)

Kořen (grafika): oblast je průnik polorovin nad oběma čarami v prvním kvadrantu. Vrstevnici $-x_1 + 2x_2 = \text{konst}$ tlačíme doprava dolů; oblast má jen dva vrcholy, $(0; 4)$ se $z = 8$ a průsečík obou hranic: $2x_1 + x_2 = 4$, $x_2 = x_1 - 1{,}25$ $\Rightarrow$ $3x_1 = 5{,}25$ $\Rightarrow$ $x^{LP} = (1{,}75;\ 0{,}5)$, $z^{LP} = -0{,}75$ — dolní mez. (Neomezeným směrem oblasti $z$ jen roste: pro přípustný směr $d$ platí $d_2 \ge d_1$ i $2d_1 + d_2 \ge 0$, z čehož $-d_1 + 2d_2 \ge 0$.)

Strom (větvíme na $x_1 = 1{,}75$):

① $x_1 \le 1$: na hraně $x_1 = 1$ vynucuje $2x_1 + x_2 \ge 4$ aspoň $x_2 = 2$; $z = 8 - 5x_1$ klesá s $x_1$ → optimum $x = (1; 2)$, $z = 3$ — celé! První incumbent $z^b = 3$.
② $x_1 \ge 2$: vrchol na $x_2 = x_1 - 1{,}25$: $x^{LP} = (2;\ 0{,}75)$, $z^{LP} = -0{,}5 < 3$ → pokračujeme, větvíme na $x_2 = 0{,}75$.
③ $x_2 \le 0$: $x_2 = 0$ žádá $2x_1 \ge 4 \Rightarrow x_1 \ge 2$ a zároveň $-4x_1 \ge -5 \Rightarrow x_1 \le 1{,}25$ — nepřípustné.
④ $x_2 \ge 1$: minimu pomáhá velké $x_1$; váže $-4x_1 + 4x_2 \ge -5$: $x_1 \le x_2 + 1{,}25 = 2{,}25$ → $x^{LP} = (2{,}25;\ 1)$, $z^{LP} = -0{,}25 < 3$ → větvíme na $x_1 = 2{,}25$.
⑤ $x_1 \le 2$ (s ②④): $x_1 = 2$, $x_2 = 1$: kontrola $4 + 1 = 5 \ge 4$ ✓, $-8 + 4 = -4 \ge -5$ ✓, $z = 0$ — celé a $0 < 3$ → nový incumbent $z^b = 0$, $x^b = (2; 1)$.
⑥ $x_1 \ge 3$ (s ④): vrchol $x^{LP} = (3;\ 1{,}75)$, $z^{LP} = 0{,}5 \ge 0 = z^b$ → ořezáno (minimalizace: dolní mez podstromu už není lepší než incumbent).

Všechny větve uzavřeny → optimum $x^* = (2,\ 1)$, $z^* = 0$. Rychlá kontrola sousedů: $(2,0)$ a $(3,1)$ porušují $-4x_1 + 4x_2 \ge -5$; $(3,2)$ má $z = 1$; $(1,2)$ má $z = 3$. ✓

FOTO checkpoint

Tohle je doložená zkoušková úloha (zápočtový test 2021, varianta 1). Vyřeš ji celou NA PAPÍR bez koukání do řešení: mřížka + oblast, u každého uzlu stromu grafické LP ($x^{LP}$, $z^{LP}$), podmínky větvení na hranách a důvod uzavření každého listu. Pošli mi fotku — zkontroluju ti ji a vytknu chyby (nejčastější: ořez podle špatného směru u minimalizace a ukončení po prvním celém řešení).

T02 Branch and Bound Method for ILP (maximization) zdroj: zápočtový test 16. 3. 2021, varianta 2 (zadání EN 1:1)

Assignment (original, EN)

“Solve the following ILP instance by Branch and Bound Algorithm, where each vertex of the search tree represents one LP problem (use graphical method to find the solution of such LP).

$$\begin{aligned} \max z = \;& x_1 + 2x_2 \\ \text{s.t.} \;& x_1 + x_2 \le 3 \\ & -2x_1 + 2x_2 \le 1 \\ & x_1, x_2 \in \mathbb{Z}_0^+ \text{”} \end{aligned}$$

a) Co je v zadání?

Druhá varianta téhož testu — maximalizace, malá ohraničená oblast. Tady poběží pseudokód ze slidu 15 doslova (včetně testu $z^{LP} \le z^b$).

b) Co k tomu budeme potřebovat?

Tato lekce — běh přesně podle pseudokódu (takeaways).
[L0.7] Co je ILP a LP relaxace — grafické řešení LP.

c) Jak nad úlohou uvažovat?

Oblast je čtyřúhelník s jediným necelým vrcholem — právě tím, kam tlačí kritérium. Po větvení na $x_1$ si u pravé větve všimni, že LP optimum vyjde rovnou celé. V jakém pořadí větve projdeš, rozhodne, kolik práce ušetříš — zkus si obě pořadí a sleduj, kdy zafunguje test $z^{LP} \le z^b$.

d) Úplné řešení (postup vlastní — k zadání se oficiální řešení nedochovalo; přiznáno)

Kořen (grafika): vrcholy oblasti: $(0;0)$, $(3;0)$, $(0;\ 0{,}5)$ a průsečík $x_1 + x_2 = 3$ s $-2x_1 + 2x_2 = 1$, tj. $x_2 = x_1 + 0{,}5$ $\Rightarrow$ $x^{LP} = (1{,}25;\ 1{,}75)$, $z^{LP} = 4{,}75$ — horní mez. Větvíme na $x_1 = 1{,}25$: $x_1 \le 1$ / $x_1 \ge 2$.

① $x_1 \le 1$: váže $x_2 \le x_1 + 0{,}5$ → optimum $x^{LP} = (1;\ 1{,}5)$, $z^{LP} = 4$. Necelé $x_2$ → větvíme: $x_2 \le 1$ / $x_2 \ge 2$.
- ② $x_2 \le 1$: optimum $x = (1; 1)$, $z = 3$ — celé, incumbent $z^b = 3$.
- ③ $x_2 \ge 2$: s $x_1 \le 1$ je $x_2 \le x_1 + 0{,}5 \le 1{,}5$ — nepřípustné.
④ $x_1 \ge 2$: váže $x_1 + x_2 \le 3$; $z = x_1 + 2(3 - x_1) = 6 - x_1$ klesá s $x_1$ → optimum $x^{LP} = (2;\ 1)$, $z^{LP} = 4$ — celé! A $4 > 3 = z^b$ → nový incumbent.

Strom uzavřen → optimum $x^* = (2,\ 1)$, $z^* = 4$ (LP mez kořene $4{,}75$, zaokrouhleno přes celočíselnost kritéria $\le 4$ — sedí ✓).

Pořadí větví: kdybys prošel nejdřív ④ ($z^b = 4$), uzel ① se ořeže okamžitě: $z^{LP}(①) = 4 \le 4 = z^b$ (test ze slidu 15 je neostrý — při rovnosti už podstrom nemůže být ostře lepší) a uzly ②③ vůbec nepočítáš. Výsledek je stejný, jen levněji — u zkoušky je legální libovolné pořadí, ale důvody ořezů musíš napsat.

Lekci mám hotovou