Bakalářka: Binární paint shop problém
Also available as: PDF Markdown Pictures (ZIP)
Obsah
Úvod
V této práci představíme binární paint shop problem. Jedná se o úlohu, kterou neumíme efektivně řešit (protože je úplná) a ani aproximovat (za předpokladu Unique games conjecture je konstantní aproximace také těžká), takže mimo jiné probíhá aktivní výzkum snažící se najít algoritmus, který je dobrý v průměrném případě (pro náhodný vstup).
Zadání
Zadání binárního paint shop problému (dále těž BPS) je následující:
Úloha (Binární paint shop): V řadě je aut různých typů – od každého typu dvě. Chtěli bychom od každého typu nabarvit jedno auto červeně a druhé modře. Auta však na barvicí linku vjíždí v pořadí, v jakém jsou v řadě. Barvicí linka je optimalizovaná na barvení velkého počtu aut jednou barvou. Tedy měnit barvu, kterou se barví, je složitá a drahá záležitost. Chceme tedy najít obarvení aut tak, aby od každého typu bylo jedno červené a jedno modré, přitom počet změn barev v řadě byl co nejmenší.
Počet změn barev řešení považujeme za skóre algoritmu. Relativní skóre pak je poměr skóre a počtu typů aut.
Problém můžeme chápat buď jako optimalizační problém, kde účelová funkce je počet změn v řešení a snažíme se ji minimalizovat, nebo jako rozhodovací problém, kde se ptáme, jestli existuje řešení s nejvýše nějakým zadaným počtem změn.
Cíle práce
Naším cílem bude najít co nejlepší algoritmus řešící BPS a odhadnout u něj střední hodnotu skóre pro náhodný vstup. Dále se pokusíme porovnat již známé algoritmy.
Struktura práce
Nejprve zavedeme notaci potřebnou pro pohodlnou práci s BPS a definujeme aproximační algoritmy. Kapitola 2 obsahuje shrnutí doposud známých algoritmů a jiných výsledků ohledně BPS. V kapitole 3 je představen princip semidefinitního programování, které má uplatnění v algoritmu představeném o kapitole 4. Kapitola 5 se věnuje praktické implementacím algoritmů a naměřeným datům o nich.
Notace
Auta budeme indexovat od do a typy od do .
Pomocí budeme značit pozici prvního auta typu a pomocí pozici druhého.
Opačně bude značit typ auta na pozici a bude značit, jestli se jedná o první nebo druhé auto daného typu (tedy bude nabývat hodnoty nebo ).
Protože někdy bude výhodnější zacházet se znaménky, zavedeme , které bude nabývat hodnot a . Také rozšíříme notaci o .
Nakonec ještě zavedeme zkratku indexu druhého auta stejného typu jako je auto na pozici : .
Barvy pro nás budou a . Pokud budeme uvažovat nějaké konkrétní obarvení , tak bude značit barvu auta na pozici .
Pro algoritmus označíme skóre na vstupu pomocí . Dále označme všechny vstupy délky jako . Průměrné skóre algoritmu na všech vstupech délky tedy bude Tuto hodnotu mimo jiné můžeme chápat jako střední hodnotu skóre pro uniformně náhodný vstup délky . K tomu ještě zavedeme notaci pro relativní skóre a analogicky průměrné relativní skóre . Nakonec označme . Protože limita nemusí vždy existovat, zavedeme ještě limes superior a limes inferior: a . Význam těchto definic bude vysvětlen v následující kapitole.
Dále označme optimální skóre na vstupu . A následně analogicky definujeme , , a stejně jako u variant s algoritmem, jen skóre daného algoritmu nahradíme za optimální skóre.
Definice aproximačních algoritmů
Protože ne pro všechny problémy známe polynomiální algoritmus, který je schopný je vyřešit, zajímavý výsledek může být, i když se k řešení zvládneme jen v nějakém smyslu alespoň přiblížit. Na to nejprve musíme říct, co pro nás znamená, že nějaké řešení je několikrát horší než jiné. To nám poskytne obecná definice optimalizačního problému.
Definice (Optimalizační problém): Problém je optimalizační, pokud pro každý vstup , existuje množina přípustných řešení . Dále existuje účelová funkce , která pro každý vstup a jeho přípustné řešení určuje reálné nezáporné číslo – jeho hodnotu.
Pokud se jedná o minimalizační problém, tak pod pojmem optimum daného vstupu (značíme ) myslíme infimum hodnot účelové funkce přes všechna přípustná řešení, tedy . Pro maximalizační problém analogicky použijeme supremum.
A nyní již přejdeme k samotným definicím algoritmů blížících se optimu.
Definice (Aproximační algoritmus): Algoritmus je -aproximační na minimalizačním problému, pokud pro každý vstup algoritmus vrátí přípustné řešení , pro které platí, že .
Předešlá definice záleží na tom, co považujeme za velikost vstupu, což se pro různé problémy a jejich interpretace liší. Naštěstí nás většinou budou zajímat -aproximace, tedy aproximace, kde je konstantní funkce rovna .
U maximalizačních problémů je drobný problém v terminologii, protože není shoda na tom, jestli má platit nebo . Naštěstí podle kontextu jde snadno rozhodnout, která definice se používá, protože je potřeba násobit optimum číslem menším rovno jedné (jinak by pro kladné hodnoty účelové funkce nemohl existovat žádný vyhovující algoritmus).
Bohužel někdy asi ani s aproximačními algoritmy nevystačíme a proto zavedeme pravděpodobnostní relaxaci.
Definice (Pravděpodobnostní aproximační algoritmus): Náhodný algoritmus je pravděpodobnostně -aproximační na minimalizačním problému, pokud pro každý vstup algoritmus vždy vrátí přípustné řešení , pro které platí, že .
Snadným důsledkem definice (a Markovovy nerovnosti) je, že pro každé pravděpodobnostně -aproximační algoritmus vrátí s pravděpodobností zdola omezenou konstantou řešení s hodnotou nejvýše .
Všimněme si, že na hodnotě příliš nezáleží. Opakovaným spouštěním algoritmu a pak vybráním nejlepšího z dodaných řešení zvládneme pravděpodobnost libovolně těsně přiblížit k jedné.
Pokud řešíme složitost algoritmů a úloh, většinou vyžadujeme, aby účelová funkce i rozhodování přípustnosti řešení byly vyčíslitelné v polynomiálním čase. Navíc chceme, aby všechna přípustná řešení měla délku omezenou nějakým polynomem v délce vstupu. Snadno nahlédneme, že za takovýchto podmínek je rozhodovací verze, jestli je optimum alespoň zadané číslo, v . Pro takovou úlohu většinou hledáme polynomiální aproximační algoritmus. Binární paint shop vyhovuje všem těmto podmínkám.
Pokud existuje -aproximační algoritmus pro každé , říkáme, že máme aproximační schéma.
Doposud známé výsledky
Bonsmaa, Epping a Hochstättler [1] dokázali, že optimalizační verze BPS je -těžký problém, což je silnější tvrzení, než že rozhodovací verze je -těžká. Za předpokladu víme, že kromě polynomiálního algoritmu na rozhodovací verzi nemůže existovat ani polynomiální aproximační schéma na optimalizační verzi.
Snadno nahlédneme, že rozhodovací problém patří do . Když nám někdo dá přiřazení barev autům, v lineárním čase jsme schopni ověřit, že počet změn je dostatečně malý a od každého typu a barvy auta je právě jeden výskyt. Tedy rozhodovací problém je -úplný.
Dále pak Gupta a spol. [2] ukázali, že za předpokladu Unique games conjecture je NP-těžké i problém libovolně konstantně aproximovat. K tomu využili převod na problém minimálního ne-řezu. To je problém podobný maximálnímu řezu, který bude představen později. Ovšem místo maximalizace počtu hran v řezu minimalizujeme počet hran mimo něj (tedy v rámci partit). Tyto dva problémy mají stejné optimum, ovšem aproximovatelnost se na nich chová drasticky jinak. V momentě, kdy jsou skoro všechny hrany v řezu, tak přidání další hrany do řezu skoro nezmění počet hran v něm. Ovšem odebrání hrany z ne-řezu bude mít velký vliv (procentuálně) na počet hran v ne-řezu.
Vzhledem k předešlým výsledkům je na místě zkoumat různé heuristiky a obecně algoritmy, co jsou nás schopny k optimálnímu řešení alespoň částečně přiblížit.
Jedním z takových algoritmů je hladový algoritmus popsaný Andresem and Hoch-stättlerem [3]:
Algoritmus (Hladový algoritmus, g): Autům budeme přiřazovat barvy v pořadí, v jakém jsou na vstupu. První auto v řadě obarvíme řekněme červeně. Dále budeme vždy první auto daného typu barvit stejně jako předcházející auto a druhé auto daného typu obarvíme vždy zbývající barvou.
V daném článku autoři o tomto algoritmu dokázali, když vezmeme uniformně náhodný vstup délky , tak střední hodnota počtu změn ve vygenerovaném řešení je .
Hladový algoritmus budeme značit , tedy předešlou hodnotu značíme . Připomeňme, že pomocí značíme tuto hodnotu vydělenou velikostí vstupu, tedy .
Pro dostatečně velká se pohybuje zhruba okolo (formálně řečeno: platí, že ) (viz obrázek
U hladového řešení je tedy střední hodnota skóre přes uniformně náhodný vstup přesně vyčíslená. Pro nás je zejména důležité, že jsme ji schopni shora odhadnout. Střední hodnotu totiž můžeme považovat za ukazatel kvality algoritmu (čím menší je, tím se jedná o lepší algoritmus) a tedy horní odhad nám dává záruku kvality algoritmu.
Zajímavé je pro nás zkoumat chování algoritmů na velkých vstupech, tedy dává smysl uvažovat limitu střední hodnoty do nekonečna. Ovšem s narůstajícím počtem aut narůstá i počet potřebných změn, takže samotná limita střední hodnoty moc nedává smysl, protože by byla nekonečná. Místo ní budeme uvažovat . O ní víme, že pro libovolný algoritmus (pokud existuje) bude v intervalu , protože maximální počet změn musí být mezi a .
I když nejsme schopní hledat optimum efektivně, pro každý vstup je určitě optimum dobře definovaná hodnota. Můžeme se tedy ptát na otázku, kolik vyjde limita, kde místo skóre algoritmu vložíme optimum pro daný vstup, tedy . Označme hodnotu této limity .
Bohužel není zřejmé, že limita skutečně existuje, proto místo limity budeme často uvažovat limes supervisor a inferior. Ty budeme značit přidáním jako horního indexu. Stejnou notaci budeme používat i u limit algoritmů.
Jelikož optimum musí být alespoň tak dobré jako výstup hladového řešení, dostáváme konstruktivní horní odhad . Hledáním lepších algoritmů můžeme horní odhad zlepšovat.
Překvapivě však je, že Hančl a kol. [4] ukázali dolní odhad pomocí počítání pravděpodobností pro náhodné obarvení. Samotný fakt, že je již poměrně zajímavé tvrzení. To nám říká, že každý algoritmus na průměrném vstupu musí použít aspoň změn barev. Nemůže tedy například existovat algoritmus, kterému by stačilo jen změn. To také říká, že odhadovat algoritmy pomocí , je alespoň co se týče asymptotiky dostačující, protože vystihuje konstantu nejvýznačnějšího členu polynomiální aproximace.
Dále si představíme několik algoritmů, které se snaží konstruktivně zlepšit horní odhad na .
Algoritmus (Rekurzivní hladové řešení, rg): Z řady aut odstraníme první auto v řadě a druhé auto příslušného typu. Zbytek aut rekurzivně obarvíme a pak do řady přidáme odebranou dvojici tak, aby byl počet změn co možná nejmenší možný.
Autoři algoritmu, Andres and Hochstättler [3], o něm dokázali, že , tedy .
Dále se o zlepšení tohoto algoritmu pokusili Hančl a kol. [4]. Ti si všimli, že ve výstupu rekurzivního řešení se občas stane, že přebarvením dvojic typů aut se zlepší skóre. Ukázali, že takových dvojic je vždy ve výstupu lineárně mnoho a z toho pak ukázali horní odhad (pro zhruba ).
Hančl a kol. [4] přišli ještě s dalším způsobem, jak vylepšit rekurzivní hladové řešení. Při běhu hladového řešení se občas stane, že některá dvojice aut stejného typu si může prohodit barvy bez změny skóre řešení. Když přidáváme auto do okolí takovéto dvojice, v některých případech můžeme provést toto prohození a tím snížit počet nově vytvořených změn barev. Budeme si tedy udržovat některé z takovýchto dvojic a pokud budeme přidávat auto do okolí evidované dvojice tak, že prohození barev dané dvojice by pomohlo, prohodíme její barvy.
Budeme pracovat nad rozšířenou abecedou barev o znak „“ reprezentující neurčenou barvu. Při rekurzi budeme udržovat invariant, že pro každý typ obě auta buď budou označena a nebo ani jedno z nich nebude označeno a pak nutně budou mít různé barvy. Navíc bude platit, že nikdy není na okrajích a nejsou dvě vedle sebe. Specificky tedy na budeme přebarvovat dvojici aut v momentě, kdy získá všechny sousedy.
Pro popis algoritmu zavedeme notaci , což bude reprezentovat multimnožinu barev aut sousedících s autem na pozici , tedy .
Algoritmus (Hvězdičkové rekurzivní řešení, rsg): Budeme pracovat nad rozšířenou škálou barev . Ze vstupu odebereme auta typu a zarekurzíme se na zbytek. Tím získáme nějaké obarvení, které může použít na původní vstup s tím, že auta typu zatím nebudou obarvená, ty dobarvíme dle následujících pravidel:
- Když a nastavíme .
- Když nastavíme .
- Když pro nějaké , nastavíme i .
- Když , nastavíme .
- Když , nastavíme .
- Když , nastavíme a přenastavíme v okolí na a druhé auto daného typu na opačnou barvu.
A druhé auto typu obarvíme zbývající barvou.
Pokud auta typu spolu nesousedí, a prohození barev aut typu by zachovalo počet změn, přenastavíme jejich barvy na .
Po návratu ze všech rekurzí zbylé dvojice aut přebarvíme na dvě různé barvy.
Autoři algoritmu o něm vyslovili domněnku, že .
Na obrázku
Zobecněné verze a související problémy
Zobecněním binárního paint shopu je obecný paint shop problém, zavedený Eppingem a spol. [5]. Z něj pochází motivace k binární verzi.
Úloha (Obecný paint shop problém): V řadě je aut různých typů – nyní však již od každého typu libovolný počet. Dále máme definováno pro každou kombinaci typu a barvy (kterých také může být více než dvě), kolik aut daného typu má být nabarveno na danou barvu. Chceme tedy najít obarvení aut tak, aby počet změn barev v řadě byl co nejmenší.
Binární verze problému je tedy speciální případ obecného paint shop problému, kde od každého typu máme dvě auta, máme jen dvě požadované barvy a navíc platí, že pro každou kombinaci typu a barvy chceme právě jedno auto.
Souvisejícím problémem je dělení náhrdelníku zavedený v Alonově článku [6]:
Úloha (Dělení náhrdelníku): Skupina loupežníků uloupí náhrdelník skládající se z drahokamů různých typů. Pro každý typ platí, že náhrdelník obsahuje právě drahokamů daného typu (pro nějaké celé ). Loupežníci si jej chtějí férově rozdělit. Náhrdelník tedy rozdělí na několik navzájem nepřekrývajících se intervalů, jejichž sjednocení je celý náhrdelník. Každý z intervalů pak přiřadí nějakému loupežníkovi tak, aby každý loupežník získat od každého typu právě drahokamů (což znamená, že všichni budou mít od každého typu stejný počet drahokamů). Chceme minimalizovat počet intervalů, na které je nutné náhrdelník rozdělit.
Nejprve si všimněme, že dělení náhrdelníku je speciálním případem obecného paint shop problému. Auta pro nás budou drahokamy. Barva auta bude označovat, který loupežník získá daný drahokam. Minimalizovat počet intervalů je to stejné jako minimalizovat počet hranic mezi nimi (kterých je o jedna méně něž intervalů). Ve vstupu problému dělení náhrdelníku navíc musí platit, pro každý typ má být stejný počet aut obarvený jednotlivými barvami (a tedy počet aut daného typu musí být násobkem ). Naopak binární paint shop problém je speciálním případem dělení náhrdelníku pro dva lupiče, kde navíc platí, že všechna jsou 1 (tedy od každého typu jsou na náhrdelníku právě dva drahokamy).
Semidefinitní programování
V této kapitole si představíme princip semidefinitního programování (dále též SDP), jak jej popisují Gärtner a Matoušek [7], a jeho použití na problém maximálního řezu, z něhož vychází algoritmus na binární paint shop.
Nejprve zavedeme a připomeneme notaci důležitou v této kapitole. Nechť značí množinu -řádkových -sloupcových matic složených z reálných čísel. Řádky i sloupce indexujeme od , tedy matice obsahuje prvky pro všechna a . Nechť je třída všech symetrických matic a nechť značí součet součinu matic po složkách. Nakonec bude značit skutečnost, že matice je pozitivně semidefinitní (bude vysvětleno později).
Úloha semidefinitního programování je optimalizační úloha (podobně jako lineární programování) následujícího formátu:
Vstupem programu tedy je velikost matice , počet podmínek a pak pro každou podmínku matice a číslo . Výstupem je pak splňující výše uvedené podmínky.
Pro nás bude důležitý následující fakt z lineární algebry:
Fakt: Nechť . Následující tvrzení jsou ekvivalentní definice pozitivně semidefinitní matice:
- Všechna vlastní čísla matice jsou nezáporná.
- Pro každý vektor platí .
- Existuje matice taková, že .
Pro nás bude důležitá zejména třetí podmínka, protože navíc platí, že ze semidefinitní matice zvládneme zkonstruovat v čase pomocí tzv. Choleského dekompozice.
Navíc pro libovolnou reálnou matici je symetrická. Tedy semidefinitní programování můžeme chápat jako optimalizační úlohu na . Pojďme se zamyslet nad tím, co v takovémto pohledu znamenají podmínky a účelová funkce. Matici můžeme považovat za sloupcových vektorů vedle sebe. Matice pak odpovídá těmto vektorům zapsaných v řádcích pod sebou. Matice tedy na pozici obsahuje skalární součin vektorů a . Účelová funkce tedy je lineární kombinací skalárních součinů a podmínky odpovídají vynucení rovnosti lineární kombinace skalárních součinů vektorů a konstanty. Speciálně tedy můžeme mít podmínku na délku vektoru: . Semidefinitní programování v tomto tvaru budeme nazývat semidefinitní programování v dekomponovaném tvaru.
Maximální řez
Představíme si pravděpodobnostní aproximační algoritmus založený na semidefinitním programování na následující problém:
Úloha: Nechť je graf s hranami ohodnocenými nezápornými čísly dle . Řezem grafu rozumíme rozdělení vrcholů na dvě disjunktní množiny . Hodnotou daného řezu je pak součet cen hran vedoucích mezi a . Tedy: Cílem je maximalizovat hodnotu řezu.
Problém maximálního řezu (resp. rozhodovací verze, kde se ptáme na existenci řezu alespoň dané velikosti) je NP-úplný [8], proto se u něj zkoumají aproximační algoritmy a pravděpodobnostní aproximační algoritmy.
Nejprve si ukážeme triviální pravděpodobnostní -aproximační algoritmus:
Algoritmus: Každý vrchol uniformně náhodně přiřaď do množiny nebo .
Věta: Triviální algoritmus je pravděpodobnostní -aproximační algoritmus.
Důkaz: Každá hrana bude v řezu s pravděpodobností – při umisťování druhého vrcholu dané hrany máme pravděpodobnost , že ho umístíme do stejné množiny a tedy hrana nebude součásti řezu a pravděpodobnost že do opačné a tedy bude součástí řezu. Součet hran v řezu je součtem indikátorů jevů přítomnosti jednotlivých hran v řezu vynásobený jejich hodnotou. Z linearity střední hodnoty tedy střední hodnota součtu vah hran v řezu je celkového součtu vah hran, což je alespoň optima. QED
Povšimněme si, že triviální algoritmus dosáhl poměrně zajímavého aproximačního poměru a to se ani nedíval na vstup.
Předešlý algoritmus lze derandomizovat, jak popisuje Dimitrakakis [9]. Výsledný algoritmus pak vždy najde řešení obsahující alespoň hran, tedy alespoň optima.
Lepšího aproximačního poměru dosáhneme Goemansovým-Williamsonovým algoritmem, založeným na semidefinitním programování a proto popsaným mimo jiné v již dříve zmíněném úvodu do semidefinitního programování [7].
Naivní implementace je, že si pro každý vrchol vyrobíme proměnnou , která může nabývat hodnot , která bude říkat, do jaké množiny máme vrchol umístit. Do účelové funkce pak zakódujeme graf. Účelová funkce bude kde značí součet hodnot všech hran. Pro každou hranu tedy přičte , pokud a mají různá znaménka, a , pokud stejná.
Takovýto optimalizační problém bohužel ani pomocí semidefinitního programování neumíme řešit. Na to, abychom uměli vyjádřit nějaký součin, musíme použít semidefinitního programování v dekomponovaném tvaru. Pak ale místo toho, abychom měli pro každý vektor jen jednu proměnnou, budeme mít pro každý vrchol celý vektor proměnných a místo součinu proměnných budeme mít skalární součin těchto vektorů. Již ale současně neumíme zařídit, aby tyto vektory byly buď nebo . Můžeme ale přidat podmínku na to, aby délka každého vektoru byla . Tím jsme vyrobili relaxaci výše uvedeného programu, protože za těchto podmínek může vektor nabývat i jiných poloh než . Celý algoritmus pak vypadá následovně:
Algoritmus (Goemansův-Williamsonův): Vyřešíme následující semidefinitní program v dekomponovaném tvaru: Dále uniformně náhodně zvolíme jednotkový vektor vektor a do jedné množiny vybereme právě ty vrcholy , pro které .
Semidefinitní program v algoritmu si lze představit jako umísťování bodů na dimenzionální sféru v . Účelová funkce se snaží umístit body vrcholů spojených hranou co nejdále od sebe.
V případě, kdy jsme povolovali pouze hodnoty , bylo jasné, které vrcholy patří do které množiny.
Nyní však výstupem optimalizace jsou vektory a tedy přiřazení množinám není tak jednoznačné.
Rádi bychom umístili od sebe vzdálené body do různých množin.
Na to můžeme rovnoměrně náhodně zvolit nadrovinu
procházející počátkem a rozdělit body
do množin podle toho, do které z polorovin určených danou nadrovinou patří.
To nám zaručí, že dvojice bodů daleko od sebe budou mít velkou pravděpodobnost toho, že budou v různých poloprostorech. Semidefinitní programování se tedy snaží dostat dvojice bodů odpovídající vrcholům spojených hranou daleko od sebe a podle toho se zvyšuje pravděpodobnost toho, že vrcholy budou v jiných množinách a tedy hrana bude v řezu.
Výběr nadroviny a rozdělování bodů jde implementovat pomocí výběru vektoru kolmého na nadrovinu. Pro každý bod pak stačí spočítat skalární součin se a podle znaménka víme, do kterého poloprostoru patří. Pokud vybereme uniformně náhodný jednotkový vektor, tak jsme uniformně náhodně vybrali nadrovinu. Jednotkový vektor můžeme generovat tak, že vygenerujeme náhodný vektor nezávisle po složkách z normálního rozdělení, a pak ho znormujeme. Povšimněme si, že normalizace ani není potřeba, protože to na znaménku součinů nic nemění.
Nyní pojďme precizněji spočítat pravděpodobnost toho, že se dvojice bodů (vektorů) ,
rozdělí náhodnou nadrovinou v závislosti na hodnotě skalárního
součinu mezi nimi.
Můžeme se podívat na rovinu, ve které leží počátek a oba vektory , (viz obrázek
Zajímá nás tedy, jaká je pravděpodobnost toho, že jedno z ramen nadroviny bude uvnitř konvexního úhlu mezi a . Velikost tohoto úhlu označme . Víme, že . Náhodnou přímku můžeme vygenerovat jako náhodný úhel mezi a s tím, že přímka pak povede směrem a . Nikdy však uvnitř konvexního úhlu nebudou obě ramena přímky, tedy pravděpodobnost, že alespoň jedno bude uvnitř a tedy body budou oddělené je:
U každé hrany optimalizujeme , což je ekvivalentní optimalizování .
Nyní se podívejme na poměr mezi pravděpodobností toho, že hrana bude v řezu, a účelovou funkcí před vynásobením hodnotou hrany jakožto funkci proměnné v intervalu :
Fakt: Pro každé platí:
Označme tuto hodnotu .
Tedy když je účelová funkce dané hrany , tak pravděpodobnost výběru hrany do řezu bude alespoň . Sečtením přes všechny hrany (z linearity středních hodnot) tedy získáme, že střední hodnota součtu hran v řešení je alespoň , kde , tedy jedno z ekvivalentních vyjádření účelové funkce.
Pokud tedy najdeme dobré řešení semidefinitního programu, ve střední hodnotě pak najdeme i dobré řešení maximálního řezu. Dále však musí platit, že optimální řešení semidefinitního programu je alespoň součet hran optimálního řešení maximálního řezu, když za účelovou funkci považujeme . Jedno z možných řešení totiž snadno sestrojíme z maximálního řezu: Vrcholům jedné množiny přidělíme vektory a druhé . Účelová funkce pak přičte za každou hranu v řezu a jinak.
Bohužel na rozdíl od lineárního programování, u semidefinitního programování nejsme schopní v polynomiálním čase najít optimální řešení. Naštěstí však platí, že v polynomiálním čase za určitých podmínek jsme schopní se mu libovolně přiblížit. Přesněji řečeno, pro každé jsme schopní najít řešení s účelovou funkcí nejdále od optima. Ovšem musí platit, že všechna přípustná řešení jsou dostatečně malá. Přesněji řečeno, musí platit, že Frobeniova norma všech přípustných matic je omezena konstantou s polynomiální délkou zápisu. Tohoto výsledku jde dosáhnout pomocí elipsoidové metody, která má nejlepší teoretické výsledky. V praxi se však často používají jiné algoritmy. Všechny naše programy budou splňovat podmínky na řešení, protože každá z hodnot hledané matice nutně bude ležet v intervalu .
Věta: Goemansův-Williamsonův algoritmus je pravděpodobnostní -aproxi-mační algoritmus.
Důkaz: Využitím předešlých pozorování a elipsoidové metody získáme (MC značí max cut, tedy maximální řez): Pro dostatečně malé se tedy jedná o pravděpodobnostní -aproximační algoritmus. QED
Řešení semidefinitním programováním
Řešení vychází z Goemansova-Williamsonova algoritmu na maximální řez. Pro každé auto nám bude semidefinitní program umísťovat bod (někdy také chápán jako vektor) na jednotkovou sféru. Poté náhodně rozřízneme nadrovinou sféru na dvě poloviny a podle toho, do které poloviny auto patří, zvolíme jeho barvu.
Rozdílné barvy aut stejného typu zařídíme tak, že vynutíme . Na to nám stačí jediná podmínka – říct, že jejich skalární součin je .
Účelovou funkcí pak řekneme, že sousední auta mají preferovat stejnou barvu, tedy jejich body na sféře mají být blízko sebe, což znamená, že skalární součin má být co největší.
Algoritmus (Řešení pomocí semidefinitního programování, sdp): Vyřešíme následující semidefinitní program v dekomponovaném tvaru: Dále uniformně náhodně zvolíme jednotkový vektor a červeně obarvíme právě ty auta , pro která . Náhodných výběrů vektoru je možné provést vícero a pak vybrat nejlepší nalezené řešení.
Pro každou dvojici do účelové funkce přičteme číslo mezi a , kde značí, že vektory jsou stejné, a , že jsou protilehlé. Účelovou funkci můžeme ekvivalentně zapsat jako
Nyní tedy pro každou dvojici sousedních aut přičítáme číslo mezi a , kde přičteme pro stejné vektory, mezi nimiž nikdy nebude změna barvy a přičteme v případě opačných vektorů, mezi nimiž se nutně barva změní. Účelovou funkci se snažíme minimalizovat.
Věta: Optimum semidefinitního programu, který minimalizuje účelovou funkci je menší rovno počtu změn v optimálním obarvení aut.
Důkaz: Podíváme se na optimální obarvení aut a každému červenému autu přiřadíme vektor a modrému . Toto je validní řešení semidefinitního programu. Účelová funkce za každou změnu barev přičte a zbytek součtu je , takže její hodnota je přesně počet změn barev. QED
Nyní by se hodilo odhadnout střední hodnotu počtu změn barev stejně jako u maximálního řezu.
Jeho důkaz vycházel z pozorování ohledně poměru pravděpodobností výběru a účelové funkce,
přesněji řečeno z toho, že tento poměr umíme zdola odhadnout.
Ovšem v našem případě místo maximalizace děláme minimalizaci účelové funkce a pravděpodobnosti.
Tedy abychom mohli tvrdit, že pravděpodobnost je menší než nějaký násobek účelové funkce,
potřebovali bychom horní odhad poměru. Ovšem tento poměr je neomezený (viz obrázky
O binárním paint shop problému je navíc známé, že je za předpokladu Unique game conjecture a je polynomiálně neaproximovatelný s konstantním faktorem [2], takže nemožnost výše uvedeného postupu by nás ani neměla zaskočit, protože v případě, že by šlo udělat odhad tímto způsobem, získali bychom pravděpodobnostní aproximační algoritmus.
Místo toho se podíváme na rozdíl pravděpodobnosti a účelové funkce.
Lemma: Pro každé platí:
Důkaz: Jedná se o spojitou funkci na kompaktním intervalu, takže maximum a minimum může nabývat jen v krajních bodech a v místech s nulovou derivací. V obou krajních bodech je však její hodnota , zbývá tedy prověřit nulové derivace. Zderivováním získáme:
což má dva kořeny , a hodnota v nich je přibližně . QED
Označme konstantu z předchozího lemmatu jako .
Věta: Střední hodnota (vzhledem k náhodným bitům generovaným algoritmem) počtu změn v řešení je nejvýše o horší než optimum.
Důkaz: Když účelová funkce pro sousední dvojici aut je , tak pravděpodobnost změny barev je nejvýše . Sečtením přes všechny hrany (z linearity středních hodnot) tedy získáme, že střední hodnota součtu změn je nejvýše , kde , tedy jedno z ekvivalentních vyjádření účelové funkce.
Celkově tedy víme:
Pro vhodně zvolené jsme tedy dokázali požadovanou vzdálenost od optima. QED
Na rozdíl od jiných řešení binárního paint shop problému, zde se jedná o střední hodnotu přes náhodné rozhodnutí algoritmu, nikoliv přes náhodnou distribuci na vstupech. Tedy když spustíme algoritmus na konkrétní instanci, dostaneme řešení a také dolní odhad na optimalní řešení dané instance (ten jednak můžeme odvodit z hodnoty řešení ale také přímo z účelové funkce semidefinitního programu).
Implementační zjednodušení
Předchozí semidefinitni program ještě lze nepatrně zjednodušit se zachováním všech potřebných vlastností. Místo toho, abychom měli vektor pro každé auto, uděláme si jen vektor pro každou dvojici aut stejného typu. Ten bude odpovídat řekněme prvnímu autu z dvojice. Všimneme si, že účelovou funkci zvládneme stále vyjádřit. Kdykoliv jsme používali vektor druhého auta, stačí použít mínus vektor prvního auta. Tedy stačí některé členy jednou až dvakrát vynásobit hodnotou .
Výsledný program vypadá takto:
Výhodou je, že je potřeba poloviční počet proměnných, matice je čtvrtinová a odebrali jsme podmínek, proto v implementační části práce využijeme této formy programu.
Měření řešení BPS
Součástí práce je implementace algoritmů řešících Binární paint shop problém.
Každý z nich byl následně spuštěn pro různé velikosti, pokaždé na nezávisle náhodně vybraných vstupech s počtem typů aut
10, 20, 50, 100, 200, 400, 566, 800, 1131, 1600, 2263 a 3200.
Pro reprodukovatelnost byly vstupy generovány deterministicky ze seedů. Se stejným seedem se tedy vždy vygeneruje stejný vstup a ideálně i stejné řešení. Pro různé algoritmy a velikosti vstupů byly použité různé seedy.
Praktické řešení semidef. programů
U většiny algoritmů byla implementace poměrně přímočará. Ovšem u řešení semidefinitního programování je většina složitosti algoritmu schovaná právě v řešení semidefinitních programů, což už svojí složitostí nepatří mezi algoritmy, které bychom chtěli (re)implementovat. Proto je žádoucí se spolehnout na funkčnost již existujících implementací. Bohužel kvalita dostupných řešičů semidefinitních programů je poměrně nízká.
SDPA-C
Jedním z použitých programů byl SDPA-C [10].
Jedná se o knihovnu v C++
založenou na metodě vnitřních bodů v primárním a duálním problému. Dle autorů projektu [10]:
SDPA (SemiDefinite Programming Algorithm) is one of the most efficient and stable software packages for solving SDPs based on the primal-dual interior-point method. It fully exploits the sparsity of given problems.
Pro účely práce byla použita verze SDPA-C ze dne 2023-06-21 (soubor sdpa-c.7.3.8.src.20180125.tar.gz
).
Kompilace je poměrně komplikovaná.
Jednak vyžaduje velké množství nainstalovaného software (například překladač Fortranu), ale také poskytnutý Makefile
není plně kompatibilní s moderními verzemi překladačů.
Bohužel i po úspěšné kompilaci stále není vyhráno. Dodaný program přeložený aktuálním kompilátorem bohužel nefunguje.
Při spuštění i na malých vstupech program rychle spadne s chybou Segmentation Fault
ve funkci Newton::compute_bMatgVec_dense_threads_SDP
.
Při následujícím ladění programu bylo zjištěno, že se program zacyklí v dané funkci ve smyčce, při které inkrementuje hodnotu proměnné
Column_Number
až do doby, kdy přeteče, což už přímo vede k pádu programu.
Pohledem na kód to vypadá, že toto by se nemělo dít.
Program už mnohokrát měl ukončit smyčku a doběhnout na konec funkce, ovšem po přidání dostatečného počtu debugovacích výpisů
je vidět, že program cyklus opustí, provede příkazy mezi cyklem a koncem funkce a pak se zase objeví uprostřed cyklu.
Problém byl v tom, že funkce vracející void*
dle normy [11] bodu 6.6.3
musí skončit pomocí return
a nemůže jen tak opustit funkci dojitím na její konec.
Pokud se tak stane, jedná se o nedefinované chování,
nikoliv jen o nedefinovanou hodnotu navrácenou z funkce.
Kdyby se jednalo jen o nedefinovanou hodnotu,
tak se nic zásadního neděje. Funkce může vrátit cokoliv, ale to je nám jedno, protože výsledek se ignoruje.
Ovšem jelikož se jedná o nedefinované chování, překladač může program přeložit tak, že v takovémto případě udělá prakticky cokoliv. A v tomto případě optimalizace překladače přeložili program tak, že v případě opuštění funkce se vykonávání programu vrátí zpět dovnitř a pokračuje se v iterování smyčky. To je důsledkem toho, jakým způsobem se snaží překladač optimalizovat kód. Překladače nemusí dodržovat naprogramovanou strukturu programu. Tedy není problém přesunout část za smyčkou do ní na místo, kde se smyčka opouští. Když překladač ví, že v korektním programu by se tudy nemělo opouštět funkci, nemusí se překladač obtěžovat umísťováním explicitního návratu z funkce na dané místo.
Naštěstí oprava tohoto problému je přímočará – stačí do takovýchto funkcí explicitně dopsat return NULL;
.
Toto bohužel není jediný problém s SDPA-C. Na některých vstupech knihovna dojde do stavu, kdy nemá semidefinitní matici a výpočet spadne s následující chybou:
CHOLMOD warning: matrix not positive definite. file: ../Supernodal/t_cholmod_super_numeric.c line: 911 getMinEigenValue:: cannot decomposition :: line 193 in sdpa_linear.cpp
Tedy během výpočtu program něco spočte špatně a jako mezivýsledek mu vyjde matice, co není pozitivně semidefinitní, se kterou již dále nejde pokračovat. Příčinu této chyby se bohužel nepodařilo odhalit, protože na rozdíl od předchozího problému vůbec není jasné, kde začít hledat. Detekce nesemidefinitnosti matice totiž může být v úplně jiné části kódu, než kde nastane chyba.
Problém se projevuje například na vstupu s a seedem .
Další problém (nebo ten stejný) se projevuje zejména u větších vstupů. Uprostřed algoritmu se také objeví chybová hláška o nesemidefinitnosti matice. Následně program udělá mnoho iterací s nekonečnou účelovou funkcí, dokud se nepřekročí maximální počet iterací, a pak je vrácena matice ze samých , což dokonce porušuje zadané podmínky. Toto se stává například na seedu pro .
Vzhledem k výše uvedeným problémům dává smysl se porozhlédnout po alternativách.
Sage
SageMath je dle oficiálních stránek [12] open-source software pro matematické výpočty založený na rozšířené syntaxi pythonu,
takže je poměrně snadné ho využívat i jako programovací jazyk.
Pro účely práce byla použita verze sage 10.1 ze dne 2023-08-20.
Sage mimo jiné obsahuje rozhraní pro řešení semidefinitních programů.
Rozhraní je navrženo tak, aby bylo schopné pracovat s více různými backendy pro řešení semidefinitních programů.
Bohužel z dokumentace [13] nebylo zřejmé, jaké backendy sage podporuje.
Při zavolání default_sdp_solver("")
se objeví chybová hláška, která tvrdí, že backend by mělo jít nastavit na
CVXOPT
(což je výchozí hodnota) nebo Matrix
, případně uživatelem dodanou třídu.
Ovšem při přepnutí na Matrix
spuštění řešení spadne na NotImplementedError
, tedy zdá se, že ani tento backend není implementovaný (alespoň ve verzi, co mám k dispozici) a tedy jediná možnost je CVXOPT
.
Drobným problémem je, že dle dokumentace [13] rozhraní sage vyžaduje formulování vstupu jako primárního semidefinitního programu, ovšem náš algoritmus je založený na řešení duálního semidefinitního programu. Mezi nimi však lze snadno přecházet pomocí triviální úpravy, ovšem výsledný kód pak vypadá velice neintuitivně.
Hodnoty skalárních součinů
V odhadu střední hodnoty počtu změn barev v řešení jsme využívali toho, že funkce rozdílu pravděpodobnosti řezu a účelové funkce (funkce ) je nejvýše .
Ovšem tato funkce nenabývá takto vysokých hodnot zdaleka všude, na polovině definičního oboru je dokonce záporná (viz obrázek
Bohužel dle naměřených dat to vypadá, že hodnoty skalárních součinů se
koncentrují pouze poblíž maxima . Viz obrázek
Z grafu je vidět, že skoro nikdy semidefinitní program neumístí sousední body do protilehlých částí. Drobnou výjimku tvoří hodnota skalárního součinu okolo , kterých semidefinitní program za běhů vyrobil zhruba . K tomuto mohl být donucen existencí dvojic aut stejného typu hned vedle sebe, kdy nemá jinou možnost než mezi nimi mít skalární součin .
Lemma: Střední hodnota počtu sousedních aut stejného typu je .
Důkaz: Pro každý typ auta máme možných pozic, kde se mohou nacházet a z toho z nich jsou vedle sebe. Střední hodnota indikátoru souslednosti aut daného typu je tedy . Z linearity střední hodnoty tedy počet sousedících aut stejného typu je . QED
Ve 100 vstupech by tedy sousedních aut stejného typu mělo být ve střední hodnotě zhruba 100, což z části vysvětluje pozorovanou anomálii. Není však vyloučeno, že hodnoty skalárního součinu nebo blízké program dosáhne i jinak.
Dimenze SDP
Semidefinitní program rozmísťuje vektory do dimenzionální sféry. Z naměřených dat však vychází, že semidefinitní program většinou generuje řešení, které má mnohem menší dimenzi. Přesněji řečeno, pro řešení často platí, že všechny vektory v něm mají několik prvních souřadnic velké hodnoty a ve zbylých souřadnicích mají hodnoty blízké nule. Tedy kdybychom vektory promítli na méně dimenzionální sféru (vzali místo nich nejbližší bod na ní), tak se účelová funkce moc nezmění.
Nevíme o žádné hypotéze, proč program generuje řešení s malou dimenzí.
Taktéž není jasné, jestli či jak by toho šlo využit pro získání lepšího řešení či dolního odhadu.
Z naměřených dat zobrazených na obrázcích
Malá dimenze má ale zásadní výhodu pro vizualizaci řešení, protože trojrozměrný prostor (tedy sféru dimenze 2) si zvládne člověk snadno představit. Z čehož plyne, že zhruba polovinu řešení pro jsme schopni
zakreslit jen s drobným zkreslením, tak, jak je ukázáno na obrázku
Světlá barva bodu značí bod na zadní straně sféry. Černé čáry spojují sousední auta a šedé jsou jim středově symetrické (protože dvojice aut, jejichž druhá auta stejného typu jsou vedle sebe, je také přitahována k sobě).
Časová složitost algoritmu
Víme, že existuje implementace algoritmu s polynomiální časové složitosti (za použití elipsoidové metody). Použité řešiče však využívají jiných metod řešení semidefinitních programů a ani jeden z nich moc neslibuje, jakou přesně složitost má. Proto je na místě změřit, jak rychlé řešení jsou.
Testování probíhalo na stroji s procesorem AMD Ryzen 5 7600. Programům bylo poskytnuto operační paměti a běh byl omezen na jedno jádro procesoru. Během výpočtu na stroji neběželo nic kromě výpočtu a základních funkcí operačního systému.
Dle výše uvedeného grafu můžeme regresí v logaritmickém grafu usuzovat, že časová složitost obou algoritmů je v . Implementace pomocí SDPA-C má menší multiplikativní konstantu a navíc mnohem rychlejší čas startu, který se zejména projevuje na malých instancích.
Skóre
Nejzajímavější je pro nás naměřené (relativní) skóre algoritmů.
Mezi uvažovanými řešeními jsou dvě implementace . Implementace pomocí sage bohužel vyžaduje velké množství paměti a proto nebyla testovaná na tak velkých vstupech. O implementaci pomocí SDPA-C víme, že občas chybuje. Naštěstí chyby nenastávají tak často, aby to moc ovlivňovalo výsledné skóre. Pokud algoritmus chyboval a vrátil nějaké řešení, je uvažováno skóre daného řešení. Pokud algoritmus žádné řešení nevrátil, uvažuje se místo toho hodnota , což je jistě horní odhad na snadno dosažitelné řešení.
Na výše uvedeném grafu a tabulkách na následujících stranách si můžeme všimnout, že s rostoucím se u všech měřených algoritmů zmenšuje rozptyl relativního skóre.
Z grafu vidíme, že pro dostatečně velká je naměřené relativní skóre algoritmu menší než . Z toho můžeme tedy usuzovat, že pro . Z toho pak můžeme vyslovit hypotézu, že pro a tedy i .
Z naměřených dat také můžeme usuzovat, že je lepší než libovolný z jiných představených algoritmů.
10 | 0.53 | 0.158 | 0.3 | 0.4 | 0.5 | 0.6 | 0.8 |
20 | 0.51 | 0.109 | 0.35 | 0.45 | 0.5 | 0.6 | 0.7 |
50 | 0.508 | 0.068 | 0.4 | 0.46 | 0.5 | 0.56 | 0.62 |
100 | 0.502 | 0.0496 | 0.42 | 0.47 | 0.5 | 0.53 | 0.58 |
200 | 0.501 | 0.0356 | 0.44 | 0.48 | 0.5 | 0.525 | 0.56 |
400 | 0.5 | 0.0258 | 0.46 | 0.482 | 0.5 | 0.517 | 0.542 |
566 | 0.5 | 0.0221 | 0.465 | 0.484 | 0.5 | 0.516 | 0.537 |
800 | 0.501 | 0.0171 | 0.472 | 0.489 | 0.5 | 0.511 | 0.529 |
1131 | 0.501 | 0.0151 | 0.476 | 0.49 | 0.5 | 0.511 | 0.526 |
1600 | 0.501 | 0.012 | 0.481 | 0.492 | 0.501 | 0.508 | 0.52 |
2263 | 0.5 | 0.0105 | 0.482 | 0.492 | 0.5 | 0.507 | 0.516 |
3200 | 0.5 | 0.00883 | 0.486 | 0.494 | 0.501 | 0.507 | 0.514 |
Veškeré hodnoty jsou zaokrouhleny na 3 platné číslice.
značí výběrový průměr, tedy , kde je počet testů a je relativní skóre -tého z nich.
značí výběrovou směrodatnou odchylku, tedy .
10 | 0.46 | 0.131 | 0.3 | 0.4 | 0.5 | 0.5 | 0.7 |
20 | 0.428 | 0.0926 | 0.3 | 0.35 | 0.45 | 0.5 | 0.6 |
50 | 0.41 | 0.0571 | 0.32 | 0.38 | 0.42 | 0.44 | 0.5 |
100 | 0.406 | 0.0396 | 0.34 | 0.38 | 0.41 | 0.43 | 0.47 |
200 | 0.403 | 0.0284 | 0.355 | 0.385 | 0.405 | 0.42 | 0.45 |
400 | 0.402 | 0.0194 | 0.37 | 0.388 | 0.403 | 0.415 | 0.435 |
566 | 0.402 | 0.017 | 0.375 | 0.39 | 0.403 | 0.413 | 0.431 |
800 | 0.401 | 0.0139 | 0.378 | 0.391 | 0.401 | 0.41 | 0.422 |
1131 | 0.4 | 0.0121 | 0.38 | 0.393 | 0.401 | 0.408 | 0.42 |
1600 | 0.4 | 0.0103 | 0.384 | 0.393 | 0.401 | 0.407 | 0.417 |
2263 | 0.4 | 0.00835 | 0.387 | 0.394 | 0.4 | 0.406 | 0.413 |
3200 | 0.4 | 0.00714 | 0.388 | 0.396 | 0.4 | 0.405 | 0.412 |
10 | 0.446 | 0.123 | 0.3 | 0.4 | 0.4 | 0.5 | 0.6 |
20 | 0.411 | 0.0832 | 0.25 | 0.35 | 0.4 | 0.45 | 0.55 |
50 | 0.387 | 0.0517 | 0.3 | 0.36 | 0.38 | 0.42 | 0.48 |
100 | 0.377 | 0.0353 | 0.32 | 0.35 | 0.38 | 0.4 | 0.43 |
200 | 0.375 | 0.025 | 0.335 | 0.36 | 0.375 | 0.39 | 0.415 |
400 | 0.372 | 0.0175 | 0.343 | 0.36 | 0.372 | 0.383 | 0.4 |
566 | 0.371 | 0.0142 | 0.346 | 0.362 | 0.371 | 0.382 | 0.394 |
800 | 0.372 | 0.0126 | 0.35 | 0.364 | 0.371 | 0.38 | 0.393 |
1131 | 0.371 | 0.0102 | 0.355 | 0.364 | 0.371 | 0.378 | 0.388 |
1600 | 0.371 | 0.00875 | 0.357 | 0.365 | 0.371 | 0.377 | 0.385 |
2263 | 0.371 | 0.00763 | 0.358 | 0.366 | 0.371 | 0.376 | 0.384 |
3200 | 0.37 | 0.00624 | 0.36 | 0.366 | 0.37 | 0.375 | 0.38 |
10 | 0.421 | 0.107 | 0.2 | 0.4 | 0.4 | 0.5 | 0.6 |
20 | 0.365 | 0.0642 | 0.25 | 0.3 | 0.35 | 0.4 | 0.45 |
50 | 0.33 | 0.0361 | 0.28 | 0.3 | 0.34 | 0.36 | 0.38 |
100 | 0.322 | 0.0242 | 0.28 | 0.31 | 0.32 | 0.34 | 0.36 |
200 | 0.323 | 0.0162 | 0.295 | 0.315 | 0.325 | 0.335 | 0.35 |
400 | 0.326 | 0.0115 | 0.305 | 0.32 | 0.328 | 0.333 | 0.343 |
566 | 0.326 | 0.00932 | 0.311 | 0.32 | 0.327 | 0.332 | 0.341 |
chyb | ||||||||
10 | 16 | 0.422 | 0.129 | 0.3 | 0.3 | 0.4 | 0.5 | 0.6 |
20 | 15 | 0.371 | 0.104 | 0.25 | 0.3 | 0.35 | 0.4 | 0.5 |
50 | 11 | 0.34 | 0.0783 | 0.28 | 0.3 | 0.34 | 0.36 | 0.4 |
100 | 10 | 0.328 | 0.0434 | 0.29 | 0.31 | 0.33 | 0.34 | 0.37 |
200 | 4 | 0.325 | 0.0291 | 0.295 | 0.315 | 0.325 | 0.335 | 0.345 |
400 | 2 | 0.325 | 0.0182 | 0.305 | 0.318 | 0.325 | 0.333 | 0.343 |
566 | 2 | 0.327 | 0.0189 | 0.309 | 0.322 | 0.327 | 0.332 | 0.341 |
800 | 0 | 0.328 | 0.00746 | 0.315 | 0.324 | 0.329 | 0.334 | 0.34 |
1131 | 0 | 0.329 | 0.00643 | 0.318 | 0.324 | 0.329 | 0.333 | 0.34 |
1600 | 0 | 0.33 | 0.00552 | 0.32 | 0.327 | 0.331 | 0.334 | 0.339 |
2263 | 0 | 0.331 | 0.00452 | 0.323 | 0.328 | 0.331 | 0.334 | 0.337 |
3200 | 0 | 0.33 | 0.00379 | 0.324 | 0.328 | 0.331 | 0.333 | 0.337 |
Dolní odhad
Výstup z každého algoritmu nám dává horní odhad na optimum daného vstupu. Ovšem semidefinitní programování nám navíc dává i dolní odhad na optimum, protože víme, že optimum jednoho z ekvivalentních vyjádření účelové funkce je vždy menši rovno optimu BPS. Použité řešiče semidefinitních programů nám navíc dají i horní odhad na optimum SDP (který se od nalezeného řešení může nepatrně lišit).
Takto vygenerovaný dolní odhad nám bohužel nepřináší žádnou zajímavou informaci o chování na náhodném vstupu.
Připomeňme, že Hančl a kol. [4] dokázali, že . Průměrný dolní odhad na testovaných vstupech je pro
dostatečně velký vstup dle obrázku
Nicméně stále je zajímavé, že pro konkrétní instanci umíme určit nějaký netriviální dolní odhad.
Závěr
V této práci jsme představili algoritmus na BPS založený na semidefinitním programování. Bohužel se nám nepodařilo dokázat žádný netriviální odhad na . Nicméně dle naměřených dat můžeme soudit, že se pohybuje okolo 0.34. Místo toho jsme však dokázali, že pro libovolný vstup bude střední hodnota (přes náhodná čísla generovaná algoritmem nikoliv přes vstup) skóre řešení nejhůře od optima, tedy, že platí
Toto řešení jsme dále dokonce dvakrát implementovali s využitím různých implementací řešení semidefinitních programů, které jsme tímto i porovnali. Z naměřených dat jsme jednak odhadli střední hodnotu skóre algoritmu přes náhodný vstup. A také jsme si všimli, že dimenze řešení semidefinitního programování je poměrně malá, což jsme zformulovali jako hypotézu.
Stále však zůstává otevřená otázka, kolik přesně je a (a případně zda se rovnají) a jaké nejlepší je možno dosáhnout polynomiálním algoritmem .
Seznam použité literatury
[1] Bonsma, P.; Epping, Th. a Hochstättler, W. Complexity results on restricted instances of a paint shop problem for words. Discrete Applied Mathematics [online]. 2006, 154(9), 1335–1343. ISSN 0166-218X. Dostupné z: https://www.sciencedirect.com/science/article/pii/S0166218X0500377X
[2] Gupta, Anupam; Kale, Satyen; Nagarajan, Viswanath; Saket, Rishi a Schieber, Baruch. The Approximability of the Binary Paintshop Problem. In: Raghavendra, Prasad; Raskhodnikova, Sofya; Jansen, Klaus a Rolim, José D. P., ed. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, s. 205–217. ISBN 978-3-642-40328-6.
[3] Andres, Stephan Dominique a Hochstättler, Winfried. Some heuristics for the binary paint shop problem and their expected number of colour changes. Journal of Discrete Algorithms [online]. 2011, 9(2), 203–211. ISSN 1570-8667. Dostupné z: https://www.sciencedirect.com/science/article/pii/S1570866710000559
[4] Hančl, J.; Kabela, A.; Opler, M.; Sosnovec, J.; Šámal, R. a Valtr, P. Improved Bounds for the Binary Paint Shop Problem. In: Wu, Weili a Tong, Guangmo, ed. Computing and Combinatorics. Cham: Springer Nature Switzerland, 2024, s. 210–221. ISBN 978-3-031-49193-1.
[5] Epping, Th.; Hochstättler, W. a Oertel, P. Complexity results on a paint shop problem. Discrete Applied Mathematics [online]. 2004, 136(2), 217–226. ISSN 0166-218X. Dostupné z: https://www.sciencedirect.com/science/article/pii/S0166218X03004426
[6] Alon, Noga. Splitting necklaces. Advances in Mathematics [online]. 1987, 63(3), 247–253. ISSN 0001-8708. Dostupné z: https://www.sciencedirect.com/science/article/pii/0001870887900557
[7] Gärtner, Bernd a Matoušek, Jiří. Approximation algorithms and semidefinite programming. B.m.: Springer Science & Business Media, 2012.
[8] Sun, Kevin. Lecture notes for Graph Algorithms, lecture 22 [online]. 2019 [vid. 2024-04-20]. Dostupné z: https://people.csail.mit.edu/ronitt/COURSE/S20/NOTES/lec6-scribe.pdf
[9] Dimitrakakis, Alexander. Lecture notes for Randomness and Computation, lecture 6 [online]. 2020 [vid. 2024-04-20]. Dostupné z: https://people.csail.mit.edu/ronitt/COURSE/S20/NOTES/lec6-scribe.pdf
[10] SDPA Project. SDPA Official Page [online]. 1995–2024 [vid. 2024-03-30]. Dostupné z: https://sdpa.sourceforge.net/
[11] ISO/IEC. Working Draft, Standard for Programming Language C++ [online]. 2014 [vid. 2024-04-20]. Dostupné z: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf
[12] Autoři SageMath. SageMath Official Page [online]. [vid. 2024-03-31]. Dostupné z: https://www.sagemath.org/index.html
[13] The Sage Development Team. Sage – Semidefinite Programming [online]. 2005-2024 [vid. 2024-03-31]. Dostupné z: https://doc.sagemath.org/html/en/reference/numerical/sage/numerical/sdp.html