Kombinatorická optimalizace

Cvičení

2019/2020

Úkoly:

Podpůrná videa k jednotlivým cvičením a úkolům od cvičících: Combinatorial Optimization 2020 - Youtube

2014/2015

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

2013/2014

starší/2013

Testy

Semestrálka

Zkouška

Tabulka úloh podle kategorie:

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

Hanzálkův nástin písemné zkoušky:

  • 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

Termín 25.5.2010 (prosím o doplnění)

  • 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

Termín 1.6.2010

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

Termín 15.6.2010

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

Termín 24.5.2011

Termín 31.5.2011

Termín 14.6.2011

  • 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

Termín 24.5.2012

  • 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

Termín 5.6.2012

  • 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

Termín 19.6.2012

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

Termín 21.5.2013

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

Termín 4.6.2013

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

Termín 18. 6. 2013

  • 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

Termín 27. 5. 2014

  • 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

Termín 3. 6. 2014

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

Termín 24. 6. 2014

  • 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

Termín 26. 5. 2015

  • 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

Termín 3. 6. 2015

  • 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ů.

Termín 15. 6. 2015

  • 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

Termín 31. 5. 2016

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

Termín 3.6.2016

  • 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

Termín 13.6.2016

  • 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

Termín 27.6.2016

  • 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

Termín 31.5.2017

  • 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

Termín 7.6.2017

  • 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

Termín 21.6.2017

  • 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

Termín 29.5.2018

  • 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

Termín 05.6.2018

  • 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ů.

Termín 19. 6. 2018

  • 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

Termín 18. 6. 2020

  • ILP: podobni 13.6.2016
  • SPT: přelévání nádob - graf, ceny hran pro nejmenší počet přelití, ceny hran pro nejmenší množství vylité vody
  • Flows: Distinct Representatives
  • Knapsack: 2-approx knapsack pseudokod a dokázat faktor
  • SCHED: ILP formulation scheduling on unrelated parallel
  • SCHED: Bratley's alg. priklad r = (0, 0, 3, 4, 3) p = (2, 3, 2, 2, 3) d = (3, 5, 13, 8, 13)
  • CP - AC-3 algoritmus

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

Studijni materiály

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

  • Prelevani vody

Prelevani vody - nejmensi cesta

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

courses/a4m35ko.txt · Poslední úprava: 2020/06/18 21:24 autor: mykel
Nahoru
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0