12 Umění formulace úloh MIP Již několikrát jsme viděli, že formulace úloh diskrétní optimalizace jako úloh MIP nebývá tak jednoduchá a skrývá v sobě někdy nečekaná úskalí. Jedním z nich je třeba nutnost formulovat exponenciálně mnoho omezení, jiným třeba požadavek formulace "A nebo B", což přímo nejde. V této lekci si ukážeme hlubší umění správné formulace diskrétních úloh v MIP na několika hezkých příkladech. Stručný přehled lekce ˇ Obecnější formulace barevnosti grafu. ˇ Další triky formulace; jako vyjádření disjunkce či kratší vyjádření TSP. ˇ Celočíselné polyedry a jejich příklady v kombinatorice. ˇ Neúplné iterativní formulace úloh. Petr Hliněný, FI MU 1 IA102 "OU": Umění formulace 12.1 Více o barevnosti grafu Pro ilustraci některých pokročilých postupů formulace úloh MIP si zkusme nejprve zapsat problém barevnosti grafu (Příklad 11.7) úplně jinou formulací: Příklad 12.1. Zformulujme problém barevnosti grafu jako problém MIP, kde barvy při- řazené vrcholům budou přímo (jako čísla) uloženy v reálných proměnných. Zachováme přitom požadavek, aby se hodnoty sousedních barev líšili alespoň o 1. Řešení: V souladu se zadáním každému vrcholu i = 1, 2, . . ., n grafu G přiřadíme reálnou proměnnou xi. Nechť {i, j} je hranou G. Jak pak v rámci formulace MIP vyjádříme požadavek |xi - xj| 1? To je, zdá se být, hlavním problémem našeho příkladu. Trik je následovný ­ zavedeme dodatečnou binární proměnnou zi,j pro každou hranu {i, j} a požadavek na barvy rozepíšeme jako xi xj - 1 + nzi,j , xi xj + 1 - n(1 - zi,j) . (Hodnota proměnné zi,j nám takto určuje, která z obou barev na hraně {i, j} bude větší.) Skutečně, pokud zi,j = 0, tak z první nerovnosti plyne xi - xj -1, a pokud zi,j = 1, tak z druhé nerovnosti plyne xi - xj 1. Opačný směr ekvivalence je také zřejmý. Petr Hliněný, FI MU 2 IA102 "OU": Umění formulace Nakonec vyjádříme celkový počet použitých barev jako maximum z hodnot nabytých proměnnými x plus 1 (nezapomeňme, že hodnoty x začínají od 0). Takže zapíšeme min y : i = 1, 2, . . ., n : xi + 1 y . Například pro graf na obrázku zapíšeme úlohu MIP s s ss s s 1 2 3 45 6 min y : x1, x2, x3, x4, x5, x6 y - 1 x1 x2 - 1 + 6z12, x1 x2 + 1 - 6(1 - z12) x1 x3 - 1 + 6z13, x1 x3 + 1 - 6(1 - z13) x2 x4 - 1 + 6z24, x2 x4 + 1 - 6(1 - z24) x3 x3 - 1 + 6z34, x3 x4 + 1 - 6(1 - z34) x4 x5 - 1 + 6z45, x4 x5 + 1 - 6(1 - z45) Petr Hliněný, FI MU 3 IA102 "OU": Umění formulace x1 x5 - 1 + 6z15, x1 x5 + 1 - 6(1 - z15) x6 x5 - 1 + 6z65, x6 x5 + 1 - 6(1 - z65) x4 x6 - 1 + 6z46, x4 x6 + 1 - 6(1 - z46) x1, x2, x3, x4, x5, x6 0 z1, z2, z3, z4, z5, z6 {0, 1} . Poněkud stranou zatím zůstala důležitá otázka, zda jsme naší úlohou MIP zapsali skutečně problém klasické barevnosti grafu. Vždyť jsme výrazně rozšířili množinu pří- pustných řešení na reálná čísla. Přesto lze dokázat, že optimálním výsledkem naší úlohy je skutečně klasická (celočíselná) barevnost. 2 Petr Hliněný, FI MU 4 IA102 "OU": Umění formulace Důležitým přínosem nových lineárních formulací kombinatorických problémů je také možnost jejich zobecňování (či relaxace) umožněné novým pohledem. Například výše uvedená formulace grafové barevnosti s reálnými "barvami" přímo motivuje následující (již dříve známou) neceločíselnou relaxaci barevnosti grafu. Definice: Cirkulární barevností grafu G rozumíme nejmenší reálné číslo f > 0 takové, že vrcholy G lze zobrazit na kruhový interval délky (tj. obvodu) f tak, že sousední vrcholy G mají na obvodu kruhu vzdálenost alespoň 1. Příklad 12.2. Zformulujme problém cirkulární barevnosti grafu jako problém MIP, kde barvy přiřazené vrcholům budou přímo uloženy v reálných proměnných. Na začátek si blíže osvětlíme význam kruhového intervalu. Dvě čísla (body) s, t jsou na kružnici o obvodu f ve vzdálenosti alespoň d pokud zároveň |s - t| d a |s - t| f - d (vzdálenosti měřené v obou směrech na kružnici). Podmínka vzdálenosti hodnot sousedních vrcholů G |xi - xj| 1 byla zformulována již v Příkladě 12.1. Pro druhou podmínku vzdálenosti na kruhu se v tomto případě ukazuje jako lepší ji přímo neformulovat, ale místo toho implicitně definovat obvod f kruhového intervalu jako minimum z hodnot |xi - xj| + 1 přes všechny hrany G. Petr Hliněný, FI MU 5 IA102 "OU": Umění formulace Řešení: S výhodou využijeme již zapsané podmínky z Příkladu 12.1 {i, j} E(G) : xi xj - 1 + nzi,j xi xj + 1 - n(1 - zi,j) zi,j {0, 1} a přidáme účelovou funkci spolu s podmínkami min y : i = 1, 2, . . ., n : xi - xj + 1 y (1) xj - xi + 1 y . Pokud cirkulární barevnost G je f, tak výše zapsaný systém podmínek má přípustné řešení s y = f dané tímto cirkulárním obarvením. Naopak pokud vezmeme přípustné řešení výše zapsaného systému podmínek a položíme f = y, pak snadno přiřadíme vrcholu i grafu G barvu ci = xi mod (f +1). Potom bude splněno |ci - cj| 1 a také |ci - cj| y - 1 = f - 1 pro každou hranu {i, j} E(G), neboli se bude jednat o platné cirkulární obarvení. 2 Petr Hliněný, FI MU 6 IA102 "OU": Umění formulace 12.2 Užitečné triky formulace Modelování disjunkce Trik použitý v Příkladě 12.1 lze zobecnit na modelování jakéhokoliv počtu disjunktivních podmínek v úlohách MIP. Stručně řečeno, dokážeme vyjádřit podmínky ve stylu "platí toto nebo toto nebo toto. . . " (nebo zde není exkluzivní). Tvrzení 12.3. Mějme úlohu MIP s omezenou množinou přípustných řešení Q. Nechť P1, . . . , Pk jsou polyedry určené nerovnostmi Cj x dj pro j = 1, . . . , k (kde vektor x zahrnuje všechny proměnné úlohy). Pak úlohu s množinou přípustných řešení Q (P1 . . . Pk) lze vyjádřit jako úlohu MIP. Důkaz: Zvolme nejprve dostatečně velkou konstantu K. Zavedeme nové binární pro- měnné z1, . . . , zk spolu s přidanými vztahy z1 + z2 + . . . + zk = k - 1 j = 1, 2, . . . , k : Cj x dj + K 1 zj (2) Pokud vektory x Q a z splňují vztahy (2), tak jedno zi = 0, neboli x splňuje Ci x di a x Q Pi. Na druhou stranu pokud x Q (P1 . . . Pk), tak pro některé i je x Q Pi. Zvolíme zi = 0 a zj = 1 pro j = i. Pak z předpokladu x Pi bude platit Ci x di a navíc pro vhodnou volbu konstany K bude Cj x dj + K 1 platit pro všechna j = 1, . . . , k. Tudíž (2) bude splněno. 2 Petr Hliněný, FI MU 7 IA102 "OU": Umění formulace Krátká formulace TSP Další moc hezký trik formulace úloh MIP je ukázán na zápise problému TSP polynomi- álně mnoha nerovnostmi. Přirozená formulace v Příkladu 11.9 vyžaduje exponenciální počet nerovností a pozdější objevení výrazně kratšího zápisu úlohy bylo docela velkým překvapením. Tvrzení 12.4. Problém obchodního cestujícího na orientovaném grafu G s n vrcholy a ohodnocením hran w : E(G) R+ lze vyjádřit následujícími polynomiálně mnoha nerovnostmi jako úlohu MIP s binárními proměnnými zi,j a reálnými ui: k = 1, 2, . . ., n : i:(i,k)E(G) zi,k = 1 k = 1, 2, . . ., n : i:(k,i)E(G) zk,i = 1 (i, j) E(G), i, j > 1 : ui - uj + n zi,j n - 1 (3) u 0 z {0, 1} Důkaz: Předpokládejme pro spor, že přípustné hodnoty proměnných zi,j = 1 nevyja- dřují v grafu G Hamiltonovský cyklus. Jelikož do každého vrcholu přichází jedna hrana se zi,j = 1 a jedna taková odchází, množina hran se zi,j = 1 je tvořena více cykly a alespoň jeden z nich, označme jej C, neprochází vrcholem 1. Sečteme-li nerovnosti (3) přes hrany cyklu C, proměnné ui se vyruší a vyjde |V (C)| n 1 (n - 1) |V (C)| , Petr Hliněný, FI MU 8 IA102 "OU": Umění formulace což je spor. Naopak máme dokázat, že každý Hamiltonovský cyklus C v G (tj. procházející přes všechny vrcholy) je přípustný. Nechť vrcholy G následují v cyklu C v pořadí v1 = 1, v2, v3, ..., vn. Položíme ui = l, kde i = vl (tj. podle pořadí na cyklu). Pak pro každou hranu (i, j) E(C), i, j > 1 platí ui - uj = l - (l + 1) = -1, takže ui - uj + n 1 -1 + n 1 = n - 1. Pro kteroukoliv jinou hranu přirozeně platí ui - uj + n 0 n - 1. Tím jsme dokončili důkaz správnosti formulace (3) pro problém TSP. 2 Poznámka: Naneštěstí se uvedená krátká formulace ukazuje jako velmi nevhodná k praktic- kému řešení problému TSP, neboť její lineární relaxace jen velmi hrubě aproximuje množinu přípustných celočíselných řešení. Proto má tento výsledek povětšinou jen teoretický význam. Petr Hliněný, FI MU 9 IA102 "OU": Umění formulace 12.3 Celočíselné polyedry Pro úvod začneme s přirozenou (a trochu upravenou) formulací problému toků v síti jako úlohy LP. Definice: A je vrcholově­hranová incidenční matice orientovaného grafu G, pokud její složky (indexované vrcholy × hranami) jsou ai,(i,j) = 1 pro (i, j) E(G), ai,(j,i) = -1 pro (j, i) E(G), ai,e = 0 jinak. Mějme síť (G, z, s, c), kde G je orientovaný graf, z zdroj, s stok a c udává kapacity jed- notlivých hran. (Definice 2.1) Doplňme graf G o "zpětnou" hranu ze stoku s do zdroje z bez omezení kapacity a přiřaďme proměnné x(i,j) tokům na jednotlivých hranách. Pak úlohu hledání maximálního toku zapíšeme jako: max x(s,z) : A I x = 0 c x 0 Definice: Polyedr P je celočíselný, pokud každá jeho neprázdná stěna obsahuje vektor se všemi celočíselnými složkami. Omezený polyedr P je celočíselný podle této definice, pokud každý jeho vrchol je vektorem s celočíselnými složkami. Petr Hliněný, FI MU 10 IA102 "OU": Umění formulace Fakt: Z celočíselnosti řešení Algoritmu 2.6 pro tok v síti v případě celočíselných kapacit c (nepřímo) vyplývá, že polyedr přípustných toků v dané síti je celočíselný. Uvedený fakt není náhodný, je ve skutečnosti jen speciálním případem šíršího fenoménu popsaného následně. Totálně unimodulární matice Definice: Řekneme, že matice A je totálně unimodulární (TU) pokud každá její čtver- cová podmatice má determinant 0, 1 nebo -1. Není těžké zjistit, že složky totálně unimodulární matice mohou být jen 0, 1 nebo -1, ale to není dostačující. Například jednotková matice I je totálně unimodulární a taková je třeba i matice -1 1 0 0 1 1 -1 1 0 0 0 1 -1 1 0 0 0 1 -1 1 1 0 0 1 -1 , která má mezi TU maticemi výsadní postavení, jehož význam přesahuje rámec našeho textu. Význam totálně unimodulárních matic v oblasti celočíselných mnohostěnů je naznačen následující vlastností, která přímo plyne ze známého "determinantového" vztahu pro inverzní matici. Petr Hliněný, FI MU 11 IA102 "OU": Umění formulace Fakt: Inverze regulární totálně unimodulární matice je celočíselná matice. Z uvedeného faktu a znalosti souvislosti bázických řešení LP s vrcholy polyedru (Lema 6.3) není těžké odvodit, že pro TU matici A a celočíselné b je polyedr ur- čený vztahy A x b, x 0 celočíselný. V obecnosti dokonce lze tvrdit (zde bez důkazu): Věta 12.5. Matice A je totálně unimodulární, právě když pro každé b Zm je polyedr určený vztahy A x b, x 0 celočíselný. Souvislost totálně unimodulárních matic s toky v sítích se ukáže následovně. Tvrzení 12.6. Nechť A je vrcholově­hranová incidenční matice orientovaného grafu G. Pak A je totálně unimodulární. Důkaz: Vezměme čtvercovou podmatici C v A. Tvrzení je jasné, pokud C má jediný sloupec. Dále postupujeme indukcí podle velikosti C. Pokud C je singulární, má determinant 0. Tato možnost mimo jiné nastává, pokud každý sloupec C obsahuje obě nenulové souřadnice (1 a -1) z příslušného sloupce matice A. Jinak najdeme sloupec v C mající právě jednu nenulovou souřadnici. Podle tohoto sloupce determinant rozvineme na jediný poddeterminant, jehož hodnota je 1 z indukčního předpokladu, tudíž to samé platí pro |C|. 2 Petr Hliněný, FI MU 12 IA102 "OU": Umění formulace Párování v grafu Mimo TU matice existují i další zajímavé případy celočíselných polyedrů vycházejících z grafových problémů. Jedním z nich je tzv. mnohostěn párování. Připomínáme, že párování v grafu je taková podmnožina hran, ve které žádné dvě hrany nesdílejí vrchol. Párování je perfektní, pokud obsahuje všechny vrcholy grafu. (Mimo jiné musí mít takový graf sudý počet vrcholů.) Definice: Nechť x {0, 1} je charakteristický vektor podmnožin hran grafu G. Mno- hostěn párování grafu G je konvexní obal všech takových charakteristických vektorů x, které odpovídají párováním v G. Mnohostěn perfektních párování grafu G je konvexní obal charakteristických vektorů perfektních párování v G. Vzpomeňme si na Příklad 11.4 ukazující IP formulaci problému párování v grafu. Je zřejmé, že pokud bychom k oné formulaci udělali LP-relaxaci, dostaneme mnohem více řešení než jen ta z mnohostěnu párování. Například ohodnocení všech proměnných hran na liché kružnici číslem 1 2 vyhovuje nerovnostem Příkladu 11.4, ale takové ohodnocení zřejmě nemá nic společného se skutečnými párováními. Jak vidíme při bližším pohledu, problémy dělají liché podmnožiny vrcholů indukující podgrafy s plně "nasycenými" ohodnocenými hranami, což je věc nemožná pro skutečné párování grafu. Petr Hliněný, FI MU 13 IA102 "OU": Umění formulace Věta 12.7. Mnohostěn perfektních párování grafu G s n vrcholy je vyjádřen následu- jícími vztahy: i = 1, 2, . . ., n : eE(G): e={i,j} xe = 1 (4) W V (G), |W| liché : eE(G): e={i,j}W xe |W|/2 (5) x 0 Mnohostěn párování grafu G je vyjádřen stejnými vztahy, jen vztah (4) je zapsán s nerovností místo =. Důkaz (náznak): Nejprve si krátce ukažme, jak z platnosti věty pro perfektní párování plyne její platnost pro všechna párování: .................... Nyní dokážeme, že vztahy (4),(5) plně popisují mnohostěn perfektních párování grafu G. V jednom směru potřebujeme dokázat, že každé perf. párování splňuje vztahy (4) a (5). Pro (4) to platí z definice perf. párování. Pokud W je lichá podmnožina vrcholů, tak aspoň jeden z vrcholů musí zůstat uvnitř W nespárovaný, a proto plyne (5). Naopak vezměme vektor x, který splňuje výše uvedené vztahy a zároveň je krajním bodem mnohostěnu perfektních párování. Předpokládejme pro spor, že x není celočí- selný. Hranám e grafu G, které mají necelé hodnoty xe, říkejme šedé hrany. Pro šedou kružnici C sudé délky v G nazveme -alternací x takové ohodnocení x , které na i-té hraně v pořadí na kružnici C nabývá x ei = xei + (-1)i a mimo C zůstává stejné jako x. Petr Hliněný, FI MU 14 IA102 "OU": Umění formulace Tvrzení 12.8. Za výše uvedených předpokladů v G existuje sudá šedá kružnice C a konstanta > 0 takové, že všechny -alternace C jsou přípustné ve vztazích (4),(5) pro - < < . Tvrzení dokazujeme indukcí podle n, použitím kontrakcí lichých "nasycených" pod- množin. . . Nyní již snadno dokončíme důkaz celé věty. Vektor x je totiž konvexní kombinací svých -alternace a --alternace, které jsou přípustné v úloze pro dostatečně malé > 0. To je ale ve sporu s předpokladem, že x je krajním bodem polyedru. 2 Petr Hliněný, FI MU 15 IA102 "OU": Umění formulace Mnohostěn perfektního grafu Jiný známý příklad kombinatorických celočíselných mnohostěnů vychází z popisu klik v jistých grafech. Připomínáme, že klika v grafu je jiný název pro inkluzí maximální úplný podgraf. Definice: Graf G je perfektní, pokud v každém jeho indukovaném podgrafu je barevnost rovna velikosti největší kliky. Nepleťme si pojem perfektního grafu s perfektním párováním, není mezi nimi žádná souvislost. Příklady perfektních grafů jsou bipartitní grafy (barevnost 2), intervalové grafy (určené průniky intervalů na přímce), nebo tzv. chordální grafy (bez indukovaných kružnic delších než 3). Definice: Nechť K je incidenční matice klik a vrcholů perfektního grafu G. (Tj. Ki,j = 1 právě když vrchol j náleží do i-té kliky.) Pak mnohostěn perfektního grafu G je určený vztahy K x 1 x 0 . Věta 12.9. Mnohostěn perfektního grafu je vždy celočíselný. Petr Hliněný, FI MU 16 IA102 "OU": Umění formulace 12.4 Neúplné formulace úloh MIP Iterativní vylepšování formulace MIP novými podmínkami na základě předchozích re- laxovaných řešení......... Petr Hliněný, FI MU 17 IA102 "OU": Umění formulace