PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
Optimalizace velkých problémů - NOPT059
Anglický název: Large-scale optimization
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2021 do 2021
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: http://ktiml.mff.cuni.cz/~bulin/optimization/
Garant: Mgr. Marika Ivanová, Ph.D.
RNDr. Jakub Bulín, Ph.D.
RNDr. Jiří Fink, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Informatika, Aplikační software, Počítačová grafika a geometrie, Databázové systémy, Didaktika informatiky, Diskrétní matematika, Předměty širšího základu, Předměty obecného základu, Počítačová a formální lingvistika, Optimalizace, Programování, Softwarové inženýrství, Teoretická informatika, Optimalizace
Anotace -
Poslední úprava: RNDr. Jan Hric (12.05.2022)
Přednáška základních a pokročilých algoritmů s aplikacemi na praktické problémy. Diskutujeme exaktní algoritmy založené na lineárním programování, heuristické algoritmy Umělé inteligence a jejich kombinace v hybridních metaheuristikách pro řešení reálných problémů.
Cíl předmětu -
Poslední úprava: RNDr. Jakub Bulín, Ph.D. (13.05.2022)

Cílem předmětu je porozumění principů různých optimalizačních metod

použitelných na velké instance pocházejících z praxe.

Podmínky zakončení předmětu -
Poslední úprava: RNDr. Jakub Bulín, Ph.D. (13.05.2022)

Studenti musí implementovat praktické domácí úkoly a splnit teoretickou

zkoušku. Povaha domácích úkolů vylučujeme možnost opakování zápočtu.

Literatura -
Poslední úprava: RNDr. Jakub Bulín, Ph.D. (13.05.2022)

Wolsey, Laurence A. Integer programming. Vol. 42. New York: Wiley, 1998.

Kochenderfer, Mykel J., and Tim A. Wheeler. Algorithms for optimization. Mit Press, 2019.

Blum, Christian, and Günther R. Raidl. Hybrid Metaheuristics: Powerful Tools for Optimization. Springer, 2016.

Desaulniers, Guy, Jacques Desrosiers, and Marius M. Solomon, eds. Column generation. Vol. 5. Springer Science & Business Media, 2006.

Sylabus -
Poslední úprava: RNDr. Jiří Fink, Ph.D. (13.05.2022)
Exaktní metody:
  • Lineární programování, dualita, komplementarita
  • Celočíselné lineární programování, větvení a mezí
  • Řezné nadroviny, generování podmínek
  • Generování sloupců, Dantzig-Wolve dekompozice
  • Lagrange relaxace
  • Vícekriteriální optimalizace, Pareto optimalita

Hybridní meta-heuristiky

  • Lokální prohledávání, Hill climbing, simulované žíhání
  • Populační metody, např. Genetické algoritmy
  • Řešení úloh pomocí redukce velikosti instance
  • Hybridní metody: Lamarckian vs. Baldwinian, příklady
  • Náhradní modely
  • Aplikace, např. v oblastech logistiky a plánování

Doporučená prerekvizita: Lineární programování a kombinatorická

optimalizace (NOPT048)

 
Univerzita Karlova | Informační systém UK