Čtení: 30 minHodnotí se: zápočtový test, úloha 3 (6 b)

3 Modelování jako ILP a SAT

Po přečtení umíš

zvolit proměnné, aby každé řešení odpovídalo jednomu přiřazení
přepsat podmínky „aspoň“, „nejvýše“ a „právě“ do ILP i CNF
zapsat klasické problémy jako ILP nebo SAT
ověřit, že model nedovoluje nesmyslná řešení

V úloze máš problém a chceš ho přeložit do jazyka řešiče. Nemusíš vymýšlet algoritmus. Stačí dobře pojmenovat proměnné a vzorně přepsat podmínky.

3.1 Ukázka: rozdáváme hlídky

Ve firmě jsou tři chodby: AB, BC, CD. Chceme co nejméně hlídek tak, aby každá chodba měla hlídku aspoň na jednom konci. To je Vertex Cover.

Pro každé místo zavedeme $x_v \in \{0, 1\}$ , kde 1 znamená, že tam hlídka je.

\min\ x_A + x_B + x_C + x_D

x_A + x_B \ge 1, \quad x_B + x_C \ge 1, \quad x_C + x_D \ge 1

Řešením je $x_B = x_C = 1$ se dvěma hlídkami. Každá nerovnice říká přesně jednu větu ze zadání.

3.2 ILP

Definice 3.2 (Celočíselné lineární programování)

Proměnné $x_1, \dots, x_n \in \mathbb{Z}$ , často jen $\{0, 1\}$ . Minimalizujeme lineární funkci za podmínek $Ax \le b$ . Rozhodovací verze se ptá, zda existuje celočíselné $x$ splňující $Ax \le b$ . Reálné LP je polynomiální, požadavek celých čísel z něj dělá NP-těžký problém.

Tahák (Převod vět do ILP)

Věta	Zápis
aspoň jedno z $a, b$	$a + b \ge 1$
nejvýše jedno	$a + b \le 1$
právě jedno	$a + b + c = 1$
negace $\neg a$	$1 - a$
$a$ implikuje $b$	$a \le b$
nejvýše $k$ vybraných	$\sum_v x_v \le k$

Příklad 3.4 (3-SAT jako ILP)

Pro každou proměnnou $y_i \in \{0, 1\}$ . Negaci zapíšeme $1 - y_i$ . Klauzule $(y_1 \vee \neg y_2 \vee y_3)$ se stane

y_1 + (1 - y_2) + y_3 \ge 1.

Klauzule je splněná, když je aspoň jeden sčítanec 1.

Příklad 3.5 (3-barvení jako ILP)

Indikátor $x_{v,c} \in \{0, 1\}$ říká, že vrchol $v$ má barvu $c$ .

Každý vrchol má právě jednu barvu: $x_{v,R} + x_{v,G} + x_{v,B} = 1$ .
Hrana $\{u, v\}$ a barva $c$ : $x_{u,c} + x_{v,c} \le 1$ .

Příklad 3.6 (Dominující množina jako ILP)

$x_v \in \{0, 1\}$ znamená, že $v$ je v množině. Každý vrchol musí být vybraný nebo mít vybraného souseda:

x_v + \sum_{u \in N(v)} x_u \ge 1 \quad \forall v, \qquad \sum_v x_v \le k.

3.3 SAT

Formule je v CNF: klauzule spojené AND, uvnitř OR. Řešič dostane DIMACS: proměnné jsou čísla, řádek 1 -2 0 znamená $x_1 \vee \neg x_2$ .

Tahák (Převod vět do CNF)

Věta	Klauzule
aspoň jedno z $a, b, c$	$(a \vee b \vee c)$
nejvýše jedno	$(\neg a \vee \neg b), (\neg a \vee \neg c), (\neg b \vee \neg c)$
právě jedno	obojí dohromady
$a$ implikuje $b$	$(\neg a \vee b)$
ne všechny tři	$(\neg a \vee \neg b \vee \neg c)$

Rozdíl proti ILP: v SAT není součet. Podmínka „nejvýše jedno“ proto potřebuje klauzuli na každou dvojici.

Příklad 3.8 (3-barvení jako SAT)

Proměnná $x_{v,c}$ pro každý vrchol a barvu.

Aspoň jedna barva: $(x_{v,1} \vee x_{v,2} \vee x_{v,3})$ .
Hrana: $(\neg x_{u,c} \vee \neg x_{v,c})$ pro každou barvu $c$ .

Podmínka „nejvýše jedna barva“ tu není potřeba. Má-li vrchol v řešení dvě barvy, jednu zahodíme a nic se nepokazí. Stejný trik používá proseminář u Schurových čísel.

Příklad 3.9 (Hamiltonovská kružnice jako SAT)

Klíč je kódování podle pozic: $x_{p,v}$ říká, že na pozici $p$ kružnice je vrchol $v$ .

