Kombinatorická optimalizace

• Stránky předmětu: https://moodle.dce.fel.cvut.cz/course/view.php?id=21
• Přednášející: Zdeněk Hanzálek
• Cvičící: Zdeněk Hanzálek, Přemysl Šůcha, Jan Kelbel, Jiří Trdlička, Michal Kutil, Zdeněk Baumelt, Roman Čapek

warehousing | bradley

!!! Můžete sem prosím dát někdo zadání z testů ze cvičení ? Díkes !!!

Praktický test - jde o výpočet toku v síti (na test bylo něco málo přes hodinu času a bylo možné používat libovolné materiály, jinak říkali ze každé cvičeni bude mít jiné zadáni)ko_prakticky_test_2015.pdf

2. zadání: knapsack - dány 2 batohy, předměty s váhou a cenou; Naplnit batohy co nejcenějšíma předmětama, pomocí ILP, každý předmět může být jen v jednom batohu.

ILP binární formule

1. optimized data storing
2. call center scheduling
3. function approximation
4. binary image reconstruction

1. úkol | 2. úkol | 3. úkol (call centre) | 4. úkol (func approx) | 5. úkol (bin. image) | 6. úkol | 7. úkol

2014/15 LS: 1. test - přednáška ve 4. týdnu | 2. test - přednáška v 8. týdnu | Praktický test - cvičení | 3 test - přednáška v 12. týdnu

2013/14 LS: 1. test - přednáška ve 4. týdnu | 2. test - přednáška v 8. týdnu | 3 test - přednáška v 12. týdnu
1 test - přednáška ve 4. týdnu | 2 test - přednáška v 8. týdnu | 3 test - cvičení v 10. týdnu | 3 test - cvičení v 10. týdnu (2012)

2D optimalní řezný problém

Rozvrh zdravotních sester ILP

Prehledna tabulka uloh podle kategorie k 9.6.2014, je tam i adresar do ktereho muzete pridavat vypracovane ulohy k dane kategorii

• 6 až 7 otázek nebo příkladů jako v semestru
• aspoň po 1 otázce z ILP, cest, toků a rozvrhů
• 1 až 2 otázky na batoh, TSP nebo programování s omezujícími podmínkami
• 2, možná až 3 iterace algoritmu
• 3, možná jen 2 formulace úlohy
• 1 teoretická otázka, třeba Bellmanova rovnice

• ILP - formulace - nějaké investice, viz druhá přednáška
• Toky - matice 3×3 suma sloupců a řádků a najít maximální tok, když číslo zaokrouhlím nahoru nebo dolu a zda tok bude vždy celočíselný
• Rozvrhování - Rothkopf
• Rozvrhování - Transformace PSm,1|temp|Cmax → PS1|temp|Cmax
• Constraint Programming - hranová konzistence AC-3
• Iterace Dijskry - to byl asi nejlehčí příklad
• Teorie - důkaz NP-obtížnosti TSP pomocí polynomiálního převodu z problému Hamiltonovské kružnice na instanci TSP

• ILP - formulace optimalizace výroby s podmínkami na fixní náklady atd. (12 bodů)
• SPT - najít nejlepší umístění skladu v závislosti na vzdálenostech k spotřebitelům a váhám nákladu (8 bodů)
• Toky - nalezení přípustného toku, když jsou nenulová spodní omezení (9 bodů)
• Knapsack - vyřešit instanci pomocí dynamického programování (9 bodů)
• Sch I. - vyřešit rozvrhování na jednom procesoru pomocí Bratleye (9 bodů)
• Sch II. - vyřešit rozvrhování pomocí úrovňového algoritmu (9 bodů)
• TSP - důkaz, že je NP-hard přes převod na Hamiltonovskou kružnici (8 bodů)

