PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
Optimalizace velkých problémů: přesné metody - NOPT059
Anglický název: Large-scale optimization: Exact methods
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2023
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: RNDr. Jan Hric (12.05.2022)
Pokročilá přednáška exaktních optimalizačních algoritmů založených na lineárním programování a kombinatorické optimalizaci s aplikacemi na praktické problémy.
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ům různých exaktních optimalizačních metod založených na lineárním programování a kombinatorické optimalizaci 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.

Cunningham, Cook, Pulleyblank, Schrijver. Combinatorial optimization. John Wiley & Sons, 1997

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

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

Sylabus -
Poslední úprava: RNDr. Jakub Bulín, Ph.D. (13.05.2022)
  • 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

V předmětu předpokládáme znalost základů lineárního programování a duality, například z předmětu Lineární programování a kombinatorická optimalizace (NOPT048).

Výuka tohoto předmětu probíhá jednou za dva roky a střídá se s předmětem Optimalizace velkých problémů: metaheuristiky (NOPT061).

 
Univerzita Karlova | Informační systém UK