Na každé pozici je aspoň jeden vrchol.
Každý vrchol je aspoň na jedné pozici.
Žádný vrchol není na dvou pozicích: $(\neg x_{p,v} \vee \neg x_{q,v})$ .
Na žádné pozici nejsou dva vrcholy: $(\neg x_{p,u} \vee \neg x_{p,v})$ .
Sousední pozice jsou spojené hranou. Pro každou nehranu $\{u, v\}$ a pozici $p$ : $(\neg x_{p,u} \vee \neg x_{p+1,v})$ , indexy modulo $n$ .

Proměnných je $n^2$ a klauzulí polynomiálně mnoho.

Příklad 3.10 (Schurův problém z prosemináře)

Lze čísla $1, \dots, n$ obarvit $k$ barvami bez jednobarevné trojice $x + y = z$ ? Proměnná $x_{i,c}$ , v DIMACS $(i - 1)k + c$ .

Aspoň jedna barva pro každé $i$ .
Pro $x \le y$ , $x + y \le n$ a barvu $c$ : $(\neg x_{x,c} \vee \neg x_{y,c} \vee \neg x_{x+y,c})$ .

Pro $k = 3$ dostane číslo 2 s barvou 2 proměnnou $(2 - 1) \cdot 3 + 2 = 5$ .

3.4 Jak model ověřit

Než model odevzdáš, odpověz si na dvě otázky:

Každé skutečné řešení splňuje všechny podmínky? Jinak model zakazuje něco platného.
Každé splnění podmínek je skutečné řešení? Jinak model pouští nesmysl.

3.5 Typické chyby

Nelineární člen $x_u \cdot x_v$ v ILP.
Zapomenutá negace, když se klauzule přepisuje do součtu.
SAT model bez podmínek „nejvýše jeden“ tam, kde jsou potřeba.
Chybějící význam proměnných. Vždy napiš větu, co proměnná znamená.

3.6 Kvíz

Kvíz

1. Jak v ILP zapíšeš, že vybereš právě jeden ze tří prvků?

a + b + c \ge 1

a + b + c \le 1

a + b + c = 1

a \cdot b \cdot c = 1

2. Kolik klauzulí potřebuje v SAT podmínka nejvýše jedno z 5 proměnných při párovém kódování? 5 10 20 32

3. Schurův problém s

k = 4

: jaké číslo má proměnná

x_{3,2}

v DIMACS? Odpověď:

4. Které zápisy patří do ILP? Může být správně více možností, ale také žádná.

x_1 + 2x_2 \le 3

x_1 x_2 \le 1

1 - x_3 \ge 0

x_1^2 = 1

5. Klauzule

(y_1 \vee \neg y_2)

v ILP je:

y_1 + y_2 \ge 1

y_1 + (1 - y_2) \ge 1

y_1 - y_2 \ge 1

6. Proč u 3-barvení v SAT nemusí být podmínka nejvýše jedna barva?

Ukázat řešení

Z vrcholu s více barvami lze libovolnou barvu odebrat a žádná podmínka hrany se tím neporuší. Formule jsou ekvisplnitelné.

3.7 Příklady na procvičení

Cvičení 3.11

Zapiš Set Cover jako ILP.

Řešení

$x_i \in \{0, 1\}$ říká, že množina $S_i$ je vybraná. Pro každý prvek $u$ : $\sum_{i : u \in S_i} x_i \ge 1$ . Dále $\sum_i x_i \le k$ .

Cvičení 3.12

Zapiš Clique velikosti $k$ jako SAT.

Řešení

$x_{i,v}$ říká, že $i$ -tý člen kliky je vrchol $v$ , pro $i = 1, \dots, k$ .

Každý člen je nějaký vrchol: $\bigvee_v x_{i,v}$ .
Pro $i < j$ a dvojici $u, v$ , kde $u = v$ nebo $\{u, v\}$ není hrana: $(\neg x_{i,u} \vee \neg x_{j,v})$ .

Druhá podmínka zakáže opakování vrcholu i nehrany.

Cvičení 3.13

Máš $n$ zkoušek, $t$ termínů, nejvýše $c$ zkoušek v termínu a konflikty mezi zkouškami. Zapiš ILP.

Řešení

$x_{e,t}$ říká, že zkouška $e$ je v termínu $t$ .

Každá zkouška jednou: $\sum_t x_{e,t} = 1$ .
Konflikt $\{e, f\}$ : $x_{e,t} + x_{f,t} \le 1$ pro každé $t$ .
Kapacita: $\sum_e x_{e,t} \le c$ pro každé $t$ .

3.8 Tahák

Tahák

Napiš větu: „ $x_{...}$ znamená, že ...“.
ILP: aspoň $\ge 1$ , nejvýše $\le 1$ , právě $= 1$ , negace $1 - a$ , implikace $a \le b$ .
SAT: aspoň = jedna klauzule, nejvýše = klauzule na dvojici, implikace $(\neg a \vee b)$ .
Pořadí a cesty: $x_{p,v}$ (na pozici $p$ je vrchol $v$ ).
Výběr z více možností: indikátor $x_{v,c}$ .
Kontrola: řešení ⇒ podmínky, podmínky ⇒ řešení.

Kapitolu mám prostudovanou