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

Lagrange relaxace

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

• ILP: Nakup reklam, zadana tabulka zisku hlasovacich hlasu na zaklade poctu vysilani reklamy, nakoupit muzeme maximalne 3 reklamy.
• SPT: Nejspolehlivejsi spojeni, vektor spolehlivosti p rozsah (0,1), vysledne spojeni je produkt vsech spolehlivosti po ceste a)prevod ulohy nejspolehlivejsiho spojeni, aby sel resit Dijkstrou b) Modifikace Dijkstry aby resil tuhle ulohu c) bude a) a b) fungovat, kdyz bude p v rozsahu (0,inf)
• SPT: Dukaz spravnosti Dijkstry
• ILP: Scheduling with temp constraints
• Knapsack: a) Dyn. programovani b) existuje vice optimalnich reseni?
• FLO: Ford-Fulkerson algorithm, 3 iterace vcetne odecitani pres zpetnou hranu + urcit hrany minimum cut
• SCH: Převod PSm 1|temp|Cmax na PS 1|temp|Cmax a určení zda je daná instance rozvrhnutelná.

• ILP: Toy production, maximalize profit , 2 factories, only one is working, 2 type of toys, different production speed per factory and toy type and toy type production initialisation cost
• SPT: Investment oportunities, Mr. Dow Jones - prednasky SPT na slajdu 29/42
• Knapsack: Popsat pseudokódem 2-aproximační algoritmus a vysvětlit proč je 2-aproximační
• Flow: 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ý
• CP: Hranová konzistence nějakého zadání (AC-3)
• SCH: vyřešit rozvrhování na jednom procesoru pomocí Bratleye
• SCH: Formulate PS1|temp|Cmax as time-indexed ILP

• ILP:
  

max f(x1);
f(x1) = 7 + 5*x1 iff x1 > 0;
f(x1) = 0 iff x1 = 0;
abs(x1 - x2) = 0 OR 6
x1, x2 >= 0; x1, x2 < = 100

• 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.
• FLOW: Flow s lower bound != 0 prevest na Flow s lower bound == 0
• TSP: důkaz NP-obtížnosti TSP pomocí polynomiálního převodu z problému Hamiltonovské kružnice na instanci TSP
• 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.
• SCH: PSm 1|temp|Cmax as ILP

• ILP: max z = součet absolutních hodnot s x1 x2 x3 x4
  x1,2,3,4 >= 0
  if x1=0 and x3=0 then x4!=0
  if x1=0 and x2=0 then x3=0 nebo něco podobného
• Tvrzení o sítích a cestcáh - zda jsou pravdivé a proč
• Dinning problem jako max flow
• Vyřešit Chetto, Silly, Bouchentouf algorithm
• Rothkopf
• Jaký faktor má Christofides, odůvodnit podle jeho postupu (byl zahrnut v zadání)
• AC-3 kondenzace

• ILP skolni jidelna - největší chyták byla podmínka, že libovolná kombinace jídel v jeden týden musí mít celkově alespoň p_min proteinů
• ILP osklive prepinani funkci - stejne, jako 13.6.2016
• SPT prelevani vody (podle slov Hanzálka jsme měli i nakreslit ručně graf)
• Flows - zadan tok, udelat iterace Ford-Fulkersona + rict, kolik maximalne iteraci je potreba pro jakoukoliv volbu zlepsujicich cest
• TSP pravdepodobna neexistence r-approx TSP
• CSP iterace AC-3
• scheduling prevod multiprocessor scheduling na PSm,1|temp|Cmax

• SCHED: temporalni omezeni, nakrestli graf a jestli je rozvrhnutelne
• ILP: vyresit Branch and Bounds jako LP solver, do ctvereckovaneho papiru
• TSP: odvodit faktor Christofidesova algoritmu, byl tam napsany ten algoritmus a musel se vysvetlit ten faktor
• Knapsack: vyresit dynamickym programovanim, n=7, W=5, Je reseni unikatni? Jaka bude slozitost pokud W⇐10n?
• FLOW: zaokrouhlovani v 3×3 matici, Budou vysledne toky celociselne?
• TSP: smeny ridicu autobusu
• ILP: formulovat jako ILP nejake rozvrhovani Tn tasku na Rm resources, min Cmax s binarnim parametrem ze nektere 2 tasky nesmi bezet na stejnem R

