Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Large-scale optimization: Exact methods - NOPT059

Title:	Optimalizace velkých problémů: přesné metody
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2023
Semester:	summer
E-Credits:	5
Hours per week, examination:	summer s.:2/2, C+Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	not taught
Language:	Czech, English
Teaching methods:	full-time
Teaching methods:	full-time
Additional information:	http://ktiml.mff.cuni.cz/~bulin/optimization/

Guarantor:	Mgr. Marika Ivanová, Ph.D. RNDr. Jakub Bulín, Ph.D. RNDr. Jiří Fink, Ph.D.
Class:	Informatika Mgr. - Teoretická informatika Informatika Mgr. - Diskrétní modely a algoritmy
Classification:	Informatics > Informatics, Software Applications, Computer Graphics and Geometry, Database Systems, Didactics of Informatics, Discrete Mathematics, External Subjects, General Subjects, Computer and Formal Linguistics, Optimalization, Programming, Software Engineering, Theoretical Computer Science, Optimalization

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: RNDr. Jan Hric (12.05.2022)

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

Aim of the course -

Last update: RNDr. Jakub Bulín, Ph.D. (13.05.2022)

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.

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.

Literature -

Last update: 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.

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