Advanced lecture on exact optimization algorithms based on Linear
Programming and Convex Optimization for solving real-life problems.
Last update: 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.
Aim of the course -
Last update: RNDr. Jakub Bulín, Ph.D. (06.05.2024)
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.
Last update: RNDr. Jakub Bulín, Ph.D. (06.05.2024)
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.
Course completion requirements -
Last update: RNDr. Jakub Bulín, Ph.D. (13.05.2022)
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.
Last update: 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.
Literature -
Last update: 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.
Desaulniers, Guy, Jacques Desrosiers, and Marius M. Solomon, eds. Column generation. Vol. 5. Springer Science & Business Media, 2006.
Syllabus -
Last update: RNDr. Jakub Bulín, Ph.D. (13.05.2022)
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
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).
Last update: 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).