Subjects

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

Large-scale optimization - NOPT059

Title:	Optimalizace velkých problémů
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2021 to 2021
Semester:	winter
E-Credits:	5
Hours per week, examination:	winter s.:2/2 [hours/week]
Capacity:	unlimited
Min. number of students:	unlimited
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
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 WS schedule Noticeboard

Annotation -

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

Aim of the course -

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

Course completion requirements -

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

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.

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.

Syllabus -

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