460-4091/01 – Kombinatorická optimalizace (KO)
| Garantující katedra | Katedra informatiky | Kredity | 4 |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. | Garant verze předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
| Ročník | 1 | Semestr | letní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2015/2016 | Rok zrušení | 2022/2023 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Student po úspěšném absolvování předmětu:
- rozumí základním pojmům z oblasti kombinatorické optimalizace (včetně příslušných pojmů teorie grafů, lineárního programování, výpočtové složitosti apod.)
- umí klasifikovat praktické problémy, které se dají vhodně modelovat jako problémy kombinatorické optimalizace
- umí sestavit k praktickým problémům příslušné vhodné modely
- umí u základních problémů rozlišit, které jsou řešitelné polynomiálními algoritmy a které jsou NP-těžké
- má přehled o metodách řešení úloh lineárního programování a celočíselného lineárního programování a umí je používat
- rozumí myšlenkám základních polynomiálních algoritmů
- má přehled o základních aproximačních algoritmech u NP-těžkých problémů a obecně použitelných heuristických přístupech
- umí pracovat se softwarovými nástroji pro řešení úloh kombinatorické optimalizace
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Mnohé problémy každodenní (průmyslové) praxe jsou de facto optimalizačními problémy: v množině přípustných řešení (např. přidělení úkolů pracovníkům či procesorům, naplánování vozidel a jejich tras pro zásobování, návrh rozmístění elektronických součástek na desce plošných spojů) hledáme takové řešení, které je z nějakého hlediska (např. ceny, času) optimální. Tyto problémy lze často formulovat jako problémy kombinatorické (nebo též diskrétní) optimalizace, většinou v pojmech grafů a (celočíselných) lineárních nerovnic. Některé problémy lze uspokojivě řešit rychlými polynomiálními algoritmy, u jiných (NP-těžkých) se musíme spokojit s algoritmy, které jen aproximují optimální řešení, či s jinými (heuristickými) algoritmy, které dávají rozumné výsledky, byť jejich kvalita není obecně garantována.
Cílem předmětu je přiblížení oblasti kombinatorické optimalizace, klasifikace problémů, které zde patří, a osvětlení metod používaných k jejich praktickému řešení.
Povinná literatura:
- Jon Lee: A first course in combinatorial optimization, Cambridge
University Press, 2004
Doporučená literatura:
- Bernhard Korte, Jens Vygen: Combinatorial Optimization (Theory and Algorithms), Springer (5th edition 2012)
- Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization:
Algorithms and Complexity, Dover Publications, 1998.
- Malik Ghallab, Dana Nau, Paolo Traverso: Automated Planning: Theory & Practice, Morgan Kaufmann, 2004.
- Alexander Schrijver: Combinatorial Optimization (3 volume, A,B, & C),
Springer, 2003.
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Nejsou kladeny další požadavky na studenty.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Osnova přednášek:
1. Přehled kursu. Obecná definice (diskrétních) optimalizačních problémů. Příklady typických úloh kombinatorické optimalizace, modelovaných v pojmech teorie grafů. Příklady problémů řešitelných "hladovým přístupem" (např. problém minimální kostry). Obecný důkaz korektnosti v pojmech matroidů.
2. Další konkrétní problémy řešitelné rychlými (polynomiálními) algoritmy. Připomenutí problémů nejkratší cesty, maximálního toku v sítích, maximálního párování; myšlenky příslušných algoritmů.
Polynomiální převeditelnost mezi problémy.
3. NP-obtížné problémy (problém SAT a MAX-SAT, problém obchodního cestujícího [TSP], problémy rozvrhování, apod.). Myšlenka Cookovy věty (NP-úplnost problému SAT) a důkazy NP-obtížnosti pomocí polynomiální převeditelnosti.
4. Celočíselné lineární programování (ILP). Formulace problémů kombinatorické optimalizace jako instancí problémů ILP. NP-obtížnost ILP.
5. Lineární programování (tj. "relaxované" ILP). Formulace úloh lineárního programování. Princip duality.
6. Řešení úloh lineárního programování; simplexová metoda. Diskuse polynomiální složitosti lineárního programování.
7. Řešení úloh ILP. Totálně unimodulární matice. Metoda větvení a mezí (branch and bound).
8. Další metody řešení úloh ILP. Metoda řezů (cutting planes).
9. Pseudopolynomiální algoritmy a aproximační algoritmy ilustrované např. na problému batohu (knapsack problem). Zmínka o heuristických přístupech řešení NP-obtížných problémů.
10. Další aproximační algoritmy a přístupy (aproximace problému TSP, metoda simulovaného žíhání).
11. Špatně aproximovatelné problémy. PCP (Probabilistically Checkable
Proofs) teorém a jeho aplikace na problém maximální kliky v grafu.
12. a 13. Různé varianty problémů plánování a rozvrhování a jejich řešení.
(Rozvrhování pro jeden procesor a pro paralelní procesory.)
14. Shrnutí kursu a zopakování hlavních pojmů a myšlenek.
Osnova počítačových cvičení:
Cvičení jsou uvedena jako počítačová, jelikož budou zahrnovat i
řešení problémů pomocí softwarových nástrojů, např. k řešení úloh
lineárního programování. Významná část cvičení bude ale věnována i
řešením problémů u tabule. Půjde o procvičení pojmů a metod probraných
na příslušných přednáškách; osnova cvičení tedy kopíruje osnovu přednášek.
Budou využívány standardní volně šiřitelné softwarové nástroje.
1. Řešení konkrétních instancí problémů minimální kostry, plánování
úloh na jednom procesoru a dalších problémů, kde funguje hladový
přístup. Procvičení pojmu matroid a důkazů korektnosti hladového
přístupu u váhových funkcí.
2. Rozbor složitosti algoritmů pro hledání nejkratší cesty v grafu.
Formulace problému jako úlohy lineárního programování.
Řešení instancí problémů maximálního toku v sítích a maximálního
párování.
3. Hledání polynomiálních redukcí prokazujících NP-obtížnost (variant)
problému obchodního cestujícího [TSP], grafových problémů, problémů
rozvrhování.
4. Formulace konkrétních optimalizačních problémů jako jako problémů
celočíselného lineárního programování a řešení konkrétních instancí.
5. Procvičení principu duality v lineárním programování na konkrétních
příkladech.
6. Řešení konkrétních instancí simplexovou metodou a jejími
variantami.
7. Problémy zachycené totálně unimodulárními maticemi.
Procvičení metoda větvení a mezí (branch and bound).
8. Procvičení dalších metod řešení úloh ILP. Metoda řezů (cutting planes).
9. Rozbor vybraných pseudopolynomiálních algoritmů
a aproximačních algoritmů.
10. Návrh aproximačních algoritmů pro vybrané NP-obtížné optimalizační
problémy.
11. Provedení důkazů špatné aproximovatelnosti vybrané NP-obtížných
problémů.
12. a 13. Řešení konkrétních instancí problémů plánování a
rozvrhování, pro jeden procesor i pro více procesorů.
14. Zopakování hlavních pojmů a metod, které budou prověřeny zkouškou.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky