slama.dev

Diskrétní a spojitá optimalizace

10. 1. 2022; poznamky z prednasky; available as a [PDF]

Poznámky jsou aktuálně rozpracované, dokončené budou až o zkouškovém.

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Martina Loebla a Milana Hladíka z akademického roku 2021/2022. Pokud by byla někde chyba/nejasnost, nebo byste rádi někam přidali obrázek/text, tak stránku můžete upravit pull requestem (případně mi dejte vědět na mail).

TODO: dělení na diskrétní a spojitou část

Základní definice

Definice (matroid): je dvojice (X,S)(X, \mathcal{S}), kde XX je konečná množina, S2X\mathcal{S} \subseteq 2^X splňující

  1. ∉S\emptyset \not \in \mathcal{S}
  2. dědičnost: (AS)AA    AS(\forall A \in \mathcal{S}) A' \subseteq A \implies A' \in \mathcal{S}
  3. výměnný axiom: (U,VS)U>V    (uUV)V{u}S(\forall U, V \in \mathcal{S}) |U| > |V| \implies (\exists u \in U \setminus V) V \cup \left\{u\right\} \in \mathcal{S}
    • (3):(3'): AX    A \subseteq X \implies všechny maximální (\subseteq) podmnožiny AA v S\mathcal{S} mají stejnou velikost

Prvkům S\mathcal{S} říkáme nezávislé množiny.

Lemma (stejná definice): Axiomy (1,2,3)(1, 2, 3) a (1,2,3)(1, 2, 3') definují stejný objekt.

Důkaz: (3)    (3)(3) \implies (3') sporem:

Důkaz: (3)    (3)(3') \implies (3) sporem:

Příklad:

  1. vektorový matroid:
    • nechť MM je matice nad tělesem F\mathbb{F} s řádky CC
    • VM=(C,S)\mathcal{V}_M = (C, \mathcal{S}), kde
      • AS    ACA \in \mathcal{S} \iff A \in C a AA je lineárně nezávislé v F\mathbb{F}
      • to, že je to matroid vyplívá ze Steinitzovy věty
  2. grafový matroid:
    • mějme graf G=(V,E)G = (V, E)
    • MG=(E,S)\mathcal{M}_G = (E, \mathcal{S}), kde
      • AS    AEA \in \mathcal{S} \iff A \subseteq E a AA je acyklická
      • (1):(1): S\emptyset \in \mathcal{S}
      • (2):(2): podmnožina acyklické je rovněž acyklická
      • (3):(3): počítání přes to, kolik hran je v komponentách souvislosti

(👀): matroidy jsou přesně dědičné systémy, kde lze definovat řádová funkce

Definice (řádová funkc ): mějme systém podmnožin (Z,M),M2Z(\mathcal{Z}, \mathcal{M}), \mathcal{M} \subseteq 2^{\mathcal{Z}} a AZA \subseteq \mathcal{Z}. Pak řádovou funkci r:2ZNr: 2^{\mathcal{Z}} \mapsto \mathbb{N} definujeme jako velikost maximální podmnožiny patřící do M\mathcal{M}:

r(A)=max{XX2AXM}r(A) = \max \left\{|X| \mid X \in 2^A \land X \in \mathcal{M}\right\}

Věta (charakteristika řádové funkce): funkce r:2XNr : 2^X \mapsto N je řádová funkce nějakého matroidu nad XX     \iff platí:

  1. r()=0r(\emptyset) = 0
  2. r(Y)r(Y{y})r(Y)+1r(Y) \le r(Y \cup \left\{y\right\}) \le r(Y) + 1
  3. r(Y{y})=r(Y{z})=r(Y)    r(Y)=r(Y{y,z})r(Y \cup \left\{y\right\}) = r(Y \cup \left\{z\right\}) = r(Y) \implies r(Y) = r(Y \cup \left\{y ,z\right\})

Důkaz:     \implies:

  1. max. nezávislá podmnožina \emptyset je \emptyset a =|\emptyset| = \emptyset
  2. z definice řádové funkce a dědičnosti matroidu
  3. TODO

Grafová odbočka

Algoritmus (hladový): je-li dán souvislý graf G=(V,E)G = (V, E) a váhová funkce w:EQ+w : E \mapsto \mathbb{Q}^+, pak MST (minimum spanning tree) lze najít hladovým algoritmem (bereme vždy nejlehčí kterou můžeme přidat) v polynomiálním čase.

Definice (sudá podmnožina hran): podmnožina hran EEE' \subseteq E je sudá, právě když H=(V,E)H = (V, E') má pouze sudé stupně.

Definice (matice incidence) grafu G=(V,E)G = (V, E) je matice IGF2V×EI_G \in \mathbb{F}_2^{|V| \times |E|} t.ž. (IG)v,e={1ve0jinak\left(I_G\right)_{v,e}=\begin{cases} 1 & v \in e \\ 0 & \text{jinak} \end{cases}



Definice (jádro matice incidence): pro matici incidence IGI_G definujeme jádro jako KerF2IG={xF2EIGx=0}\mathrm{Ker}_{\mathbb{F}_2} I_G = \left\{\mathbf{x} \in \mathbb{F}_2^{|E|} \mid I_G \mathbf{x} = \mathbf{0}\right\}

Definice (charakteristický vektor): mějme nosnou množinu XX a podmnožinu AXA \subseteq X. Charakteristický vektor AA je XA{0,1}X\mathcal{X}_A \in \left\{0, 1\right\}^{|X|} t.ž. (XA)k={1kA0k∉A\left(\mathcal{X}_A\right)_{k} = \begin{cases} 1 & k \in A \\ 0 & k \not\in A \end{cases}

(👀): řádek matice incidence IGI_G indexovaný vrcholem ww je roven XN(w)okolıˊ\mathcal{X}_{\underbrace{|N(w)|}_{\text{okolí}}}

(👀) (prostor cyklů): jádro matice můžeme ekvivalentně vyjádřit jako KerF2IG={xF2Ex=XE pro E sudou}\mathrm{Ker}_{\mathbb{F}_2} I_G = \left\{x \in \mathbb{F}_2^{|E|} \mid x = \mathcal{X}_{E'}\ \text{pro}\ E'\ \text{sudou}\right\} Tuto množinu rovněž nazýváme prostor cyklů.

TODO: hodně přednášek

Perfektní párování

Definice (párování): G=(V,E)G = (V, E) graf; MEM \subseteq E párovaní, jestliže e,eM    e=ee, e' \in M \implies e=e' nebo ee=e \cap e' = \emptyset.

Definice (maximální párování) pokud M|M| je maximální (co do velikosti).

(👀): neplatí, že maximální do velikosti je maximální do inkluze (můžeme si hrany vybrat špatně)

Definice (perfektní párování): pokud M=V/2|M| = |V| / 2

Definice (pokrytí): vrchol je MM-pokrytý, pokud je v nějaké hraně z párování, jinak je MM-nepokrytý.

Definice (defekt) def(M)\mathrm{def}(M) je počet MM-nepokrytých vrcholů

Definice (alternující cesta): podgraf, který je cesta

Věta: graf G=(V,E)G = (V, E), MM párování. Pak MM je maximální     \iff GG nemá zlepšující cestu.

Důkaz:

(👀): G=(V,E),AVG = (V, E), A \subseteq V. Pak v libovolném párování musí být liché komponenty GAG \setminus A pokryté pouze z AA a tedy def(M)lc(GA)A\mathrm{def}(M) \ge \mathrm{lc}(G \setminus A) - |A| Kde lc\mathrm{lc} značí počet lichých komponent grafu.

(👀): g=(V,E)g = (V, E). Pak max. velikost párování minAV12(Vlc(GA)+A)\le \min_{A \subseteq V} \frac{1}{2} \left(|V| - \mathrm{lc}(G \setminus A) + |A|\right)

Věta (Tutte-Berge): Pro výše uvedené pozorování max=min\max = \min

Důkaz: stačí najít párování MM t.ž. platí rovnost.

Najdeme algoritmem (Edmonds), který najde maximální párování

  1. MM perfektní     \implies je maximální a věta platí (A=A = \emptyset)
  2. MMMM-nepokrytý vrchol rr: budujeme alternující strom TT tím, že sřídavě přidáváme hrany:
    • BB-vrcholy: vrcholy v sudé vzdálenosti od rr
    • AA-vrcholy: vrcholy v liché vzdálenosti od rr
    • zastavíme se, když:
      • existuje w∉T,{v,w}Ew \not\in T, \{v, w\} \in E a ww je nepokrytý – pak jsme našli alternující cestu
      • neexistuje ww
        1. všechny zbývající hrany z BB-vrcholů vedou do AA-vrcholů – poté když uvážíme GAG \setminus A, tak liché komponenty vedou pouze do AA vrcholů ale BB je o jedna více (máme rr), tedy B=A+1|B| = |A| + 1 a GG nemá perfektní párování a našli jsme defektní vrchol
        2. pokud je graf bipartitní, tak nemáme žádné BBB-B hrany

TODO: obrázek?

Pro bipartitní grafy můžeme algoritmus výše opakovat (opakovaně stavíme stromy z vrcholů, které nejsou v párování), najít všechny defektní vrcholy a věta výše platí (máme množinu defektních vrcholů a párování splňující rovnost).

Pro nebipartitní grafy může existovat hrana mezi BBB-B vrcholy (lichá kružnice).

(👀): CC lichá kružnice v GG, GG' vznikne kontrakcí CC do jednoho (pseudo)vrcholu, MM' je párování v GG'. Potom existuje párování MM v GG, že počet MM'-nepokrytých vrcholů je stejný jako počet MM-nepokrytých.

TODO: obrázek

Podgrafy GG reprezentované pseudovycholy mají lichý počet vrcholů (chceme opět dostat MM a AA, abychom větu dokázali). To platí, protože pseudovrcholy vzinkly kontrakcí liché kružnice na vrchol a tedy přišly o sudý počet vrcholů.

Postup pro BBB-B hrany je tedy ten, že zkontrahujeme CC, rekurzivně vyřešíme párování a odkontrahujeme.

Důsledek (Tutte [47]): GG má perfektní párování     AV:lc(GA)A\iff \forall A \subset V: \mathrm{lc}(G \setminus A) \le |A|

Věta (Edmonds-Gallai dekompozice): GG graf, G=(V,E)G = (V, E), BVB \subseteq V vrcholů nepokrytých nějakým maximálním párovaním. Nechť AVBA \subseteq V \setminus B sousedé vrcholů z BB, C=V(BA)C = V \setminus \left(B \cup A\right). Pak

  1. každá komponenta G(AC)G \setminus \left(A \cup C\right) je kritická (vK:K{v}\forall v \in K: K \setminus \left\{v\right\} má PP)
    • GG kritický     \iff GG lze zkonstruovat z liché kružnice lepením lichých uší
  2. každé maximální párování MM splňuje:
    • eM,eA    eA=1e \in M, e \cap A \neq \emptyset \implies |e \cap A| = 1 a ee vede do BB
      • tohle nezamezuje, že by dvě hrany z AA nevedly do jedné z BB
    • do každé komponenty BB vede 1\le 1 hrana MM

Důkaz: Uvažme poslední alternující les v Edmondsově algoritmu.

Každá hrana s koncem v AA vede do BB (s tím, že vrcholy v BB jsou (pseudo)vrcholy vzniklé operací kontrakce. Defekt def(M)\mathrm{def}(M) je počet komponent v tomto lese.

Nepokryté vrcholy žádným maximálním párováním:

Takové vrcholy tedy mohou být pouze v BB, čímž jsme dokázali (1).

Část (2) rovněž plyne z Edmondsova algoritmu.

?

Nechť G=(V,E)G = (V, E) rovinný, w:EQw : E \mapsto \mathbb{Q}

  1. maximální PP – najdi MM PP t.ž. w(E)w(E) je maximální
    • polynomiální (pro všechny grafy)
  2. maximální hranový řez – najdi EE' hranový řez t.ž. w(E)w(E') je maximální
    • obecně je NP-těžný, pro grafy na 2D plochách polynomiální

Definice (determinant): nechť AA je reálná matice. Pak determinant je Det(A)=π(1)sign(π)i=1nAi,π(i)transverzaˊla\mathrm{Det}(A) = \sum_{\pi} (-1)^{\mathrm{sign}(\pi)} \overbrace{\prod_{i = 1}^{n} A_{i, \pi(i)}}^{\text{transverzála}}

Definice (permanent): nechť AA je reálná matice. Pak permanent je Per(A)=πi=1nAi,π(i)\mathrm{Per}(A) = \sum_{\pi} \prod_{i=1}^{n} A_{i, \pi(i)}

Příklad: G=(V1,V2,EG = (V_1, V_2, E bipartitní graf, AV1×V2A^{|V_1| \times |V_2|} 010-1 matice podle toho, jaké obsahuje hrany. Pak Per(A)\mathrm{Per}(A) je počet perfektních párování GG.

Generující funkce, které se hodí

P(G,x,w)=P perf. paˊr.xw(P)\mathcal{P}(G, x, w) = \sum_{P\ \text{perf. pár.}} x^{w(P)} E(G,x,w)=E sudaˊxw(E)\mathcal{E}(G, x, w) = \sum_{E'\ \text{sudá}} x^{w(E')} φ(G,x,w)=C hranovyˊ rˇezxw(C)\varphi(G, x, w) = \sum_{C\ \text{hranový řez}} x^{w(C)}

Věta: GG rovinný. Pak φ(G)E(G)P(GΔ)\varphi(G) \equiv \mathcal{E}(G^*) \equiv \mathcal{P}(G_\Delta^*) kde symbolem \equiv rozumíme vzhledem k vypočítatelnosti a GΔG_\Delta následující operaci:

Rovněž předpokládáme w(e)Z,w(e)V(G)cw(e) \in \mathbb{Z}, |w(e)| \le |V(G)|^{c} pro cc konstantu.

Věta (Kasteleyn): Když GG rovinný, pak P(G,x,w)\mathcal{P}(G, x, w) lze spočítat v polynomiálním čase.

Důsledek:

Důkaz (naznačení): pro DD orientaci GG, M0M_0 fixní PP definujeme „determinantní verzi“ P\mathcal{P} následně: P(G,D,M0,x,w)=P perf. paˊr.sign(D,M0,P)xw(P)\mathcal{P(G, D, M_0, x, w)} = \sum_{P\ \text{perf. pár.}} \mathrm{sign}(D, M_0, P) x^{w(P)} kde sign(D,M0,P)=(1)# D-sudyˊch cyklu˚ M0 Δ P\mathrm{sign}(D, M_0, P) = (-1)^{\#\ \text{$D$-sudých cyklů $M_0\ \Delta\ P$}}

Postup důkazu:

Připomenutí: pro další plochy je to trochu komplikovanější, ale jde to dělat podobně.

Pošťáci a cestující

Definice: G=(V,E)G = (V, E) graf silniční sítě, l:EQ+l : E \mapsto \mathbb{Q}^+:

Problém (čínského pošťáka):

  1. G=(V,E)G = (V, E)všechny stupně sudé      \implies řešení je uzavřený eulerovský tah
    • (👀): když H=(W,F)H = (W, F) má všechny stupně sudé a FF \neq \emptyset je neprázdná, pak FF má cyklus; odstraněním cyklu má opět všechny stupně sudé; opakováním dostaneme disjunktní sjednocení cyklů, což jde do eulerovského tahu udělat trivialně
  2. nechť T={vdegG(v) lichyˊ}T = \left\{v \mid \mathrm{deg}_G(v)\ \text{lichý}\right\}

(👀): T|T| je sudé (počet vrcholů lichého stupně je sudý) Definice: EEE' \subseteq E je TT-join, jestli graf GT=(V,E)G_T = (V, E') splňuje (vV)(degGT(v) lichyˊ    vT)\left(\forall v \in V\right) \left(\mathrm{deg}_{G_T} (v)\ \text{lichý} \iff v \in T\right)

Věta: nechť EEE' \subseteq E je množina hran min. trasy čínského pošťáka, které se projdou více než jednou. Pak

  1. se projdou 22-krát
  2. EE' je min. TT-join (kde TT je výše definovaná množina)

Důkaz: (👀): nechť GG' vznikne z GG dodáním násobných hran, násobnost je podle počtu procházení minimální trasou PP. Potom GG' má všechny stupně sudé.

Z pozorování plyne (1), jelikož FF spolu s původními hranami dává 22 průchody.

Navíc jelikož E(G)=E(G)FE(G') = E(G) \cup F je TT-join, jelikož přesné splňuje definici (stupně budou liché v GG', protože musí být sudé po přidaní do GG). Navíc E(G)FE(G) \cup \overline{F} rozhodně nebude lepší než minimální cesta čínského pošťáka a tedy naše FF.

Algoritmus (čínský pošťák):

  1. najdi minimální TT-join
    • použij konstrukci (modifikovanou) Fischera z minulé přednášky (GGΔG \mapsto G_\Delta), o čemž víme, že je polynomiální
    • (alternativně) uvažme pomocný graf H=(T,(T2))H = \left(T, \binom{T}{2}\right) a váha w:(T2)Q+w : \binom{T}{2} \mapsto \mathbb{Q}^+, kde w({u,v})=w(\left\{u, v\right\}) = délka nejkratší cesty mezi u,vu, v v GG
      • nechť MM je min. PP v HH
      • nechť F=eMPeF = \bigcup_{e \in M} P_e, kde PeP_e je nejkratší cesta v GG spojující vrcholy ee
  2. přidej zbylé hrany
  3. profit?

Problém (obchodního cestujícího): předpokládáme

Christofidesova heuristika

Poděkování