Informace k praktickým domácím úkolům z optimalizačních metod (NOPT048)

Paralelky středa od 14:00 a čtvrtek od 17:20

Zadání

• Obecné informace
• 1. úkol, deadline 22.4. (do původní verze se vloudil bug a ukázkový výstup byl špatně, v této verzi už je opraven)
• 2. úkol, deadline 29.6.

Testovací data

1. úkol

• Malá data, vhodná pro debuggování.
• Středně velká data, vaše řešení (i triviální) by mělo být schopné zpracovat celou tuto sadu do půlhodiny (vzorové triviální řešení to zvládne do dvou minut).
• Různě velká data, obsahují vstupy s grafy od 100 vrcholů až do 2000 vrcholů. Vhodné pro experimentování s efektivitou vašeho řešítka.
• Vězte, že může existovat více optimálních řešení, pokud se tedy vaše řešení neshoduje s tím vzorovým, může to být právě tím, že jste našli jiné řešení.
• Pokud máte pocit, že jste v datech našli chybu (třeba máte lepší řešení), tak prosím dejte co nejdříve vědět.

2. úkol

• Miniaturní data, vaše řešení (i triviální) by mělo být schopné zpracovat celou tuto sadu do půlhodiny (vzorové triviální řešení to zvládne do tří minut).
• Malá data (v původně byla zveřejněna špatná sada, teď už by měla být v pořádku)
• Velká data, pro zisk plného počtu bodů musí být vaše řešení rozumně rychlé i na těchto vstupech.
• Vězte, že může existovat více optimálních řešení, pokud se tedy vaše řešení neshoduje s tím vzorovým, může to být právě tím, že jste našli jiné řešení.

Trochu o celočíselném programování

Zatímco pro řešení problémů lineárního programování (LP) se používá simplexový algoritmus (který sice obecně není polynomiální ale obvykle se tak chová), k řešení celočíselného lineárního programování se obvykle používá algoritmus branch-and-cut (který se zdaleka polynomiálně nechová). V jádru není branch-and-cut nic jiného, než chytrý způsob, jak pomocí metody rozděl a panuj projít všechna celočíselná řešení problému a najít to nejlepší. Algoritmus řeší problém tak, že přidáním nějaké podmínky rozdělí problém na dva podproblémy (např. prodproblém s x je nejvýš 4 a podproblém s x je alespoň 5) a ty vyřeší rekurzivně. Před rozdělením ale řešič nejdřív spočítá řešení lineární relaxace problému. To má vícero důvodů. Pokud je řešení relaxace celočíselné, pak není třeba pokračovat, neb jsme našli optimum. Naopak, pokud řešení relaxace má horší hodnotu účelové funkce než doposud nejlepší celočíselné řešení, taktéž nemusíme tento podproblém řešit, neb lepší řešení z něj nedostaneme. Na základě řešení relaxace se můžeme například rozhodnout, jak problém rozdělit (např. budeme vždy dělit jen podle proměnné, která není celočíselná). Podrobněji se o branch-and-cut můžete dočíst např. v knize Applied Mathematical Programming (kapitoly 9.4 a 9.5) nebo Wikipedii. Popis algoritmu, který používá GLPK najdete v dokumentaci (níže v užitečných zdrojích) v kapitole 5.1.2.

Jak můžeme tedy řešiči pomoct? Například:

• Zmenšit počet přípustných celočíselných řešení, například snížením počtu proměnných, silnějšími podmínkami atp. Čím méně je přípustných řešení, tím méně jich musí řešič projít. Při přidávání podmínek je dobré být opatrný, neboť zvětšují problém (viz níže)
• Zmenšit úlohu (počet podmínek a jejich velikost). Při každém větvění se znovu řeší lineární relaxace problému (nějak upraveného). Tedy i malé zrychlení v řešení relaxace může mít v součtu velký vliv.
• Přidat silné řezy (podmínky). Je-li hodnota řešení lineární relaxace dobrou aproximací hodnoty celočíselného optima, může algoritmus už na základě vyřešení relaxace vynechat spoustu neperspektivních problémů. Může tedy velmi pomoci přidat podmínky pro řezy (ve smyslu metody řezů z přednášky), které zmenší rozdíl mezi celočíselným a relaxovaným optimem.

Pozor! To, jaké chytristiky řešiči pomohou silně závisí na konkrétním řešiči. GLPK je poměrně hloupé a tedy mu pomůže leccos, ale třeba u komerčních řešičů je velká šance, že stejně dokáží vymyslet něco lepšího než vy.

Užitečné zdroje

• Stručný, ale kvalitní tutoriál o modelovacím jazyce GMPL, neboli MathProg: MathProg z rychlíku.
• Oficiální dokumentace knihovny GLPK, verze 4.55.
• Oficiální dokumentace jazyka GMPL, verze 4.50.
• Wikikniha. Obsahuje spoustu věcí navíc a je to spíš kostra, ale ze zajímavých věcí obsahuje například seznam knihoven, skrze které je možné dostat GLPK do spousty programovacích jazyků.
• GLPSOL má poměrně striktní omezení na délku stringových konstant (200 znaků). Potřebujete-li vypisovat na výstup delší řetězce, prostě je rozdělte mezi víc printfů.