Binární proměnná
Prerekvizity: [L0.7] Co je ILP a LP relaxace.
Rozhodnutí jako číslo
Nejdůležitější modelovací trik celého kurzu: binary variable (binární proměnná) $x_i \in \{0,1\}$ kóduje rozhodnutí ano/ne. Slidy (02_ILP, slide 19) to říkají přímo: „flexible — e.g. binary variable can be used to model the decision (logical expression)“. Konvence čtení:
$$x_i = 1 \iff \text{„věc } i \text{ je vybrána / aktivní“}, \qquad x_i = 0 \iff \text{„není“}.$$Ukázka přímo ze slidu 5 (2-Partition): „$x_i = 1$ iff $i \in S$“ — binární proměnná kóduje, jestli bankovka $i$ patří do podmnožiny $S$. Každá podmnožina $S \subseteq \{1,\dots,n\}$ odpovídá právě jednomu vektoru nul a jedniček a naopak.
Zkus sám: co spočítá výraz $\sum_{i=1}^{n} x_i$? A co $\sum_{i=1}^{n} p_i x_i$, když $p_i$ je hodnota věci $i$?
$\sum_i x_i$ = počet vybraných věcí (vybrané přispějí jedničkou, nevybrané nulou). $\sum_i p_i x_i$ = celková hodnota vybraných věcí — dosazením $x_i \in \{0,1\}$ se ze sumy „vyškrtnou“ právě nevybrané členy. Tohle je důvod, proč binární proměnné fungují: výběr podmnožiny se stane lineárním výrazem.
Počítací omezení
Jakmile $\sum_i x_i$ počítá vybrané, omezení na počet jsou lineární nerovnosti:
- $\sum_i x_i = 1$ — „vyber právě jednu“,
- $\sum_i x_i \le k$ — „vyber nejvýše $k$“,
- $\sum_i x_i \ge k$ — „vyber aspoň $k$“.
A negace zadarmo: když $x_i$ znamená „vybráno“, pak $1 - x_i$ znamená „nevybráno“. Slide 7 (ILP1c, optimalizační verze 2-Partition) přesně takhle zapisuje druhou polovinu rozdělení: hodnota nevybraných je $\sum_i (1 - x_i)\, p_i$.
Zkus sám: kolik přípustných řešení má omezení $x_1 + x_2 \le 1$, $x_1, x_2 \in \{0,1\}$? A co to znamená slovně?
Tři: $(0,0)$, $(1,0)$, $(0,1)$ — vyloučí se jen $(1,1)$. Slovně: „nevyber obě zároveň“ (nejvýš jednu ze dvou). Tahle drobnost je základ modelování logiky (konflikty, XOR, implikace) — systematicky v [L1.3] Modelování logiky: implikace, XOR, AND (kapitola K1).
Binární vs. spojitá: vidíš ten rozdíl?
Slide 6 ukazuje, co se stane, když binárnost povolíš: pro bankovky $p = [100, 50, 50, 50, 20, 20, 10, 10]$ frakční varianta ($x_i \in \langle 0,1\rangle$) připustí $x = [0, 0, 0.9, 1, 1, 1, 1, 1]$ — bankovku smíš „rozstřihnout“. S binárními proměnnými to nejde — a přesně tahle změna dělá z polynomiální úlohy NP-úplnou (srov. [L0.7]: LP vs. ILP). Detailně si to osaháš v úloze T02.
Key takeaways — L0.8- $x_i \in \{0,1\}$: $x_i = 1 \iff$ „věc $i$ je vybrána / aktivní“, $x_i = 0 \iff$ „není“; negace = $1 - x_i$.
- $\sum_i x_i$ = počet vybraných; $\sum_i p_i x_i$ = celková hodnota vybraných (výběr podmnožiny jako lineární výraz).
- Počítací omezení: $\sum x_i = 1$ „právě jedna“, $\sum x_i \le k$ „nejvýše $k$“, $\sum x_i \ge k$ „aspoň $k$“.
- Záměna $x_i \in \{0,1\}$ za $x_i \in \langle 0,1 \rangle$ je LP relaxace výběru — povolí „rozstřižené“ věci a může být přípustná, i když binární řešení neexistuje.
“2-Partition Problem. Instance: Number of banknotes $n \in \mathbb{Z}^+$ and their values $p_1, \dots, p_n$, where $p_{i \in 1..n} \in \mathbb{Z}^+$. Decision: Is there a subset $S \subseteq \{1, \dots, n\}$ such that $\sum_{i \in S} p_i = \sum_{i \notin S} p_i$? … $x_i = 1$ iff $i \in S$.”
$$\begin{aligned} \min \quad & 0 \\ \text{subject to:} \quad & \textstyle\sum_{i \in 1..n} x_i \ast p_i = 0.5 \ast \sum_{i \in 1..n} p_i \\ \text{parameters:} \quad & n \in \mathbb{Z}^+,\ p_{i \in 1..n} \in \mathbb{Z}^+ \\ \text{variables:} \quad & x_{i \in 1..n} \in \{0,1\} \end{aligned}$$Explain the role of the binary variables: why does the single constraint encode $\sum_{i \in S} p_i = \sum_{i \notin S} p_i$, and why is the objective $\min 0$?
a) Co je v zadání?
Rozdělení bankovek na dvě stejně hodnotné hromádky zapsané jako ILP. Máš vysvětlit, co dělají binární proměnné, proč stačí jediné omezení a proč je cílová funkce nulová.
b) Co k tomu budeme potřebovat?
- Tato lekce — čtení $x_i = 1 \iff i \in S$, suma $\sum p_i x_i$.
- [L0.7] Co je ILP a LP relaxace — co je ILP a rozhodovací úloha.
c) Jak nad úlohou uvažovat?
Rozepiš $\sum_{i \in S} p_i$ pomocí $x_i$. Pak si všimni: když vybraná polovina má hodnotu přesně $0.5 \sum p_i$, kolik nutně zbývá na nevybranou? A k cíli: hledáme nejlepší řešení, nebo nějaké?
d) Úplné řešení
Role $x_i$: $x_i = 1 \iff i \in S$ — vektor $(x_1,\dots,x_n)$ jednoznačně kóduje podmnožinu $S$. Hodnota vybraných je pak lineární výraz $\sum_i p_i x_i = \sum_{i \in S} p_i$.
Proč stačí jedno omezení: označ $P = \sum_i p_i$ (konstanta). Podmínka „obě hromádky stejné“ je $\sum_{i \in S} p_i = \sum_{i \notin S} p_i = P - \sum_{i \in S} p_i$, což je ekvivalentní $2\sum_{i \in S} p_i = P$, tedy $\sum_i p_i x_i = 0.5\, P$ — přesně omezení modelu. Druhá hromádka je určená automaticky ($1 - x_i$).
Proč $\min 0$: je to rozhodovací úloha — nezajímá nás žádná kvalita řešení, jen jestli existuje přípustné $x$. Konstantní cíl znamená „najdi libovolné přípustné řešení“; solver odpoví buď řešením (= rozdělení existuje), nebo infeasible (= neexistuje). Slide dodává, že je to jeden z „nejlehčích“ NP-úplných problémů.
“We allow division of banknotes such that $x_{i \in 1..n} \in \langle 0, 1 \rangle$. … For example: $p = [100, 50, 50, 50, 20, 20, 10, 10]$ the fractional variant allows for $x = [0, 0, 0.9, 1, 1, 1, 1, 1]$ and thus divides the banknotes into equal halves $100 + 50 + 5 = 45 + 50 + 20 + 20 + 10 + 10$, but this instance does not have a non-fractional solution. For some non-fractional instances we can easily find that they cannot be partitioned (e.g. when the sum of all values divided by the greatest common divisor is not an even number).” Verify the fractional solution and prove that no binary solution exists for this instance.
a) Co je v zadání?
Stejné bankovky, ale proměnné smí být zlomky (bankovku lze rozdělit). Máš ověřit, že uvedené frakční $x$ opravdu dělí hodnotu napůl, a dokázat, že binární (nerozstřižené) rozdělení pro tuto instanci neexistuje.
b) Co k tomu budeme potřebovat?
- Tato lekce — čtení binárního výběru, $\sum p_i x_i$.
- [L0.7] Co je ILP a LP relaxace — frakční varianta = LP relaxace.
c) Jak nad úlohou uvažovat?
Spočítej $\sum_i p_i$ a polovinu. Pro ověření dosaď $x$ do $\sum_i p_i x_i$. Pro neexistenci binárního řešení: jakým číslem jsou dělitelné všechny $p_i$ — a je polovina součtu taky jeho násobkem? (Slide napovídá přes největší společný dělitel.)
d) Úplné řešení
Ověření: $\sum_i p_i = 100+50+50+50+20+20+10+10 = 310$, polovina $= 155$. Dosazení: $\sum_i p_i x_i = 0 + 0 + 0.9 \cdot 50 + 50 + 20 + 20 + 10 + 10 = 45 + 110 = 155$ ✓. Nevybraný zbytek: $100 + 50 + 0.1 \cdot 50 = 155$ ✓ — přesně rozdělení „$100 + 50 + 5 = 45 + 50 + 20 + 20 + 10 + 10$“ ze slidu.
Neexistence binárního řešení: všechna $p_i$ jsou násobky $\gcd = 10$, takže hodnota jakékoli podmnožiny $\sum_{i \in S} p_i$ je násobek 10. Ale požadovaná polovina $155$ násobek 10 není — žádné binární $x$ omezení nesplní. (Slidové kritérium: $310 / \gcd = 310/10 = 31$ není sudé číslo → instance nejde rozdělit.) Frakční varianta (LP relaxace, konvexní množina) tedy řešení má, binární ILP ne — další ilustrace, že relaxace může být přípustná tam, kde celočíselný problém přípustný není.