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 [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: vyuč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

Anotace

čeština

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

angličtina

Poslední úprava: RNDr. Jan Hric (12.05.2022)

Lecture on basic and advanced optimization algorithms applicable to practical problems. We discuss exact algorithms based on Linear Programming, heuristic algorithms based on Artificial Intelligence and their combinations in hybrid meta-heuristics for solving real-life optimization problems.

Cíl předmětu

čeština

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.

angličtina

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

Understand the main principles of various optimization methods with

emphasis on large-scale instances. Learn how to apply these methods in

practice.

Podmínky zakončení předmětu

čeština

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.

angličtina

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

Student are expected to implement practical homeworks and to pass

theoretical examination. The nature of homeworks excludes the

possibility of repeated attempts to get credit.

Literatura

čeština

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

čeština

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)

angličtina

Poslední úprava: RNDr. Jiří Fink, Ph.D. (13.05.2022)

Exact methods:

• Linear programming, duality, complementary slackness

• Integer linear programming, Branch and bound

• Gomory-Chvátal cutting plane, lazy constraint

• Column generation, Dantzig-Wolve decomposition

• Lagrange relaxation

• Multi-objective optimization, Pareto optimality

• Applications, e.g. Cutting Stock Problem, Vehicle Routing Problems, Job Scheduling

Hybrid meta-heuristics

• Local search, Hill climbing, Simulated annealing

• Population methods, e.g. Genetic algorithms

• Problem instance reduction, Large neighborhood search

• Hybrid methods: Lamarckian vs. Baldwinian learning, examples

• Surrogate models

• Applications, e.g. Minimum Common String Partition, Minimum Weight Dominating Set Problem, Arc Routing Problems, Public Transportation

Recommended prerequisite: Linear Programming and Combinatorial

Optimization (NOPT048)