Cvičení z Optimalizačních metod v LS 15/16 (pondělí 10:40, S10)

K přednášce Optimalizační metody prof. Jiřího Sgalla vedu cvičení, které se koná v pondělí od 10:40 v S10. Další česká cvičení vedou Tomáš Masařík a Radek Hušek

Pokud máte nějaký dotaz či vám nesedí body v tabulce, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po cvičení. Také budu rád, když se během cvičení budete ptát, jakmile vám nebude něco jasné.

Chcete-li konzultaci, ozvěte se mi emailem. Domluvené časy konzultací (ohlaste se předem, že přijdete):

18. 7. (poslední konzultace do září)

Zajděte do S320 (místnost vedle S3), a pokud mě tam nenajdete podívejte se na chodbu KAM/IUUK ve třetím patře (dveře naproti S3). Jestliže nebudu ani tam, počkejte na chodbě před S320.

Novinka: 27. května zadán 3. praktický DÚ, viz níže.

Co jsme dělali

22. 2.	Opakování lingebry, především afinních podprostorů jakožto řešeních soustavy Ax=b. Příklady. (Žádný DÚ nebyl zadán.)
29. 2.	Formulace lineárních programů, jak se vypořádat s absolutní hodnotou, převádění nerovnic na rovnice a naopak, co dělat s ostrými nerovnostmi a minimalizace maxima. Příklady a DÚ. (Zadány dva teoretické domácí úkoly.)
7. 3.	Opáčko na formulaci LP. Na úvod, jak mohou vypadat LPčka ve 2D. Příklady na celočíselné LP a jejich relaxace. Důkaz, že pro LP relaxaci celočíselného programu pro perfektní párování v bipartitním grafu existuje celočíselné optimum (pokud existuje přípustné řešení) – viz Matouškova kniha. Update: v třetím úkolu můžete používat celočíselné i reálné proměnné (říká se tomu pak smíšené celočíselné programování).
14. 3.	Řešení opáčka z minula a celočíselný program pro obchodního cestujícího. Opakování pojmů z afinity a konvexity, příklady (stihli jsme jen první tři).
21. 3.	Opáčko na afinitu. Příklady na mnohostěny (stihli jsme vše do 5.a). Slíbený domácí úkol.
28. 3.	Velikonoce
29. 3.	Bonusové cvičení na konvexitu a mnohostěny od Tomáš Masaříka.
4. 4.	Mnohostěny, simplexy a simplexová metoda. Příklady a DÚ, stihli prvních 5 příkladů.
11. 4.	Cvičil Dušan Knop: Příklady na simplexovou metodu (stihly se první dva a kus třetího, ten si zkuste rozmyslet)
18. 4.	Opáčko na simplexovou metodu a příklady na dualitu (nestihli jsme poslední dva).
25. 4.	Dokončení duality: pár příkladů z minula a dva duální programy na nejkratší cestu. Totální unimodularita: úvod, opakování determinantu a příklady (stihli jsme první tři, zbytek příště).
2. 5.	Opáčko na dualitu, pokračování unimodularity a komplementarita. Příklady a DÚ (změna oproti vytisklému zadání: deadline až za 3 týdny). Hint k 3. části DÚ: vzpomeňte si, jak jsme dělali, že pro LP relaxaci celočíselného programu pro perfektní párování v bipartitním grafu existuje celočíselné optimum.
9. 5.	Cvičil Martin Böhm: Opáčko na unimodularitu a příklady na komplementaritu (řezy se nestihly).
16. 5.	Velká písemka na celé cvičení na formulace LP, geometrii, simplex, dualitu a komplementaritu.
23. 5.	Řešení prvních tří příkladů v písemce, primárně-duální algoritmy (poslední příklad jsme nestihli).

Praktické domácí úkoly

Než začnete, přečtěte si obecné informace k praktickým DÚ a manuál k jazyku MathProg (sepsal Martin Böhm)