• ILP - formulace investice do nemovitostí (12 bodů)
• Toky - nalezení maximálního toku a minimálního řezu v zadaném grafu (9 bodů)
• SPT - pomoci Floydova algoritmu najít nejdelší cesty v grafu (9 bodů)
• CP - úvodní propagace před běhěm algoritmu, nakreslit částečná řešení stromu pro prohledávání a propagaci, napsat konečné řešení nebo rozhodnout, zda-li řešení existuje (10 bodů)
• Sch I. - převod 1|rj, dj|Cmax na PS1|temp|Cmax (6 bodů)
• Sch II. - ILP formulace 1|prec|suma wi*Ci + k čemu lze v algoritmu větví a mezí použít částečné řešení J^LP(zbylých úloh) (10 bodů)
• Knapsack - popsat pseudokódem 2-aproximační algoritmus a vysvětlit proč je 2-aproximační (8 bodů)

• Zadání a řešení

• Zadání a řešení
• Bonus - stihnul jsem vyfotit pár jiných zadání

• převod 1|rj, dj|Cmax na PS1|temp|Cmax
• Bratleyův algoritmus + podmínka optimality
• Knapsack - vyřešit instanci pomocí dynamického programování
• Christofidesův algoritmus - pseudokód + faktor aproximace
• Ford-Fulkersonův algoritmus na maximální tok a minimální řez
• Příklad SPT3 z přednášky: Nejspolehlivější spojení
• ILP - investice na burze

• ILP - formulace problému TSP s časovým oknem. Kromě standardní instance jsou ještě dány vektory e a l definující nejmenší resp největší čas příjezdu od města.
• SPT - přelévání nádob - graf, kriteriální funkce pro nejmenší počet přelití, kriteriální funkce pro nejmenší množství vylité vody
• Sched - úrovňový algoritmus
• Sched - formulace Psm,1|temp|Cmax pomocí ILP
• Toky - navrhnout síť pro toky pro řešení zaokrouhlování v tabulce + říct, jestli to bude celočíselné a proč
• CP - AC-3 algoritmus
• knapsack - napsat pseudokód pro 2-aproximační knapsack a dokázat, že faktor 2

• ILP - 4 loupežníci - rozhodnout, zda lze lup rozdělit tak, že mezi maximálním dílem a minimálním dílem je rozdíl nejvýše 10% celkové ceny lupu
• SPT - Nejspolehlivější spojení
• Sched - Rozvrh na dva procesory pomocí dyn.prog. (Rothkopf)
• Sched - Metoda větví a mezí s LP pro 1 |prec|suma wjCj a jak na LP prořezávání
• Toky - Ford-Fulkerson - zadaný počáteční přípustný tok, udělat 4 iterace, určit maximální tok a minimální řez
• CP - Prohledávání a propagace
• TSP - Pravděpodobná neexistence r-aproximačního algoritmu pro obecný TSP

• ILP - investice na burze
• Dijkstra - Pomoci dijkstrova algoritmu spoctete vektory l(v) a p(v) pro kazdy v z V(G), je-li l(v) delkou nejkratsi cesty z vrcholu 1 a p(v) je predposledni vrchol na teto ceste (predchudce). Nedefinovane prvky vektoru p(v) oznacte otaznikem. Zaznamenejte 8 iteraci algoritmu.

• LP - Formulujte nejlevnejsi multikomoditni toky - Multikomoditni toky
• Knapsack - n=4, c={10, 20, 30, 10}, w={21, 35, 52, 17}, W=100. Na zaklade principu algoritmu dyn. programovani vysvetlete, zda vami nalezene reseni je jedine optimalni nebo existuje i jine optimalni reseni.
• Slozitost TSP pomoci HK.
• Urovnovy algoritmus + Gantuv diagram.

• List scheduling - Pseudokodem popiste List scheduling, aproximacni algoritmus pro P|prec|Cmax. Uvedte aproximacni faktor tohoto algoritmu pro nesetrideny list uloh. Myslenka LPT algoritmu + odpovidajici aproximacni faktor.

