Zápočet

Zápočet dostanete, pokud dostanete alespoň 65 bodů. Body se budou rozdávat za:

• účast na hodině - 1b za cvičení
• předvedení příkladu na tabuli - 2 body za příklad (limit 2 příklady za cvičení).
• 2 písemky - každá za 25 bodů.
• 2 velké domácí úkoly - každý za 25 bodů.

Domácí úkoly

Domácí úkol 1: 25 bodů, termín 9.5.2014 23:59.

Příklad 0 (1 bod): Podivejte se do bodové tabulky a najděte si vaše zaručeně náhodné číslo (znč). Pak přejděte do složky s úkoly a najděte si svůj náhodný graf. Zkontrolujte, že nemá více, než 63 vrcholů a že je formát dat v pořádku. Kdyby nikoli, tak se ozvěte.

Příklad 1 (12 bodů): Ve vašem grafu na (právě) 63 vrcholech spočítejte jedním lineárním programem nejkratší cesty z vrcholu 1 do všech ostatních vrcholů. Formát vstupu je:

a -- b (c)

a -- b je popis (neorientované) hrany mezi vrcholy čísla a & b, c je délka hrany mezi nimi (celé číslo mezi 1 a 50). Pozor, může se stát, že do některého vrcholu nevede žádná cesta, nebo že vrchol je zcela izolovaný. Pak hodnotu proměnné "délka nejkratší cesty" nastavte na nějakou velkou hodnotu, která se jinak vyskytovat nebude.

Příklad 2 (12 bodů): Ve vašem grafu na 63 vrcholech (v tom samém, co v prvním příkladu) spočítejte lineární relaxaci problému vrcholového pokrytí. Pokud si zadání celočíselného problému vrcholového pokrytí nepamatujete, podívejte se na Wikipedii. V tomto příkladu ignorujte váhy, které jsou na hranách. Připomínám, že problém máte vyřešit jako lineární relaxaci, ne jako celočíselný problém.

Řešení posílejte emailem na bohm[zavináč]iuuk.mff.cuni.cz s předmětem OPT: HW1. Prosím, dodržte předmět, ať v tom nemám nepořádek.

Domácí úkol 2: 25 bodů, termín 30.6.2014 23:59. Úkoly mají tentokrát jen jeden vzorový vstup; přesto by vaše konvertory měly zvládnout i jiná zadání podobné velikosti.

Příklad 1 (5 bodů):

Vlak potřebuje, aby v něm byl vždy alespoň určitý počet průvodčích. Tento počet se v průběhu dne mění. Požadované počty pro každý časový úsek dne jsou v tabulce. Každý průvodčí po nástupu do práce zůstává ve vlaku 8 hodin, pak odchází a v průběhu stejného dne už nenastoupí. Vytvořte a spočtěte celočíselný program, který určí, kolik průvodčích a kdy má nastoupit do práce, když chceme minimalizovat počet potřebných průvodčích při zachování minimálních potřebného počtu v každém časovém úseku. Myslete také na to, že průvodčí, který nastoupil o 20:00, zůstává ve vlaku až do druhého dne (04:00).

Zadání prvního příkladu.

Příklad 2 (20 bodů:)

V Říši pohádek byla postavena jednosměrná silniční síť a místního despotu by zajímalo, jaká je maximální celočíselná cirkulace v této síti (cirkulace je tok, který nemá zdroj ani stok, čili Kirchhoffovy zákony platí v každém vrcholu).

Problém je, že kromě normálních "pozemských" jednosměrných silnic bylo postaveno také 8 kouzelných hyperhran, které žádné logické zákony nerespektují. Jediný způsob, jak tyto silnice chápat, je zapsat si vektor násobnosti každé hyperhrany u každého vrcholu -- a toto číslo bude celočíselná hodnota v intervalu [-5,5]. Hyperhrana nemá jeden zdrojový a jeden cílový vrchol -- u každého vrcholu má násobnost prakticky libovolnou. Hyperhrana má kapacitu 1 -- lze ji buď použít, nebo nepoužít. Ostatní hrany mají celočíselnou kapacitu 10000.

Říše pohádek by ráda používala své kouzelné hrany, takže si cení více, pokud najdete řešení s nimi. Celkovou cirkulaci měřte jako "součet toku každou hranou" + "100000 * počet hyperhran, které jste použili".

Vašim úkolem je navrhnout program, který zadanou úlohu vyřeší pomocí celočíselného/lineárního programování, a to včetně magických hyperhran. Na prvním řádku vstupu dostanete počet vrcholů (nejvýše 300), hran (nejvýše 60 000) a magických hyperhran (nejvýše 8). Zbytek zadání je matice incidence grafu s tím, že posledních 8 sloupců odpovídá hyperhranám.