Čtverce (8 bodů, deadline na odevzdání: do začátku cvičení 11. dubna) – Update: čtverce jsou vždy rovnoběžné s osami, tedy je nelze otáčet (mělo by to vyplývat z definice čtverce na začátku).
Další update: správné výsledky pro některé vzorové vstupy
Graf bez orientovaných cyklů (12 bodů, deadline na odevzdání prodloužena do: 16. května 10 h)
Letecká klika (10 bodů, deadline na odevzdání: 27. června 10 h)

(Teoretické úkoly jsou za příklady dělané na cvičeních.)

Studijní materiály

V češtině:

Poznámky z přednášky a další zdroje na stránkách přednášky
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.

V angličtině (převzato od Martina Böhma):

Understanding and Using Linear Programming (Jiří Matoušek, Bernd Gärtner). An introductory book to Linear Programming for computer scientists which covers a large part of the lecture. Very accessible and readable. Contains applications, but no exercises.
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.

Cvičení z let minulých:

LS 2015: Martin Böhm, Tomáš Masařík, Radek Hušek
LS 2014: Martin Böhm, Marek Eliáš,
LS 2012: Dušan Knop, Marek Eliáš, Vojta Tůma
LS 2011: Dušan Knop, Marek Krčál
LS 2010: Marek Krčál

Zápočet

Všechna česká cvičení mají velmi podobné podmínky na zápočet a ten bude vyžadován k přihlášení na zkoušku. Zápočet získáte za dosažení celkem alespoň 55 bodů. Pokud získáte 75 bodů budete mít snažší průběh zkoušky u prof. Sgalla. Body můžete získat těmito způsoby:

aktivita na cvičení: 1 až 2 body za kompletně předvedený příklad (za část řešení také něco bude),
5-krát za semestr: 15-minutové opáčko à 4 body,
jedna velká písemka za 30 bodů,
tři praktické domácí úkoly dohromady za 30 bodů,
teoretické domácí úkoly celkem alespoň za 20 bodů.

Aktivita: pokud by vám přišlo, že jste měli během cvičení dostat nějaké body a já to přehlédl nebo zapomněl, ozvěte se emailem či po cvičení.

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

Písemka je 90-minutový klasický test. Bude se konat ke konci semestru – vyhlášena bude 14 dní dopředu. Písemka také není povinná, silně však doporučujeme na ni přijít. Pokud se nebudete moci na písemku dostavit a chtěli byste si ji napsat, kontaktujte mne co nejdříve předem emailem či po cvičení.

Praktické domácí úkoly budou programovací. Za úkol bude vyřešit daný problém pomocí lineárního programování – tedy napsat program/skript, který zadanou úlohu vyřeší a vypíše výsledek. Na domácí úkoly bude vždy alespoň měsíc času a odevzdávají se emailem. Rád bych vás ještě upozornil, abyste se vyvarovali plagiátorství.

Teoretické domácí úkoly budou zadávány průběžně, většinou formou drobnějších příkladů po cca 2 bodech. Na jejich řešení můžete spolupracovat, důležité ale je, abyste řešení důkladně rozuměli a sami ho sepsali. Na teoretické úkoly bude 14 dní času, přesněji do začátku cvičení 14 dní od zadání. Odevzdávejte je nejlépe elektronicky (ve formátu PDF, ODT, ... nebo i jen jako text emailu) nebo na papíře na začátku cvičení. Nafocené či naskenované papíry mi neposílejte.

Obecně: Všechny kroky se snažte pečlivě zdůvodňovat, je to důležitější než mít správný výsledek. Naopak můžete používat cokoli z přednášek či cvičení bez důkazu, jen vždy uveďte, co právě využíváte. Ještě bych rád upozornil, že bodové hodnocení jednotlivých příkladů nemusí vždy nutně odpovídat jejich obtížnosti.

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

Vaše průběžné výsledky budu zveřejňovat na webu. Pokud chcete, můžete si místo jména zvolit přezdívku (či nějaký unikátní identifikátor) – buď na prvních cvičeních, nebo emailem.

Tabulka výsledků

Již není vidět