11 Kombinatorické optimalizační problémy Velmi mnoho známých kombinatorických úloh má přirozené formulace v lineární či celočíselné optimalizaci. Předpokládáme, že čtenáři, zvláště ti mající informatický základ, znají různé běžné kombinatorické problémy na grafech, nebo třeba problémy splnitelnosti formulí. Ukázkami jejich formulace zároveň čtenáři ukážeme některé obecné principy formulace úloh IP. Stručný přehled lekce ˇ Formulace problémů splnitelnosti logických formulí SAT. ˇ Formulace běžných grafových problémů ­ párování, nezávislá a do- minující množina, barevnost. ˇ Problém obchodního cestujícího. Petr Hliněný, FI MU 1 IA102 "OU": Kombinatorické optimalizační problémy 11.1 Formulace problému SAT Začneme s IP formulací jednoho ze základních obtížných algoritmických problémů a jeho optimalizačního rozšíření. Definice: Logická formule s proměnnými x1, x2, . . . , xn je v konjunktivním normál- ním tvaru pokud je zapsaná jako = c1 c2 . . . ck , kde každé ci se nazývá klauzule a představuje zkratku pro ci = (i1 i2 . . . imi ) a kde ij je literál mající jednu ze dvou podob pro některé p {1, . . . , n} ij xp nebo ij xp . Příklady logických formulí v konjunktivním normálním tvaru jsou: 1 = (x1 x2 x4) (x1 x3 x4) (x2 x3 x4) 2 = (x1 x2) (x1 x3 x4) (x2 x3 x4) (x1 x4 x5) (x2 x5) U takovýchto formulí si budeme všímat, zda některé logické ohodnocení vstupních proměnných má za výsledek hodnotu T (pravda) celé formule. Petr Hliněný, FI MU 2 IA102 "OU": Kombinatorické optimalizační problémy Definice: Problém splnitelnosti SAT se pro danou formuli v konjunktivním normálním tvaru ptá, zda je pro nějaké ohodnocení proměnných tato formule pravdivá. Problém MAX-SAT se pro danou formuli v konjunktivním normálním tvaru ptá, kolik nejvíce klauzulí v ní lze splnit vhodným ohodnocením proměnných. Věta 11.1. Problém MAX-SAT lze formulovat v IP s polynomiálním počtem nerov- ností a proměnných. Důkaz: Použijeme binární proměnné zi pro logické proměnné xi dané formule a další binární proměnné tl pro klauzule cl ve . Účelovou funkcí bude max t1 + t2 + . . . + tk za podmínek, ve kterých pro každou klauzuli cl = xi xj . . . píšeme tl zi + (1 - zj) + . . . . Snadno vidíme, že hodnota tl = 1 pro klauzuli cl je přípustná právě tehdy, pokud aspoň jedna pozitivní proměnná v cl má hodnotu 1 nebo pokud aspoň jedna negovaná proměnná v cl má hodnotu 0. To jest právě když je klauzule cl splněná v ohodnocení. 2 Petr Hliněný, FI MU 3 IA102 "OU": Kombinatorické optimalizační problémy Pro výše uvedený příklad formule 1 = (x1 x2 x4) (x1 x3 x4) (x2 x3 x4) důkaz Věty 11.1 vyprodukuje úlohu IP ve tvaru max t1 + t2 + t3 : t1 z1 + 1 - z2 + z4 t2 1 - z1 + z3 + z4 t3 1 - z2 + 1 - z3 + 1 - z4 . Důsledek 11.2. Problém SAT, a tudíž všechny problémy ve třídě NP, lze efektivně vyjádřit jako problém existence přípustného řešení pro úlohu IP. Důsledek 11.3. Otázka existence přípustného řešení úlohy IP je NP-úplná a řešení úloh IP je NP-těžké. Uvědomte si, jak silné jsou uvedené důsledky. Nejen, že víme, že řešení úloh IP je v obecnosti efektivně nezvládnutelné, ale víme i, že každý problém ve třídě NP je nějakým způsobem zformulovatelný jako problém přípustnosti IP. Něco takového u mnoha příkladů vůbec není zřejmé, jak sami z vlastní zkušenosti poznáte. . . Petr Hliněný, FI MU 4 IA102 "OU": Kombinatorické optimalizační problémy 11.2 Některé grafové problémy Pro ukázku se podíváme na IP formulace několika známých grafových problémů. Příklad 11.4. Zformulujme problém párování v grafu jako problém IP. Množina hran M je párováním, pokud žádné dvě z nich nesdílí vrchol. Pro ilustraci, následující graf má největší párování velikosti 3. s s ss s s 1 2 3 45 6 Řešení: V příkladech jako tento, kdy hledáme podmnožinu jistých vlastností, je přiro- zenou volbou přiřadit této podmnožině její charakteristický vektor (složený z binárních proměnných). V tomto případě tedy hraně {i, j} přiřadíme binární proměnnou zi,j s významem, že zi,j = 1 právě když {i, j} M. Aby vybraná podmnožina M byla párováním, může každý vrchol grafu náležet nejvýše jedné hraně M. Pro vrchol i se sousedy j1, . . . , jk tedy zformulujeme podmínku zi,j1 + zi,j2 + . . . + zi,jk 1 . Účelovou funkcí ­ velikostí párování, je potom součet všech proměnných zi,j pro hrany grafu, případně i vážený součet. Petr Hliněný, FI MU 5 IA102 "OU": Kombinatorické optimalizační problémy Například pro graf na obrázku zformulujeme úlohu s s ss s s 1 2 3 45 6 max z13 + z15 + z24 + z34 + z45 + z56 + z46 : z13 + z15 1 z13 + z34 1 z24 + z34 + z45 + z46 1 z15 + z45 + z56 1 z46 + z56 1 z13, z15, z24, z34, z45, z56, z46 {0, 1} . 2 Petr Hliněný, FI MU 6 IA102 "OU": Kombinatorické optimalizační problémy Příklad 11.5. Zformulujme problém nezávislé množiny v grafu jako problém IP. Množina vrcholů I je nezávislá, pokud žádné dva z nich nejsou spojené hranou. Pro ilustraci, následující graf má největší nezávislou množinu velikosti 3. Dokážete ji najít? s s ss s s 1 2 3 45 6 Řešení: V tomto příkladě hledáme podmnožinu vrcholů, takže vrcholu i přiřadíme binární proměnnou zi s významem, že zi = 1 právě když i I. Podmínka nezávislosti se pak formuluje jako nerovnost zi + zj 1 pro každou hranu {i, j} daného grafu. Například pro graf na obrázku zformulujeme úlohu max z1 + z2 + z3+ z4 + z5 + z6 : z1 + z2 1, z1 + z3 1 z1 + z5 1, z2 + z4 1 z3 + z4 1, z6 + z4 1 z5 + z4 1, z6 + z5 1 z1, z2, z3, z4, z5, z6 {0, 1} . 2 Petr Hliněný, FI MU 7 IA102 "OU": Kombinatorické optimalizační problémy Příklad 11.6. Zformulujme problém dominující množiny v grafu jako problém IP. Dominující množina D v grafu G je taková D V (G), že každý vrchol G mimo D je spojený hranou s některým vrcholem v D. Najdete v následujícím grafu dominující množinu velikosti 2? s s ss s s 1 2 3 45 6 Řešení: Opět každému vrcholu i přiřadíme binární proměnnou zi s významem, že zi = 1 právě když i D. Podmínka dominující množiny se pak formuluje pro každý vrchol i se sousedy j1, . . . , jk jako nerovnost zi + zj1 + . . . + zjk 1 vyjadřující, že vrchol i je v D nebo některý jeho soused je v D. Například pro graf na obrázku zformulujeme úlohu min z1 + z2 + z3 + z4 + z5 + z6 : z1 + z2 + z3 + z5 1 z2 + z1 + z4 + z6 1 z3 + z1 + z4 1 z4 + z2 + z3 + z5 1 Petr Hliněný, FI MU 8 IA102 "OU": Kombinatorické optimalizační problémy z5 + z1 + z4 + z6 1 z6 + z2 + z5 1 z1, z2, z3, z4, z5, z6 {0, 1} . 2 Předchozí příklady byly docela jednoduché a přímočaré, že? Co ale třeba s podobně jednoduše vypadajícím problémem barvení grafu? Obarvením grafu rozumíme přiřazení přirozených čísel (barev) vrcholům grafu tak, aby sousední vrcholy dostaly různé barvy. Barevností grafu pak je nejmenší počet barev, kterým lze daný graf obarvit. Příklad 11.7. Zformulujme problém barevnosti grafu jako problém IP. Přirozenou první myšlenkou většiny čtenářů asi bude použít celočíselné proměnné pro barvy jednotlivých vrcholů. (Ponechme stranou otázku omezenosti proměnných, neboť počet barev lze vždy omezit počtem vrcholů.) Jak ale vyjádříme, že sousední vrcholy mají různé barvy? Rámec formulace úloh IP nám totiž nedává možnost přímo na- psat zi = zj. Pokud bychom pro hranu {i, j} chtěli například napsat zi zj +1, museli bychom při- pustit i možnost zi zj -1, ale my neumíme přímo vyjádřit disjunkci podmínek. (Blíže viz Oddíl 12.2.) Využijeme raději podobnost problému barvení s nezávislou množinou ­ vrcholy stejné barvy musí být nezávislé. Obarvení grafu k barvami tudíž znamená nalezení rozkladu množiny vrcholů na k nezávislých podmnožin. Petr Hliněný, FI MU 9 IA102 "OU": Kombinatorické optimalizační problémy Řešení: Pro každou potenciální barvu c (je třeba počítat s počtem barev až rovným počtu vrcholů n) zavedeme sadu binárních proměnných z1,c, . . . , zn,c, kde zi,c = 1 zna- mená, že vrchol i může být obarven barvou c. Pro každé c pak přidáme na z1,c, . . . , zn,c podmínky vyjadřující nezávislou množinu, jako v Příkladě 11.5 c = 1, 2, . . . , n, {i, j} E(G) : zi,c + zj,c 1 . Dále musíme vyjádřit požadavek, že každý vrchol dostane přidělenu jednu barvu k = 1, 2, . . . , n : zk,1 + zk,2 + . . . + zk,n = 1 . Posledním poněkud trikovým bodem je vyjádření počtu barev, které celkem použijeme. Pro to musíme zavést další binární proměnné t1, . . . , tn indikující ty z barev, které byly skutečně použity, a vyjádříme účel min t1 + . . . + tn c = 1, 2, . . ., n : z1,c + z2,c + . . . + zn,c n tc . Všimněte si dobře, jakým způsobem jsme v posledních vztazích "spočítali", kolik barev c je vlastně při barvení našeho grafu použito: Pokud tc = 0, barva c nemůže být použita vůbec, pokud naopak tc = 1, lze c použít až na všech n vrcholech. Jedná se o docela užitečný trik k zapamatování. 2 Petr Hliněný, FI MU 10 IA102 "OU": Kombinatorické optimalizační problémy 11.3 Problém obchodního cestujícího Klasickou dobře známou úlohou diskrétní optimalizace je tzv. problém obchodního cestujícího (TSP), motivovaný následovně: Úkolem cestujícího je obejít daných n měst (v libovolném pořadí, s návratem do výchozího) tak, aby byla celková délka či cena cesty minimální. Tento tradiční problém neopomineme ani v našem textu. Definice: (Orientovaný) sled v grafu G je posloupnost v0, e1, v1, e2, v2, . . . , ek, vk, kde vždy hrana ei, 1 i k vede z vrcholu vi-1 do vi. Definice 11.8. Obecný problém TSP (Obchodního cestujícího v grafu) V nejobecnější grafové formulaci se problém obchodního cestujícího zadá následovně: Vstup: Orientovaný ohodn. souvislý graf G, s ohodnocením hran w : E(G) R+ . Výstup: Najít uzavřený orientovaný sled v G, ve kterém je součet ohodnocení (délek) hran nejmenší možný. Poznámka: Uvědomme si, že optimální řešení obecného problému TSP může opakovat jeden vrchol vícekrát, například pokud graf G je stromem. Obvykle se však při formulaci problému TSP explicitně požaduje, aby se žádný vrchol ve sledu neopakoval, neboli se hledá tzv. Ha- miltonovský cyklus grafu. V této "neopakovací" formulaci také graf G obvykle bývá úplný. Příklad 11.9. Zformulujme problém TSP na orientovaném grafu G bez povoleného opakování vrcholů ve sledu jako úlohu IP. Petr Hliněný, FI MU 11 IA102 "OU": Kombinatorické optimalizační problémy Řešení: Nechť V (G) = {1, 2, ..., n}, pak každé orientované hraně (i, j) E(G) přiřa- díme proměnnou zi,j {0, 1}. Jelikož opakování vrcholů je zakázáno, hledáme formu- laci popisující Hamiltonovský cyklus v G. ˇ Do každého vrcholu k jednou přijdeme a jednou z něj odejdeme i:(i,k)E(G) zi,k = 1, i:(k,i)E(G) zk,i = 1 . Pokud však má G dostatek vrcholů, tyto podmínky splňuje i kolekce více dis- junktních cyklů, že? ˇ Navíc tedy musíme vyloučit případ, kdy by se náš cyklus "uzavřel" ještě před navštívením všech vrcholů. To znamená, že na každé podmnožině vrcholů W V (G), 2 |W| n - 2 zabráníme vytvoření podcyklu nerovnostmi (i,j)E(G), i,jW zi,j |W| - 1 , (1) které zaručí pokračování cyklu mimo W. Takto sestavených nerovností pro TSP je bohužel zhruba 2n , takže je nelze ani rozumně zapsat do paměti. Přesto se tato formulace TSP v praxi používá tak, že nerovnosti v (1) se vygenerují "na žádost", tj. například pro jeden konkrétní podcyklus v částečném řešení přidáme příslušnou vylučující nerovnost. Ukazuje se, že nakonec je třeba využít obvykle jen rozumně malou část ze všech těchto podcyklových nerovností. 2 Petr Hliněný, FI MU 12 IA102 "OU": Kombinatorické optimalizační problémy Poznámka: V poválečné době bylo velkým matematickým úspěchem vyřešit problém TSP na 49 hlavních městech kontinentálních států USA. S dnešními vylepšenými algoritmy a výkon- nými počítači jsme schopni řešit obecné problémy TSP až na tisících vrcholech. Přesto tento optimalizační problém zůstává velmi obtížný a také velmi populární. Aproximace Euklidovského TSP Původní motivace problému TSP nese oproti abstraktní formulaci jednu podstatnou informaci navíc ­ délky hran mezi městy splňují trojúhelníkovou nerovnost. Toho lze s výhodou použít při aproximaci řešení TSP. Definice: Problém TSP se nazývá Euklidovský, pokud délky hran grafu splňují trojú- helníkovou nerovnost (graf musí být úplný). Speciálně tedy pokud jsou délky dány Euklidovskou metrikou. Příklad 11.10. Ukážeme, jak lze problém Euklidovského neorientovaného TSP přibližně vyřešit v polynomiálním čase s cenou nejvýše dvojnásobnou od optimálního řešení. Řešení: Na (neorientovaném) grafu G najdeme minimální kostru T G (například hladovým algoritmem v čase O(mlog m), m = |E(G)|). Pak "zdvojením" každé hrany T dostaneme uzavřený sled délky dvojnásobku T . Pokud je vyloučeno opakování vrcholů, tak nakonec tento sled "narovnáme" přeskoče- ním opakovaných vrcholů. Podle trojúhelníkové nerovnosti si narovnáním sled nepro- dloužíme, ale v praxi většinou zkrátíme. 2 Petr Hliněný, FI MU 13 IA102 "OU": Kombinatorické optimalizační problémy