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 2024
• 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: 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: RNDr. Jakub Bulín, Ph.D.; RNDr. Jiří Fink, Ph.D.; Mgr. Marika Ivanová, Ph.D.
• Vyučující: 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

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.

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

angličtina

Advanced lecture on exact optimization algorithms based on Linear Programming and Convex Optimization for solving real-life problems.

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

Cíl předmětu

čeština

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. (Předmět je vhodný pro studenty 3. ročníku bakalářského studia, a pro magisterské studenty.)

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

angličtina

Understand the main principles of various exact optimization methods based on linear programming and combinatorial optimization with emphasis on large-scale instances. Learn how to apply these methods in practice. (The course is suitable for 3rd-year bachelor's students and for master's students.)

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

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

čeština

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.

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

angličtina

Students are expected to implement practical homework assignments and pass theoretical examination. The nature of homework assignments excludes the possibility of repeated attempts to get credit.

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

Literatura

čeština

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.

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

Sylabus

čeština

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

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

angličtina

• Linear programming, duality, complementary slackness

• Integer linear programming, Branch and bound

• Gomory-Chvátal cutting plane, lazy constraint

• Column generation, Dantzig-Wolve decomposition

• Lagrangian relaxation

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

Knowledge of the basics of linear programming and duality will be expected, recommended prerequisite: Linear Programming and Combinatorial Optimization (NOPT048).

The course is taught bi-yearly, alternating with the course Large-scale optimization: Metaheuristics (NOPT061).

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