• ILP investice na burze.
• Nejspolehlivější spojení - uvést převod do nejkratších cest, navrhnout svůj algoritmus a říct, jestli bude fungovat s p > 1.
• Dining - toky. Jsou n rodin a q stolů. Potřebujeme,aby za jedním stolem neseděli členy stejné rodiny. Formulovat jako úlohu hledání maximálního toku v síti. (příklad 6.1 na s. 198 v [AMO93])
• Knapsack - n=4, c={10, 2, 0, 30, 10}, w={21, 35, 52, 17}, W=100. Na zaklade principu algoritmu dyn. programovani vysvetlete, zda vami nalezene reseni je jedine optimalni nebo existuje i jine optimalni reseni.
• TSP - Pravděpodobná neexistence r-aproximačního algoritmu pro obecný TSP.
• úrovňový algoritmus.
• Formulovat časem-indexovaný model pro PS 1 |temp| Cmax jako ILP.

• ILP výrobní plán (fixní náklady, sudý počet jednoho výrobku, big M)
• Vyjádřit problém obsazení směn řidičů tak, aby se dal vyřešit pomocí algoritmů na nejkratší cesty. (příklad 4.13 na s. 127 v [AMO93])
• Nalezení počátečního přípustného toku pro Ford-Fulkersonův Algoritmus převést na rozhodovací problém přípustného toku v síti. (popsat algoritmus)
• Knapsack - Kombinace 2-Aproximačního algoritmu a dynamického programování. Napsat pseudokód.
• Dokázat složitost Christofidesova algoritmu.
• Vytvořit rozvrh pomocí Rothkopfa
• Převod PSm, 1 |temp| Cmax na PS1 |temp| Cmax a určení zda je daná instance rozvrhnutelná.

• CP: AC-3 algoritmus (iterace) 8b
• SCHEDULING: PSm,1|temp|Cmax (formulace) 7b
• SCHEDULING: Bratleyho algoritmus (iterace) 7b
• KNAPSACK: 2-aproximační algoritmus (pseudokód a důkaz faktoru) 7b
• FLOWS: Distinct Representatives, př. 6.2 na str. 170 v [AMO93] (formulovat jako úlohu maximálního toku) 7b
• SPT: Bellman-Fordův algoritmus (princip optimality a důkaz správnosti algoritmu) 7b
• ILP: 4 Partition Problem (formulace) 7b

• ILP: Investice do n domů s příjmy z nájmů. Maximalizovat profit při omezení výše investice.
• SPT: Důkaz správnosti Dijkstry
• FLOWS: Zaokrouhlování čísel/řádků/sloupců v 3×3 matici
• TSP: Christofides + o jaký aproximační faktor se jedná
• SCHEDULING: Formulace PSm, 1|temp|Cmax pomocí ILP
• SCHEDULING: Úrovňový algoritmus + ganttův graf
• CP: Iterace AC-3 algoritmu

• ILP: Finanční portfolio
• FLOWS: Nalezení počátečního přípustného toku pro Ford-Fulkersonův Algoritmus převést na rozhodovací problém přípustného toku v síti. (popsat algoritmus)
• FLOWS: Distinct Representatives, př. 6.2 na str. 170 v [AMO93] (formulovat jako úlohu maximálního toku)
• SPT - Nejspolehlivější spojení
• Knapsack - n=4, c={10, 20, 30, 10}, w={21, 35, 52, 17}, W=100. Na zaklade principu algoritmu dyn. programovani vysvetlete, zda vami nalezene reseni je jedine optimalni nebo existuje i jine optimalni reseni.
• TSP: Christofides - o jaký aproximační faktor se jedná + důkaz
• SCHEDULING: Převod PSm, 1 |temp| Cmax na PS1 |temp| Cmax a určení zda je daná instance rozvrhnutelná.

• ILP: Nějaká výroba 5 produktů - formulace
• ILP: 1|prec|wjCj - formulace, k čemu se dá použít relaxované LP řešení při řešení ILP
• FLOWS: 4 iterace Ford-Fulkersona a najít minimální řez
• SPT: Formulace problému tak, aby šel vyřešit Dijkstrou. Máme rozvážkovou službu, která rozváží v době 9-16. K dispozici jsou různé časy směn (9-11, 9-13, 12-14, 12-16, 12-17, 14-16, 15-17… takhle přesně to nebylo, ale tenhle styl).
• SPT: 5 výroků a říct zda platí nebo ne. Pokud platí, dokázat, pokud ne, udělat protipříklad. Výroky typu „když zvýšíme cenu hrany v grafu o násobek k, délka nejkratší cesty se také zvýší k-krát“, „Dijkstrův algoritmus nalezne vždy nejkratší cestu s nejmenším počtem hran“)
• SCHEDULING: Převod 1|rj,dj|Cmax na PS1|temp|Cmax
• TSP: Pravděpodobná neexistence r-aproximačního algoritmu