• ILP: maximalizace souctu dvou absolutnich hodnot, formulovat
• ILP: iterace BaB
• SPT: formulace ulohy, maximalizace zisku pri ceste z A do B, mezi nekterymi dvojicemi mest po ceste si lze privydelat dorucenim zasilky, prime spojeni mezi vsemi mesty, naklady ~ ujeta vzdalenost
• Knapsack: vyresit dynamickym programovanim, c =[…], w = […], W ⇐ 100, Je reseni unikatni?
• FLOW: vyber reprezentantu klubu ve vekovych skupinach a dalsi podminky
• SCHED: EDD dukaz optimality
• CSP: iterace AC-3

• ILP: maximalizace souctu dvou absolutnich hodnot, formulovat
• SPT: dokazat Dijkstru. Byl tam pseudokod celeho algoritmu.
• Knapsack: vyresit dynamickym programovanim, c =[2,2,2,4,3], w = [1,1,2,3,4], W = 5, Je reseni unikatni? Jaka se casova slozitost pokud W ⇐ 10*n
• TSP: Dokazat aproximacni faktor Christofidesova alg. Byl tam pseudokod celeho algoritmu.
• FLOW: family dining problem
• SCHED: Chetto, Silly, Bouchentouf algorithm pro 1|pmtn,prec|r,d|L_max. Vyresit jednu instanci a vypsat hodnoty hlavnich promennych v kazde iteraci algoritmu.
• SCHED: formulovat Time-indexed ILP model for PS1 |temp| C_max

• ILP: stejne jako 13.6.2016, akorat jsou x1,x2 z <0,20>
• SPT: Formulace problému tak, aby šel vyřešit Dijkstrou (zadani na slajdu 6 (7 v prohlizeci) http://www.ifp.illinois.edu/~angelia/ge330fall09_shortpath_l17.pdf )
• TSP: Pravděpodobná neexistence r-aproximačního algoritmu, převod na Hamilt. kružnici
• CP: Hranová konzistence nějakého zadání (AC-3) - stejne jako 24.5.2011
• SCH: Rozvrhnout tasky pomocí Hornova algoritmu, nakreslit gantův diagram a spočítat Lmax
• SCH: Project scheduling with temporal constraints
• FLOWS: ILP formulace multikomoditních toků.

• ILP: Školní Jídelna

Počet jídel M = {1, …,100}, 
pracovních dnů D= {1, …,5}, 
c_m - cena jídla, 
v_m {0,1} - jeslti je jídlo veganské, 
p_m - počet proteinů v jídle, 
p^min - minimální počet proteinů za celý týden. 
Podmínky: 
	- každý den 4 jídla, 
	- alespoň 1 veganské, 
	- minimalizace costu za celý týden, 
	- každé jídlo max jednou za celý týden. 
       - Pocet porci kazdeho jidla z menu je presne 120 
	- Jakákoliv kombinace z jídel v menu za ten týden (1 jídlo denně), musí mít v součtu alespoň p_min proteinů 

• SPT: Max reliability Dijkstra
• Flows: Iterace Ford Fulkerson, najít mincut flow
• Knapsack: 2-approx knapsack pseudokod a dokázat faktor
• TSP: Christofides - napsat pseudokod, říct faktor (nemusel se dokazovat)
• SCHED: Rothkopf p=(2,2,1,2), Cmax=5
• SCHED: ILP formulace - 1|prec|Cmax, jak může LP relaxace pomoci při řešení algoritmem Branch and Bounds

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á.

Kvalitny strucny prehlad toho co je dolezite na skuskach, co sa casto opakuje: ko.pdf

• 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 )