Modelování logiky: implikace, XOR, AND
Prerekvizity: [L0.8] Binární proměnná; navazujeme na Real Estate model z [L1.1].
Kde se v ILP bere logika
Vrať se k Real Estate Investment z [L1.1]: 6 budov, binární $x_i$ („koupit budovu $i$?“), rozpočet 14 mil. Slide 30 přidává novou větu zadání: „if building 1 is selected, then building 2 is selected too“ — tedy logickou implikaci (implication) $x_1 \Rightarrow x_2$. Jenže ILP nezná „jestliže–pak“; umí jen lineární (ne)rovnosti. Celá tahle lekce je o jednom triku: logickou formuli nad binárkami přepiš na lineární omezení, které propustí přesně ty samé kombinace nul a jedniček.
Začni pravdivostní tabulkou implikace (slide 30):
| $x_1$ | $x_2$ | $x_1 \Rightarrow x_2$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Zkus sám: kolik kombinací $(x_1, x_2)$ implikace zakazuje a kterou? Co z toho plyne pro hledané omezení?
Jedinou: $(x_1, x_2) = (1, 0)$ — „koupil jsem 1, ale ne 2“. Ostatní tři řádky jsou povolené. Hledám tedy lineární nerovnost, která ze čtyř rohů čtverce $\{0,1\}^2$ vyřízne přesně bod $(1,0)$ a zbylé tři nechá.
Zkus sám: najdi tu nerovnost. (Nápověda: porovnej $x_1$ a $x_2$ ve třech povolených řádcích a v zakázaném.)
V povolených řádcích je vždy $x_2 \ge x_1$ ($0\ge0$, $1\ge0$, $1\ge1$); v zakázaném $(1,0)$ je $0 \ge 1$ nepravda. Takže:
$$x_1 \Rightarrow x_2 \quad\equiv\quad x_2 \ge x_1.$$Čtení nahlas: „$x_2$ je aspoň tak velké jako $x_1$“ — když se zapne $x_1$, musí se zapnout i $x_2$; když je $x_1 = 0$, na $x_2$ se nic nevynucuje.
Geometricky (slide 30): ze čtverce $0..1 \times 0..1$ zůstane trojúhelník — bod $(1,0)$ je odříznutý:
Model ze slidu 30 (build 3) pak jen přidá řádek do „subject to“:
$$\begin{aligned} \max z = \;& 16x_1 + 22x_2 + 12x_3 + 8x_4 + 11x_5 + 19x_6 \\ \text{s.t.} \;& 5x_1 + 7x_2 + 4x_3 + 3x_4 + 4x_5 + 6x_6 \le 14 \\ & x_2 \ge x_1 \\ & x_{i \in 1 \cdots 6} \in \{0, 1\} \end{aligned}$$Negace: $\overline{x}$ je prostě $1 - x$
Slide 30 (další build) přidává: „If building 3 is selected, then building 4 is not selected“ — $x_3 \Rightarrow \overline{x_4}$. Nový prvek je negace (negation): „budova 4 NENÍ vybrána“. Žádnou novou proměnnou nepotřebuješ — když $x \in \{0,1\}$, pak výraz $(1 - x)$ je přesně jeho opak: $1-0 = 1$, $1-1 = 0$.
Zkus sám: dosaď negaci do hotového vzorce implikace $x_1 \Rightarrow x_2 \equiv x_2 \ge x_1$ a uprav. Co vyjde pro $x_3 \Rightarrow \overline{x_4}$?
Hlava implikace je $\overline{x_4} = 1 - x_4$, takže $1 - x_4 \ge x_3$, tedy:
$$x_3 + x_4 \le 1.$$Kontrola proti pravdivostní tabulce: zakázaný je jediný řádek $(x_3, x_4) = (1,1)$ — a opravdu, $1 + 1 = 2 \not\le 1$, zatímco $(0,0), (0,1), (1,0)$ projdou. Čtení: „dohromady nejvýš jedna z obou budov“ — vzájemné vyloučení (NAND / at most one). Z [L0.8] to znáš jako $\sum x_i \le 1$ pro dvojici.
XOR: právě jedna z obou
Slide 31: „either building 5 is chosen or building 6 is chosen, but not both“ — $x_5$ XOR $x_6$ (exclusive or, vylučovací nebo). Tabulka:
| $x_5$ | $x_6$ | $x_5$ XOR $x_6$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Zkus sám: tentokrát jsou zakázané řádky dva — $(0,0)$ i $(1,1)$. Jaké omezení je vyřízne oba najednou?
$(1,1)$ zakáže $x_5 + x_6 \le 1$ (to už umíš); $(0,0)$ zakáže $x_5 + x_6 \ge 1$ („aspoň jedna“ — opět počítání z [L0.8]). Dohromady:
$$x_5 + x_6 = 1.$$„Právě jedna z obou.“ Geometricky zbude z čtverce jen úsečka — diagonála z $(0,1)$ do $(1,0)$.
Mimochodem — obyčejné OR („aspoň jedna z obou, klidně obě“) je jen volnější polovina téhož: $x_5 + x_6 \ge 1$.
Univerzální recept: zakaž řádky pravdivostní tabulky
Všechna tři odvození měla stejný rytmus: najdi v tabulce řádky s hodnotou 0 a každý vyřízni jedním omezením. To funguje vždy (postup ze studentské wiki ilpbin, tam přes tzv. maxtermy):
Recept „zakázaný řádek“Pro každý zakázaný řádek pravdivostní tabulky (kombinaci hodnot $v_1, \ldots, v_k$) přidej jedno omezení: sečti přes všechny zúčastněné proměnné literál, který v tom řádku vyšel 0 — tedy $x_i$, pokud $v_i = 0$, a $(1 - x_i)$, pokud $v_i = 1$ — a chtěj
$$\sum_{i:\, v_i = 0} x_i \;+\; \sum_{i:\, v_i = 1} (1 - x_i) \;\ge\; 1.$$Levá strana je 0 právě v zakázané kombinaci a $\ge 1$ ve všech ostatních — omezení tedy vyřízne přesně ten jeden řádek. Jedna formule = tolik omezení, kolik má zakázaných řádků.
Zkus sám: ověř recept na implikaci $x_1 \Rightarrow x_2$ (zakázaný řádek $x_1 = 1, x_2 = 0$). Vyjde známé $x_2 \ge x_1$?
$v_1 = 1$ dá literál $(1 - x_1)$, $v_2 = 0$ dá literál $x_2$:
$$(1 - x_1) + x_2 \ge 1 \quad\Longleftrightarrow\quad x_2 \ge x_1. \;\checkmark$$A XOR: řádek $(0,0)$ dá $x_5 + x_6 \ge 1$, řádek $(1,1)$ dá $(1-x_5) + (1-x_6) \ge 1 \Leftrightarrow x_5 + x_6 \le 1$ — dohromady $x_5 + x_6 = 1$. ✓
AND v předpokladu: $(x_1 \text{ AND } x_2) \Rightarrow x_3$
Domácí úkol ze slidu 32 obsahuje i tříproměnnou formuli: „if estates 1 and 2 have been chosen, then estate 3 must be chosen too“. Tady už geometrická úvaha ve čtverci nestačí (krychle $\{0,1\}^3$ má 8 rohů) — ale recept funguje stejně.
Zkus sám: který jediný řádek tabulky $(x_1, x_2, x_3)$ formule zakazuje? Aplikuj recept a uprav výsledek.
Implikace selže, jen když platí předpoklad a neplatí hlava: $(x_1, x_2, x_3) = (1, 1, 0)$. Recept: $v_1 = 1 \to (1-x_1)$, $v_2 = 1 \to (1-x_2)$, $v_3 = 0 \to x_3$:
$$(1 - x_1) + (1 - x_2) + x_3 \ge 1 \quad\Longleftrightarrow\quad x_3 \ge x_1 + x_2 - 1.$$Kontrola čtením: když $x_1 = x_2 = 1$, pravá strana je $1$ → vynutí $x_3 = 1$. Když je aspoň jedna z nich 0, pravá strana je $\le 0$ → na $x_3$ se nic nevynucuje. Přesně implikace.
Pozor: implikace ⇒ není ekvivalence ⇔Omezení $x_3 \ge x_1 + x_2 - 1$ modeluje JEN směr „když 1 a 2, tak i 3“. Nezakazuje koupit budovu 3 samotnou ($x_3 = 1$ při $x_1 = 0$) — a to je správně, zadání nic takového nechce. Kdyby zadání chtělo ekvivalenci „$x_3 = 1$ právě když $x_1 = x_2 = 1$“ (tj. $x_3 = x_1 \wedge x_2$), musíš zakázat i řádky, kde $x_3 = 1$ a předpoklad neplatí: přidej $x_3 \le x_1$ a $x_3 \le x_2$. Vždy si v tabulce ověř, KTERÉ řádky tvoje věta zadání opravdu zakazuje — modelovat víc, než zadání říká, je stejná chyba jako modelovat míň.
Počítání vybraných: „aspoň 2 ze 3“ a podobné
Část logických vět se obejde i bez tabulky — jsou to jen počty. Z [L0.8] víš, že $\sum_i x_i$ = počet vybraných věcí. Takže:
- „aspoň dvě z budov $A, B, C$“: $x_A + x_B + x_C \ge 2$,
- „právě 3 budovy celkem“: $\sum_i x_i = 3$,
- „právě 2 budovy NEkoupené“: $\sum_i (1 - x_i) = 2$, po úpravě $\sum_i x_i = n - 2$,
- „budova 1 povinně, budova 2 zakázaná“: $x_1 = 1$, $x_2 = 0$ (fixace proměnné je taky lineární omezení).
Rozliš: logika nad PROMĚNNÝMI vs. nad OMEZENÍMIVše v této lekci spojuje binární proměnné — „vyber aspoň 2 ze 3 budov“. U zkoušky (např. Real estate test 8. 3. 2011) ale padá i „musí platit aspoň 2 ze 3 podmínek“ (celých nerovností!). To čistou logikou nezvládneš — nerovnost nejde „sečíst jako binárku“. Potřebuješ velkou konstantu $M$ a pomocné přepínače $y_i$ — přesně to je [L1.4] big-M: disjunkce omezení.
Key takeaways — L1.3- Implikace $x \Rightarrow y$: $\;y \ge x$. Negace $\overline{x}$: dosaď $(1 - x)$; takže $x \Rightarrow \overline{y}$ je $x + y \le 1$ (nejvýš jedna).
- XOR (právě jedna z $A, B$): $x_A + x_B = 1$. Obyčejné OR (aspoň jedna): $x_A + x_B \ge 1$.
- AND v předpokladu — „$A$ a $B$ ⟹ $C$“: $x_C \ge x_A + x_B - 1$. Je to jen implikace, ne ekvivalence ($C$ smí být 1 i samo o sobě).
- Univerzální recept: každý zakázaný řádek pravdivostní tabulky → jedno omezení $\sum_{v_i=0} x_i + \sum_{v_i=1}(1 - x_i) \ge 1$.
- Počty: „aspoň 2 ze 3“ = $x_A + x_B + x_C \ge 2$; „právě $k$“ = $\sum x_i = k$; povinná/zakázaná volba = fixace $x_i = 1$ / $x_i = 0$.
- Logika mezi celými omezeními („platí aspoň jedna z nerovností“) se takhle udělat nedá → big-M, [L1.4].
“We consider 6 buildings for investment. (… model from slide 29: maximize income, budget 14 mil CZK, $x_i \in \{0,1\}$ …) Another constraint:
- if building 1 is selected, then building 2 is selected too $\;(x_1 \Rightarrow x_2)$;
- if building 3 is selected, then building 4 is not selected $\;(x_3 \Rightarrow \overline{x_4})$;
- either building 5 is chosen or building 6 is chosen, but not both $\;(x_5 \text{ XOR } x_6)$.”
Extend the ILP model from slide 29 with these three logical constraints.
a) Co je v zadání?
Hotový základní model z [L1.1] (úloha T01) a tři logické věty navíc: implikace, implikace s negací a XOR. Úkol je přepsat každou na jedno lineární omezení.
b) Co k tomu budeme potřebovat?
- Tato lekce — vzorce $y \ge x$, $x + y \le 1$, $x + y = 1$ (resp. recept „zakázaný řádek“).
- [L1.1] Cílová funkce a základní omezení — základní model, do kterého omezení přidáváš.
- [L0.8] Binární proměnná — čtení součtů binárek.
c) Jak nad úlohou uvažovat?
Pro každou větu si napiš (klidně jen v hlavě) pravdivostní tabulku a označ zakázané řádky. Implikace zakazuje jediný řádek — který? Negaci nahraď $(1-x)$ a použij už hotový vzorec implikace. XOR zakazuje dva řádky — jaká dvě omezení z toho plynou a jak se slijí do jednoho?
d) Úplné řešení
Tři nová omezení (slidy 30–31):
- $x_1 \Rightarrow x_2$: zakázaný řádek $(1,0)$ → $x_2 \ge x_1$.
- $x_3 \Rightarrow \overline{x_4}$: hlava $\overline{x_4} = 1 - x_4$, takže $1 - x_4 \ge x_3$ → $x_3 + x_4 \le 1$.
- $x_5$ XOR $x_6$: zakázané řádky $(0,0)$ a $(1,1)$ → $x_5 + x_6 \ge 1$ a $x_5 + x_6 \le 1$, dohromady $x_5 + x_6 = 1$.
Celý model se všemi třemi formulemi najednou:
$$\begin{aligned} \max z = \;& 16x_1 + 22x_2 + 12x_3 + 8x_4 + 11x_5 + 19x_6 \\ \text{s.t.} \;& 5x_1 + 7x_2 + 4x_3 + 3x_4 + 4x_5 + 6x_6 \le 14 \\ & x_2 \ge x_1 \\ & x_3 + x_4 \le 1 \\ & x_5 + x_6 = 1 \\ & x_{i \in 1 \cdots 6} \in \{0, 1\} \end{aligned}$$Kontrola: optimum základního modelu $x = (1,0,0,1,0,1)$ z [L1.1] teď není přípustné ($x_1 = 1$, ale $x_2 = 0$ porušuje $x_2 \ge x_1$) — logická omezení opravdu „kousla“. Nové optimum je nižší: např. $x = (0,1,0,0,0,1)$ s cenou $7 + 6 = 13 \le 14$ a ziskem $z = 22 + 19 = 41 < 43$ — za logiku se platí ziskem.
“Formulate:
- building 1 must be chosen but building 2 can not
- at least 3 estates must be chosen
- exactly 3 estates must be chosen
- if estates 1 and 2 have been chosen, then estate 3 must be chosen too $(x_1 \text{ AND } x_2) \Rightarrow x_3$
- exactly 2 estates can not be chosen”
a) Co je v zadání?
Pět samostatných slovních podmínek nad šesti binárkami $x_1, \ldots, x_6$ Real Estate modelu; každou máš vyjádřit lineárním omezením (nebo dvojicí omezení).
b) Co k tomu budeme potřebovat?
- Tato lekce — fixace proměnných, počty vybraných, recept „zakázaný řádek“ pro AND-implikaci.
- [L0.8] Binární proměnná — $\sum x_i$ = počet vybraných, negace $(1-x_i)$.
c) Jak nad úlohou uvažovat?
Roztřiď podmínky: které jsou jen počty (sčítání binárek s $\ge$ / $=$), které jsou fixace jediné proměnné a která jediná potřebuje pravdivostní tabulku? U „exactly 2 … can not be chosen“ si dej pozor, CO se počítá — vybrané, nebo nevybrané budovy?
d) Úplné řešení
- building 1 must be chosen but building 2 can not: $x_1 = 1$ a $x_2 = 0$ (dvě fixace).
- at least 3 estates must be chosen: $\sum_{i=1}^{6} x_i \ge 3$.
- exactly 3 estates must be chosen: $\sum_{i=1}^{6} x_i = 3$.
- $(x_1 \text{ AND } x_2) \Rightarrow x_3$: jediný zakázaný řádek $(1,1,0)$ → $(1-x_1) + (1-x_2) + x_3 \ge 1$, tedy $$x_3 \ge x_1 + x_2 - 1.$$
- exactly 2 estates can not be chosen: počítám NEvybrané: $\sum_{i=1}^{6} (1 - x_i) = 2$, po úpravě $\sum_{i=1}^{6} x_i = 4$.
Sanity check AND-implikace: $x_1 = x_2 = 1$ → $x_3 \ge 1$ → vynuceno; $x_1 = 1, x_2 = 0$ → $x_3 \ge 0$ → volné. ✓ (A pozor — je to jen ⇒, ne ⇔; viz červený box v lekci.)
„Maximalizace zisku z najmu pro nakup nemovitosti - velmi podobny priklad jako ve slidech. Meli jsme to formulovat jako ILP. Nekolik omezeni navic jako XOR, pokud plati A a zaroven B tak taky C atd. Prekvapilo ze jsme meli vybrat 2 ze 3 podminek - nutno resit pomoci velkeho celeho cisla M a pomocne promenne y_1, y_2 a y_3 (y_1+y_2+y_3≤1)“
Pozn.: jde o studentský přepis, ne doslovné znění zadání — proto je výjimečně česky. Procvič na něm: formuluj pro Real Estate model omezení (i) „budova $A$ XOR budova $B$“, (ii) „pokud $A$ a zároveň $B$, tak taky $C$“, (iii) „koupeny aspoň 2 ze 3 budov $A, B, C$“.
a) Co je v zadání?
Tatáž Real Estate kostra, ale zkoušející navrší několik logických omezení naráz — přesně mix téhle lekce. Poslední překvapení testu („vyber 2 ze 3 podmínek“ přes velké $M$ a $y_1 + y_2 + y_3 \le 1$) je už disjunkce celých omezení.
b) Co k tomu budeme potřebovat?
- Tato lekce — XOR, AND-implikace, počty vybraných.
- [L1.1] Cílová funkce a základní omezení — základní model.
- Na „2 ze 3 podmínek“: [L1.4] big-M: disjunkce omezení (další lekce).
c) Jak nad úlohou uvažovat?
Body (i) a (ii) jsou přímo vzorce z takeaways. U bodu (iii) se ptej: počítám budovy (binárky), nebo platnost nerovností? Když binárky — stačí součet s vhodnou pravou stranou. A rozmysli si dopředu, proč by „aspoň 2 ze 3 nerovností“ stejným součtem nešlo (čím se nerovnost liší od binární proměnné?).
d) Úplné řešení
Nad binárkami $x_A, x_B, x_C$ Real Estate modelu:
- (i) $A$ XOR $B$: $x_A + x_B = 1$.
- (ii) $(A \text{ AND } B) \Rightarrow C$: $x_C \ge x_A + x_B - 1$.
- (iii) aspoň 2 ze 3 budov: $x_A + x_B + x_C \ge 2$.
Proč (iii) nefunguje pro podmínky-nerovnosti: nerovnost typu $5x_1 + 7x_2 \le 14$ není proměnná — nemá hodnotu 0/1, kterou bys sečetl. „Platí aspoň 2 ze 3 nerovností“ se řeší tak, že ke každé nerovnosti přidáš binární přepínač $y_i$, který ji přes člen $+ M y_i$ umí „vypnout“, a vypnutí povolíš nejvýš jedno: $y_1 + y_2 + y_3 \le 1$ — přesně konstrukce z přepisu testu. Detailně v [L1.4].