Tato úloha je bodovaná i časově: pokud vymyslite program, který pomocí celočíselného/lineárního řešiče spočítá řešení zhruba do 90 minut, dostanete 5 bodů, pokud vymyslíte program, který spočítá řešení do zhruba 10 minut, dostanete plný počet bodů.

Váš konvertor a program by měl být schopen vyřešit tuto úlohu pro libovolný graf, ne jen pro ten zadaný (tedy řešení "optimum jsem doma napočítal za několik hodin, odevzdaný program ho jen ověří" není správné). Časové limity berte jen nahrubo, ve skutečnosti měříme a hodnotíme myšlenku vašeho řešení. Vaše programy budeme spouštět na čtyřjádrovém (osmivláknovém s HT) Intel Core i7-3770 CPU s 16GB RAM.

Zadání druhého příkladu.

Řešení posílejte emailem na bohm[zavináč]iuuk.mff.cuni.cz s předmětem OPT: HW2. Prosím, dodržte předmět, ať v tom nemám nepořádek.

Q: Jak mám řešit úkol?

A: Na úkol je potřeba využít nějakého řešiče lineárního/smíšeného programování (tzv. solveru). Osobně doporučuji knihovnu GLPK, případně její samostatný program glpsol a jazyk pro zadání lineárního programu AMPL/MathProg. Seznam dalšího softwaru, který se dá použít, najdete u Marka. Chcete-li i příklady zápisů, podívejte se na slajdy o řešičích z minulých let.

Q: Co má být součástí řešení?

A: Řešením má být (alespoň) trojice souborů: konvertor, tudíž váš vlastní program, který z vašeho grafu vytvoří lineární program pro váš zvolený řešič; program samotný, a stručná dokumentace, čili aspoň několikařádkový popis, jak váš lineární program je strukturovan, a také technikálie: jak použít konvertor a jaké příkazy mám použít, abych vypsaný LP vyřešil. Nezapomeňte v dokumentaci zmínit, jak intepretovat řešení lineárního programu (například jak vyčíst, jak dlouhé jsou nejkratší cesty).

Q: Mohu vyřešit úlohu chytrým využitím lineárního/celočíselného programování? Třeba použiju opravdu chytrý řešič, napíšu si vlastní řešič, upravím zadání úlohy, úlohu zparalelizuji, pustím na kvantovém počítači?

A: V zásadě ano, chytrá řešení vítám -- věřím, že vás napadnou i taková, o kterých bych nesnil. Nicméně je to cvičení na optimalizační metody, a tak by vaše řešení mělo v jádru využívat formulaci/řešič lineárního nebo celočíselného programu.

FAQ

Q: Mohu chodit k Tobe na cviceni, i kdyz jsem zapsan na jinem? I kdyz chodim na jinou prednasku? Mohu jit misto Tveho cviceni na jine?

A: Na vsechny otazky je odpoved stejna: ano, ale prosim napis mi o tom email, abych to vedel. Pokud Ti nejde zapsat se do meho cviceni v SISu, dej mi o tom take vedet pres email nebo osobne na cviceni.

Q: Mohu dostat zapocet dva dny pred koncem semestru, pokud jsem dosud nic neudelal?

A: Ne.

Q: Jsou obě Tvá cvičení záměnná?

A: Standardně ano, takže pokud nemůžete přijít na jedno, přijďte na druhé. Pokud se bude psát písemka, tak čekejte, že obě cvičení budou mít různá zadání.

Q: Mohu chodit střídavě na Tvoje a Markovo cvičení?

A: Je pravda, že naše cvičení budou sdílet přípravu a materiály (takže například DÚ budou shodné, požadavky na zápočet jsou shodné a příklady na písemkách podobné). Přesto je cvičení v kompetenci cvičícího a cvičení se mohou v průběhu semestru lišit -- což platí i o příkladech na písemku. Vyberte si proto během prvních týdnů jedno ze cvičení a choďte potom na to.

Q: Když všichni opíšeme úkol, tak všichni dostaneme 65 bodů prakticky zadarmo, ne?

A: Nepočítejte s tím. Jednak budou domácí úkoly připravené individuálně náhodně, tj. každý student bude mít o trochu jiné zadání, a jednak budeme požadovat i zdrojový kód/postup řešení a když odhalíme plagiaritu, body budeme odčítat.

Q: Optimalizace mi moc nejde a na cviceni se nechytam. Co ted?

A: Prijd na konzultaci! Kazdy matfyzak, ktery se nechyta, ale nezajde na konzultaci, zaslouzi vymachat v hodne studene vode. Konzultace si snadno domluvíte pomocí emailu. Pokud máte kratší dotaz, stači ho napsat v emailu a pořešíme ho elektronickou cestou.

Body