Cvičení z Optimalizačních metod.

Zde se budou nacházet informace pro studenty Optimalizačních metod (2014/2015), pondělní cvičení od 14:00 k přednáškám profesora Martina Loebla. Další cvičení vedou kolegové Martin Böhm a Radek Hušek.

Studijní materiály:

Studijní materiály v angličtině:
Linear programming, A Concise Introduction (Thomas S. Ferguson). A writeup of a lecture with a similar linear programming content, but missing other combinatorial optimization topics.
Combinatorial Optimization: Polyhedra and Efficiency (Alexander Schrijver). A series of three textbooks containing almost everything one needs to know from combinatorial optimization. A bit dense in some places, but it is readable.
Introduction to Discrete Geometry and Lectures on Discrete Geometry (Jiří Matoušek). The first link are lecture notes from a discrete geometry class, available for borrowing at the Faculty of Math and Physics library. The second book is a normal book on the same subject. You do not need to read the whole book; the essential parts are the lectures on convexity and on convex polytopes.
Studijní materiály v češtině:
Lineární programování pro informatiky (Jiří Matoušek,2006) -- dostupné v knihovně MFF UK (jako Lineární programování a lineární algebra pro informatiky) a také na webu!
Literatura od prof. Sgalla z předchozího roku.
Cvičení z let minulých:
cvičení Martina Böhma z LS 2013/2014,
cvičení Marka Eliáše z LS 2013/2014,
cvičení Dušana Knopa z LS 2012,
cvičení Dušana Knopa z LS 2011,
cvičení Marka Eliáše z LS 2012,
cviceni Vojty Tůmy z LS 2012.
cvičení Marka Krčála z LS 2010/2011 a z LS 2009/2010.

Co se dělo na cvičeních:

1.hodina (bez opáčka): Zavedení základního tvaru LP, motivace proč studovat LP (existuje polynomiální algoritmus, P-úplnost, "snadné" ověření, dualita, aproximace), Zopakování triku z přednášky (vytvoření rovnosti z nerovností). Příklady.
2.hodina (bez opáčka): Doplnění příkladu z přednášky (odděluji dvě množiny pomocí přímky. Bylo potřeba ošetřit případ, kdy opt řešením byla přímka kolmá na osu x), jak se zbavit ostrých nerovností v případě, že mám úlohu ve které nepotřebuji optimalizovat. Příklady na formulace LP.
3.hodina (opáčko): LP formulace základního tokového problému, příklady z minula, zopakování definic, příklady a definice.
4. hodina (bez opáčka): Dořešení restů z minulého cvičení. Geometrie II.
5. hodina (opáčko): Příklady na Simplex. Zkuste si projít a sami zkusit základní případ simplexu (Příklad šestý). K ostatním se ještě trochu vrátíme příště a řekneme si i nějaké další tipy a triky.
6. hodina (opáčko): Jak si uštřit práci při simplexové metodě a další příklady, včetně ukázky řešení prvního příkladu. Příklady na geometrii jsme na cvičení neměli, ale můžete je použít na procvičování. Tedy Simplex+řešení a geometrie. Motivace na dualitu ukázána přes horní odhady a tím neformálně dokázána slabá věta o dualitě.
7. hodina (bez opáčka): 1. velká písemka.
Velikonoce
8. hodina (bez opáčka) (P. Veselý): Ukázání příkladu na MaxCut z písemky (dvě různá řešení). Příklady na dualitu.
9. hodina (opáčko) (P. Veselý): Příklady na unimodularitu.
10. hodina (bez opáčka) (P. Veselý): Dualizace SATu z opáčka, Příklady na komplementaritu.
11. hodina (bez opáčka): 2. velká písemka.
12. hodina (bez opáčka): Podrobně popsán primárně duální algoritmus na vážené vrcholové pokrytí s důkazem 2-aproximace, Příklady na primárně duální algoritmy.
13. hodina (opáčko): Podorobné řešení 2. písemky, podrobné vysvětlení primárně duálního algortmu pro nejkratší cestu z 12. cvičení, anketa.

Domácí úkoly:

První domácí úkol: Přečtěte si zadání a projděte si manuál. Hotové úkoly posílejte emailem do: 18. dubna 2015 8:00.

Druhý domácí úkol: Přečtěte si zadání a můžete si opět projít manuál. Hotové úkoly posílejte emailem do: 11. června 2015 8:00.

Požadavky na zápočet:

Podmínky na všech cvičeních budou stejné a zápočet bude potřeba ke zkoušce.

Zápočet získáte za dosažení alespoň 60 bodů. Body můžete získat těmito způsoby:

Aktivita na cvičení: ~2 body za předvedený příklad.
5-6-krát za semestr: 10-minutové opáčko za 2 body.
Dvě písemky: každá za 25 bodů.
Dva praktické domácí úkoly: každý za 25 bodů.

Opáčko je opakování látky z posledních dvou cvičení formou minipísemky s jedním příkladem. Bude probíhat zhruba 5-6krát za semestr, vždycky prvních 10 minut cvičení. Opáčka jsou dobrovolná a nejsou přepadová; týden dopředu vyvěsíme na web, jestli se příští cvičení bude jedno konat.

Písemka je 90-minutový klasický test, obsahující cca 5 příkladů po 5 bodech. Bude se konat v polovině semestru a ke konci semestru -- vyhlášena bude 14 dní dopředu. Písemka také není povinná, silně však doporučujeme na písemky přijít. Pokud se nemůžete na písemku dostavit, kontaktujte mne co nejdříve předem emailem.

Domácí úkoly budou praktické a programovací. Za úkol většinou bude vyřešit daný problém pomocí lineárního programování a napsat program/skript, který zadané konkrétní řešení vyřeší a vypíše výsledek. Úkoly budou jiné než ty loňské, ale podobné. Na domácí úkoly bude vždy alespoň měsíc času. Rád bych vás ještě upozornil, abyste se vyvarovali plagiátorství.

Všimněte si, že je mnoho způsobů, jak získat 60 bodů; vyberte si tu cestu, která vám vyhovuje nejvíce.

Vaše průběžné výsledky budeme zveřejňovat na webu. Pokud chcete, můžete si místo jména zvolit přezdívku -- buď na prvních cvičeních, nebo emailem.

Výsledky a nárok na zápočet:

Dosavadní výsledky v google dokumentu.

masarik<a>mimuw.edu.pl

CENT building room 03.111, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 8514, Department of Mathematics, Simon Fraser university, 8888 University Drive, Burnaby, V5A 1S6, Canada
Room 320, KAM MFF, Malostranské náměstí 25, Praha 1, 11800, Czech Republic