• ILP: Finanční portfolio
• ILP: 1|prec|wjCj - formulace, k čemu se dá použít relaxované LP řešení při řešení ILP
• FLOWS: Zaokrouhlování čísel/řádků/sloupců v 3×3 matici
• SPT: Najít nejdelší cesty Floydem
• SPT: Nejspolehlivější spojení
• SCHEDULING: Rozvrhnout tasky pomocí Hornova algoritmu, nakreslit gantův diagram a spočítat Lmax
• TSP: Pravděpodobná neexistence r-aproximačního algoritmu, převod na Hamilt. kružnici

• SPT: Důkaz správnosti Dijkstry
• SPT: Formulace problému tak, aby šel vyřešit Dijkstrou. Máme řidiče autobusu a směny v době 9-17. K dispozici jsou různé časy směn (9-11, 9-13, 12-14, 12-16, 12-17, 14-16, 15-17 cca) a ke směnám ceny. Je to někde v knížce Network Flows - Ahuja, Magnanti, Orlin.
• TSP/ILP: Formulace TSP s time windows pomocí ILP
• CP: Hranová konzistence nějakého zadání (AC-3)
• SCH: Převod PSm 1|temp|Cmax na PS 1|temp|Cmax a určení zda je daná instance rozvrhnutelná.
• Knapsack: Dyn. programování, mělo se řešit doplňováním cen do tabulky. 5 předmětů, ceny 1, 6, 18, 22, 28, hmotnosti 1, 3, 5, 6, 7 (cca).
• FLOWS: ILP formulace multikomoditních toků.

• ILP: Real estate investment, klasicky budovy s XORem a dalsi podminky vcetne 2 ze 3 musi platit.
• SCH: Rothkopf, solve P||Cmax by dynamic prog. p=(2,2,1,2), UB=7, R=2
• SCH: Formulate PS1|temp|Cmax as time-indexed ILP
• TSP: Derive approx. factor of Christofides alg. (Nestaci napsat factor. Je potreba napsat, proc ma takovy factor.)
• FLO: Ford-Fulkerson algorithm, 3 iterace vcetne odecitani pres zpetnou hranu + urcit hrany minimum cut
• FLO: Dinning problem - max flow problem, Nekolik rodin je na veceri. Je potreba rozhodit cleny rodin tak, aby nesedeli dva clenove jedne rodiny u stejneho stolu. Je potreba urcit, kdy je reseni feasible.
• SPT: Investment oportunities, Mr. Dow Jones - prednasky SPT na slajdu 29/42

Tip: Ke všemu napište aspoň něco, i když nevíte, něco zkuste - když to má alespoň trochu správnou myšlenku, tak člověk dostane nějaký body a ono se to nasčítá.

• knizka Grafy a jejich aplikace, Jiri Demel; (jsou tam napriklad ty ulohy na nejkratsi cestu delane na tabuli o prednasce)

• knizka Grafy a jejich aplikace, Jiri Demel, OCR verze prohnane pres ABBYY finereader a orezane programem briss; (jsou tam napriklad ty ulohy na nejkratsi cestu delane na tabuli o prednasce)

• kniha Network Flows (odkazovano ze slidu + stejne priklady jako ve slidech), řešení příkladů z knihy

• Knapsack pomocí dynamického programování v detailním příkladu (Pozor, je zde varianta dělaná přes váhy, na přednášce to bylo přes ceny)

• OIS=uplne stejny predmet na stm-wiki

• Prelevani vody

• Poznámky k tokům kolegy Antonína Šulce

• Tabulka algoritmů z přednášek (pro ty, co se jim pletou všechny dohromady )