big-M: disjunkce omezení
Prerekvizity: [L0.8] Binární proměnná, [L1.1] Cílová funkce a základní omezení. Navazujeme přesně tam, kde skončil žlutý box v [L1.3] Modelování logiky.
Proč nestačí logika z L1.3
V [L1.3] jsi dělal OR mezi binárními proměnnými: „koupit budovu 5 NEBO 6“ je $x_5 + x_6 \ge 1$. Slide 37 přednášky ILP ale chce OR mezi celými nerovnostmi — pro $x_{i \in 1 \dots 4} \in \langle 0, 5 \rangle$, $x_i \in \mathbb{R}$:
$$\begin{aligned} \text{holds } & 2x_1 + 2x_2 \le 8 \\ \text{or } & 2x_3 - 2x_4 \le 2 \\ & \text{or both} \end{aligned}$$Zkus sám: proč nemůžu prostě „sečíst nerovnosti“ jako binárky a chtít součet $\ge 1$?
Nerovnost není proměnná — nemá v modelu žádnou hodnotu 0/1, kterou by šlo sčítat. Buď v soustavě JE (a pak platit MUSÍ), nebo v ní není (a pak se nevynucuje nikdy). ILP solver bere všechna omezení v soustavě jako konjunkci (AND). Potřebujeme tedy trik, kterým omezení v soustavě necháme, ale umíme ho podle hodnoty nějaké binární proměnné učinit neúčinným.
Jak „vypnout“ nerovnost: velké $M$
Zkus sám: jak upravit nerovnost $2x_1 + 2x_2 \le 8$, aby zůstala v soustavě, ale platila automaticky pro ÚPLNĚ každé $x_1, x_2 \in \langle 0,5 \rangle$?
Zvětšit pravou stranu tak, aby ji levá strana nemohla nikdy přerůst. Levá strana je nejvýš $2 \cdot 5 + 2 \cdot 5 = 20$, takže např. $2x_1 + 2x_2 \le 8 + 15 = 23$ platí vždy — omezení je formálně v soustavě, ale nikoho neomezuje. Je „vypnuté“.
Tomu přičtenému velkému kladnému číslu se říká big-M (velké $M$; slide 37 volí $M = 15$). A teď klíčový krok: přičtení uděláme podmíněně přes binární přepínač $y \in \{0,1\}$ — člen $M \cdot y$ je buď $0$ (omezení platí normálně), nebo $M$ (omezení vypnuto). Konstrukce ze slidu 37:
$$\begin{aligned} 2x_1 + 2x_2 & \le 8 + M \cdot y \\ 2x_3 - 2x_4 & \le 2 + M \cdot (1 - y) \end{aligned}$$Zkus sám: projdi obě hodnoty $y$. Která nerovnost je kdy vynucená a může se stát, že jsou vypnuté obě?
Pro $y = 0$: první nerovnost se redukuje na $2x_1 + 2x_2 \le 8$ (vynucená), druhá má vpravo $2 + M$ (vypnutá). Pro $y = 1$ přesně naopak: první vypnutá, druhá vynucená $2x_3 - 2x_4 \le 2$ (slide 38). Protože druhý přepínač je negace $(1-y)$ toho prvního (znáš z [L1.3]), vždy je vypnutá nejvýš jedna — tedy aspoň jedna platí. A „or both“? Vypnutí neznamená zákaz: i vypnutá nerovnost smí být náhodou splněna. Proto konstrukce modeluje OR, ne XOR.
Zkus sám: jak malé $M$ by v příkladu ještě stačilo? A co se stane, když dám $M$ moc malé, třeba $M = 5$?
Vypnutá nerovnost musí platit pro všechna přípustná $x$. První: levá strana $\le 20$, takže potřebuju $8 + M \ge 20$, tj. $M \ge 12$. Druhá: levá strana $2x_3 - 2x_4 \le 10$, takže $2 + M \ge 10$, tj. $M \ge 8$. Stačí tedy $M \ge 12$; slide bere s rezervou $M = 15$. S $M = 5$ by „vypnutá“ první nerovnost říkala $2x_1 + 2x_2 \le 13$ — pořád by ořezávala body jako $(5,4)$, a model by tak zakazoval řešení, která zadání povoluje. Tichá, těžko odhalitelná chyba.
Jak volit $M$ (a směr členu s $M$)$M$ musí být tak velké, aby vypnuté omezení platilo pro každou přípustnou hodnotu proměnných — spočti ho z mezí proměnných (nejhorší možná levá strana). U omezení typu $\le$ se $M \cdot y$ přičítá k pravé straně (zvětšuje strop). U omezení typu $\ge$ je to zrcadlově: $M$ se přičítá k menší (levé) straně, např. $M \cdot (1-y) + 2x_1 + x_2 \ge 10$ — vypnutí strop nezvedá, ale podlahu „podlézá“. Vždy si ověř dosazením: po vypnutí musí nerovnost platit triviálně.
Klasické použití: nepreemptivní rozvrhování
Slidy 40–42 ukazují, kde se big-M potkáš nejčastěji: non-preemptive scheduling (nepreemptivní rozvrhování) $1 | r_j, \widetilde{d_j} | C_{max}$ (Grahamova notace rozvrhování — rozklíčujeme ji až v K5, tady ber zápis jen jako jméno problému). Úlohy $T_1, \dots, T_n$ s dobami $p_i$, časy uvolnění $r_i$ a deadliny $\widetilde{d_i}$ běží na jednom procesoru; hledáme časy startu $s_i$. Na jednom procesoru běží v každém okamžiku nejvýš jedna úloha, takže pro každou dvojici $T_i, T_j$ musí platit:
- $T_i$ předchází $T_j$ — $s_j \ge s_i + p_i$,
- nebo $T_j$ předchází $T_i$ — $s_i \ge s_j + p_j$.
Pro $p_i > 0$ nemohou platit obě najednou — je to disjunkce jako vyšitá. Slide 41 zavádí $x_{ij} \in \{0,1\}$, $x_{ij} = 1$ když $T_i$ předchází $T_j$, a pro každou dvojici píše:
$$\begin{aligned} s_j + M \cdot (1 - x_{ij}) & \ge s_i + p_i \quad \text{„switched off“ when } x_{ij} = 0 \\ s_i + M \cdot x_{ij} & \ge s_j + p_j \quad \text{„switched off“ when } x_{ij} = 1 \end{aligned}$$Zkus sám: nerovnosti jsou typu $\ge$ — sedí to s pravidlem z warning boxu? Ověř dosazením $x_{ij} = 1$.
Sedí: člen s $M$ je přičtený na levé (menší) straně. Pro $x_{ij} = 1$: první nerovnost je $s_j \ge s_i + p_i$ ($T_i$ opravdu předchází $T_j$ — vynuceno), druhá je $s_i + M \ge s_j + p_j$ — pro dost velké $M$ (např. větší než nejzazší deadline) platí pro libovolné starty, je vypnutá. Pro $x_{ij} = 0$ zrcadlově. Stejný vzor jako u OR výše, jen má přepínač navíc význam: $x_{ij}$ rovnou kóduje pořadí úloh.
Co big-M dělá s přípustnou oblastí: nekonvexita
Slide 42 si vezme konkrétní čísla: $p_i = 2$, $p_j = 3$, $r_i = r_j = 0$, $\widetilde{d_i} = 10$, $\widetilde{d_j} = 11$, $M = 11$. Deadliny dávají $s_i \le 8$, $s_j \le 8$. Podívej se na řezy prostorem řešení v rovinách $x_{ij} = 1$ a $x_{ij} = 0$:
Zkus sám: vezmi bod z prvního trojúhelníku a bod z druhého a podívej se na jejich průměr. Je přípustný? Co to říká o tvaru celé přípustné oblasti?
Např. $(s_i, s_j) = (0, 2)$ (z řezu $x_{ij}=1$) a $(3, 0)$ (z řezu $x_{ij}=0$); průměr $(1.5, 1)$ neleží ani v jednom trojúhelníku — úlohy by se překrývaly. Sjednocení obou řezů tedy není konvexní: úsečka mezi dvěma přípustnými body vede přes nepřípustný pás. Slide 42: nekonvexní 2D prostor je projekce dvou řezů 3D polytopu v rovinách $x_{ij} = 0$ a $x_{ij} = 1$.
Nekonvexita je smysl, ne vadaPřípustná oblast čistého LP je vždy konvexní (průnik polorovin) — proto LP „nebo“ z principu neumí. big-M s binárním $y$ slepí dohromady dvě konvexní oblasti do nekonvexního sjednocení; nekonvexitu nese právě celočíselnost přepínače. To je důvod, proč disjunkce patří do ILP, a ne do LP.
Zobecnění: aspoň $K$ z $N$ omezení
Slide 43: máme $N$ omezení typu $f(x_1, \dots, x_n) \le b_i$ a chceme, aby platilo aspoň $K$ z nich. Dvojici už umíš — co takhle obecně?
Zkus sám: dej každému omezení vlastní přepínač $y_i$ („vypínám $i$-té“). Jaké omezení na $\sum y_i$ zajistí „aspoň $K$ platí“?
$y_i = 1$ znamená, že $i$-té omezení smí být porušeno. Když má platit aspoň $K$ z $N$, smí být vypnuto nejvýš $N - K$ omezení. Slide píše rovnost:
$$\begin{aligned} f(x_1, \dots, x_n) & \le b_i + M \cdot y_i \quad i \in 1 \dots N \\ \sum_{i=1}^{N} y_i & = N - K \end{aligned}$$Funguje i $\sum y_i \le N - K$ — vypnutí totiž porušení jen povoluje, nevynucuje, takže méně vypnutých nikdy nevadí. A poznámka ze slidu 43: pro $K = 1$, $N = 2$ stačí jediná skalární proměnná $y$ s negací $(1 - y)$ — přesně OR konstrukce ze začátku lekce.
Tohle je přesně to „překvapení“ ze zkouškového přepisu Real estate (test 8. 3. 2011, úloha T03 v [L1.3]): „vyber 2 ze 3 podmínek“ = $N = 3$, $K = 2$, tedy $y_1 + y_2 + y_3 \le 1$.
Key takeaways — L1.4- Vypnutí omezení: člen $M \cdot y$, $y \in \{0,1\}$ — u „$\le$“ přičti $M y$ k pravé straně, u „$\ge$“ k levé. $y = 1$ ⇒ omezení platí triviálně (je vypnuté), $y = 0$ ⇒ platí normálně.
- OR dvou omezení (aspoň jedno platí): přepínače $y$ a $(1-y)$ — vypnuté je vždy nejvýš jedno: $\;2x_1 + 2x_2 \le 8 + M y$, $\;2x_3 - 2x_4 \le 2 + M(1-y)$.
- Aspoň $K$ z $N$ omezení: $f(x) \le b_i + M y_i$ pro $i \in 1..N$ a $\sum y_i = N - K$ (či $\le N - K$) — nejvýš $N-K$ vypnutých.
- $M$ = dost velká konstanta: spočti z mezí proměnných tak, aby vypnuté omezení platilo VŽDY. Moc malé $M$ tiše zakazuje povolená řešení.
- big-M dělá přípustný prostor nekonvexní (sjednocení oblastí) — proto „nebo“ neumí LP a potřebuješ binární přepínač, tj. ILP.
- Kanonický příklad: nepreemptivní rozvrhování — pro dvojici úloh $s_j + M(1 - x_{ij}) \ge s_i + p_i$ a $s_i + M x_{ij} \ge s_j + p_j$.
“To model OR relation between inequalities, draw the 2D solution space $(x_1, x_2)$ of the system of inequalities with big M:
$$\begin{aligned} 2x_1 + x_2 & \le 5 + M \cdot y \\ 2x_1 - x_2 & \le 2 + M \cdot (1 - y) \\ y & \in \{0, 1\} \end{aligned}$$Example where OR overlaps with XOR: In 2D draw the solution space $(x_1, x_2)$ of the system of inequalities. Note that the equations correspond to parallel lines. Is it possible to find $x_1, x_2$ such that both original inequalities $2x_1 + x_2 \le 5$ and $2x_1 + x_2 \ge 10$ are valid simultaneously?
$$\begin{aligned} 2x_1 + x_2 & \le 5 + M \cdot y \\ M \cdot (1 - y) + 2x_1 + x_2 & \ge 10 \\ y & \in \{0, 1\} \end{aligned}$$a) Co je v zadání?
Dvě malé soustavy s big-M a přepínačem $y$; u obou máš nakreslit, jak vypadá množina přípustných $(x_1, x_2)$ (přes obě hodnoty $y$). U druhé navíc odpovědět, zda mohou obě původní nerovnosti platit zároveň — tedy jestli je to OR, nebo fakticky XOR.
b) Co k tomu budeme potřebovat?
- Tato lekce — čtení konstrukce $M y$ / $M(1-y)$, směr členu s $M$ u $\le$ vs. $\ge$.
- [L0.8] Binární proměnná — negace $(1-y)$.
c) Jak nad úlohou uvažovat?
Pro $y = 0$ a $y = 1$ zvlášť si napiš, co ze soustavy zbyde (vypnutá omezení škrtni), a nakresli příslušnou polorovinu. Celková přípustná množina je sjednocení obou obrázků. U druhé soustavy: obě hraniční přímky mají stejný směrový vektor — co leží mezi $2x_1 + x_2 = 5$ a $2x_1 + x_2 = 10$?
d) Úplné řešení
Soustava 1: $y = 0$ vynucuje $2x_1 + x_2 \le 5$ (druhé omezení vypnuté), $y = 1$ vynucuje $2x_1 - x_2 \le 2$ (první vypnuté). Přípustný prostor = sjednocení dvou polorovin (zde kresleno v okně $0..5 \times 0..5$):
Sjednocení je nekonvexní: např. $(2, 0)$ je přípustné přes $y=0$, $(3, 5)$ přes $y=1$, ale jejich průměr $(2.5, 2.5)$ porušuje obě původní nerovnosti ($7.5 > 5$ i $2.5 > 2$). Body jako $(0, 0)$ splňují obě nerovnosti najednou — OR, ne XOR.
Soustava 2: $y = 0$ vynucuje $2x_1 + x_2 \le 5$, $y = 1$ vynucuje $2x_1 + x_2 \ge 10$:
Odpověď: Ne — $2x_1 + x_2 \le 5$ a $2x_1 + x_2 \ge 10$ zároveň by znamenalo $10 \le 2x_1 + x_2 \le 5$, spor. Hraniční přímky jsou rovnoběžky a pás mezi nimi je prázdná zóna. Konstrukce je formálně OR, ale protože „obě najednou“ je nemožné, splývá tady OR s XOR — vždy platí právě jedna.
“$1 | r_j, \widetilde{d_j} | C_{max}$ … NP-hard problem. Instance: A set of non-preemptive tasks $\mathcal{T} = \{T_1, \dots, T_i, \dots, T_n\}$ with release date $r$ and deadline $\widetilde{d}$ should be executed on one processor. The processing times are given by vector $p$. Goal: Find a feasible schedule represented by start times $s$ that minimizes completion time $C_{max} = \max_{i \in \langle 1, n \rangle} s_i + p_i$ or decide that it does not exist.
Since at the given moment, at most, one task is running on a given resource, therefore, for all task pairs $T_i, T_j$ it must hold: 1. $T_i$ precedes $T_j$ ($s_j \ge s_i + p_i$) 2. or $T_j$ precedes $T_i$ ($s_i \ge s_j + p_j$). […] We need to formulate that at least one inequality holds.”
a) Co je v zadání?
Rozvrhování na jednom stroji: každá úloha má start $s_i$ (spojitá proměnná), trvání $p_i$, nejdřívější start $r_i$ a deadline $\widetilde{d_i}$. Jádro úlohy: pro každou dvojici úloh zapsat „jedna předchází druhou“ — disjunkci dvou nerovností, které (pro $p > 0$) nemohou platit obě.
b) Co k tomu budeme potřebovat?
- Tato lekce — big-M přepínač pro $\ge$ nerovnosti.
- [L0.8] Binární proměnná — význam $x_{ij}$ a negace $(1 - x_{ij})$.
c) Jak nad úlohou uvažovat?
Co přesně má kódovat přepínač? Tady se nabízí dát mu rovnou význam: $x_{ij} = 1$ ⟺ „$T_i$ předchází $T_j$“. Kterou z obou nerovností má $x_{ij} = 1$ vynucovat a kterou vypínat? A nezapomeň na omezení, která disjunkci nepotřebují: release date a deadline každé úlohy.
d) Úplné řešení
Pro každou dvojici zaveď $x_{ij} \in \{0,1\}$, $x_{ij} = 1$ když $T_i$ předchází $T_j$ (slide 41):
$$\begin{aligned} s_j + M \cdot (1 - x_{ij}) & \ge s_i + p_i \quad \text{„switched off“ when } x_{ij} = 0 \\ s_i + M \cdot x_{ij} & \ge s_j + p_j \quad \text{„switched off“ when } x_{ij} = 1 \end{aligned}$$Celá soustava omezení (slide 42; dvojice stačí brát jednou, $j < i$):
$$\begin{aligned} s_i & \ge r_i & i \in 1..n \quad & \text{release date} \\ \widetilde{d_i} & \ge s_i + p_i & i \in 1..n \quad & \text{deadline} \\ s_j + M \cdot (1 - x_{ij}) & \ge s_i + p_i & i \in 1..n,\ j < i \quad & T_i \text{ precedes } T_j \\ s_i + M \cdot x_{ij} & \ge s_j + p_j & i \in 1..n,\ j < i \quad & T_j \text{ precedes } T_i \end{aligned}$$Volba $M$: dost velké vzhledem k horizontu rozvrhu — na slidu 42 ($\widetilde{d_j} = 11$) je $M = 11$; obecně stačí $M \ge \max_i \widetilde{d_i}$, protože pak $s_i + M$ přeroste jakékoli $s_j + p_j \le \widetilde{d_j}$. Kritérium $C_{max} = \max_i (s_i + p_i)$ se pak minimalizuje pomocnou proměnnou $C_{max} \ge s_i + p_i \;\forall i$ — modelování maxima rozebere [L1.8].
“We have $N$ constraints and we need at least $K$ of them to hold. Constraints are of type:
$$f(x_1, x_2, \dots, x_n) \le b_1, \quad f(x_1, x_2, \dots, x_n) \le b_2, \quad \dots, \quad f(x_1, x_2, \dots, x_n) \le b_N.$$How can this be modeled in ILP?”
a) Co je v zadání?
Zobecnění OR z této lekce: místo „aspoň 1 ze 2“ chceme „aspoň $K$ z $N$“ nerovností. Hledá se obecná konstrukce s pomocnými binárkami.
b) Co k tomu budeme potřebovat?
- Tato lekce — vypínání omezení přes $M y_i$.
- [L0.8] Binární proměnná — $\sum y_i$ = počet zapnutých jedniček.
c) Jak nad úlohou uvažovat?
Každé omezení dostane vlastní přepínač $y_i$ ($y_i = 1$ = „$i$-té omezení smí být porušeno“). Kolik omezení smí být nejvýš vypnuto, když jich aspoň $K$ má platit? A proč u dvojice (OR) stačila jen jedna proměnná $y$?
d) Úplné řešení
Zaveď $N$ proměnných $y_{i \in 1 \dots N} \in \{0,1\}$ (slide 43):
$$\begin{aligned} f(x_1, x_2, \dots, x_n) & \le b_i + M \cdot y_i \quad i \in 1 \dots N \\ \sum_{i=1}^{N} y_i & = N - K \end{aligned}$$Vypnutých je přesně $N - K$ omezení, takže zbylých $K$ platí. Funguje i $\sum y_i \le N - K$ — $y_i = 1$ porušení jen povoluje, nevynucuje. Poznámka ze slidu 43: pro $K = 1$ a $N = 2$ lze použít jedinou skalární proměnnou $y$ a její negaci $(1 - y)$ — viz OR konstrukce výše. A zkoušková aplikace „aspoň 2 ze 3 podmínek“ (Real estate 2011, [L1.3] T03): $y_1 + y_2 + y_3 \le 1$.