Course detail

Optimization Methods II

FSI-VPP-AAcad. year: 2027/2028

The course introduces mathematical and computational methods for multistage decision-making, optimal control, and the solution of complex engineering optimization problems. The main emphasis is on Bellman's principle of optimality and dynamic programming for deterministic and stochastic problems with finite and infinite horizons. The topics include shortest-path algorithms, hidden Markov models and the Viterbi algorithm, multiobjective optimization, and constrained optimization.

Further topics include continuous-time optimal control, the Hamilton–Jacobi–Bellman equation, Pontryagin's maximum principle, linear-quadratic regulation (LQR), Kalman filtering, and model predictive control. The course also covers approximate dynamic programming and heuristic optimization methods, including evolution strategies, genetic algorithms, and ant colony optimization.

Computer-assisted exercises focus on mathematical modeling, implementation of selected algorithms, computational experiments, and interpretation of results. Applications include sequential decision-making, graph optimization, control of dynamical systems, and combinatorial optimization problems, including production scheduling.

Language of instruction

English

Number of ECTS credits

7

Assignment to study programme types

Master's

Mode of study

Not applicable.

Guarantor

doc. Ing. Jakub Kůdela, Ph.D.

Department

Institute of Automation and Computer Science (ÚAI)

Offered to foreign students

Of all faculties

Entry knowledge

Students are expected to have basic programming skills, including familiarity with variables, data structures, functions, and control flow, and the ability to implement and test simple algorithms.

Required mathematical knowledge includes fundamentals of linear algebra (vectors, matrices, and systems of linear equations), mathematical analysis (differential and integral calculus, functions of several variables), set theory, probability, and statistics. Students should be able to formulate a simple mathematical optimization problem and interpret its solution.

Previous experience with mathematical optimization and the modeling of dynamical systems is beneficial.

Rules for evaluation and completion of the course

Course-unit credit: Active participation in the seminars, elaboration of a given project. Examination: Written and oral.
Attendance at seminars is required. An absence can be compensated for via solving additional problems.

Aims

Upon successful completion of the course, students will be able to:

  1. Formulate deterministic and stochastic multistage decision problems by identifying states, decisions, transitions, objective functions, and constraints, and construct appropriate mathematical models.

  2. Derive and apply Bellman recursions and implement selected dynamic programming algorithms, including shortest-path algorithms and the Viterbi algorithm.

  3. Analyze finite- and infinite-horizon decision problems, compare exact and approximate dynamic programming approaches, and assess their computational complexity and limitations.

  4. Explain and apply selected principles of discrete- and continuous-time optimal control, including basic LQR problems, state estimation using Kalman filtering, and model predictive control, and interpret optimality conditions based on the Hamilton–Jacobi–Bellman equation and Pontryagin's maximum principle.

  5. Formulate and solve selected constrained and multiobjective optimization problems, compare feasible solutions, and evaluate trade-offs among conflicting objectives.

  6. Implement and experimentally evaluate selected heuristic and metaheuristic algorithms for combinatorial and scheduling problems, comparing solution quality, computational requirements, and the suitability of different approaches.

Study aids

To support their studies, students are provided with materials for lectures and computer exercises. These materials are made available via the university's e-learning environment.

Prerequisites and corequisites

Not applicable.

Basic literature

Bazaraa, M, S.; Sherali, H. D.; Shetty, C. M.: Nonlinear Programming. Wiley, 2013. (EN)
Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. I. Athena Scientific, Nashua. 2017. (EN)
Brucker, P.: Scheduling Algorithms. Springer-Verlag, Berlin, 2010. (EN)
Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, 2014. (EN)
Martí, R. Pardalos, P.M., Resende, M.G.C.: Handbook of Heuristics. Springer Cham, 2025. (EN)
Luke, S.: Essentials of Metaheuristics: A Set of Undergraduate Lecture Notes. Lulu.com, 2016. (EN)
Puterman, M. L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience, New Jersey, 2005. (EN)

Recommended reading

Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B.: Network Flows. Prentice Hall, Upper Saddle River, New Jersey, 1993. (EN)
Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. II: Approximate Dynamic Programming. Athena Scientific, Nashua. 2012. (EN)
Boyd, S; Vandenberghe, L.: Convex Optimization. Cambridge University Press, 2004. (EN)
Kerzner, H.: Project Management: A Systems Approach to Planning, Scheduling, and Controlling. Wiley, New Jersey, 2009. (EN)
Pinedo, M. L.: Scheduling: Theory, Algorithms, and Systems. Springer-Verlag, Cham, 2016. (EN)
Winston W.L.: Operations Research. Applications and Algorithms. Thomson - Brooks/Cole, Belmont 2004. (EN)

Classification of course in study plans

  • Programme N-AIŘ-P Master's 2 year of study, winter semester, compulsory

Type of course unit

 

Lecture

39 hours, optionally

Teacher / Lecturer

doc. Ing. Jakub Kůdela, Ph.D.

Syllabus

1. Basics of mathematical processes theory. Bellman optimality principle and dynamic programming.
2. Deterministic finite-state problems. Forward DP algorithm.
3. Hidden Markov models and the Viterbi algorithm.
4. Algorithms for shortest paths in a graph.
5. Multicriteria and constrained optimal control problems.
6. LQR a Kalman filter. Problems without perfect state information.
7. Problems with an infinite number of stages.
8. Deterministic continuous-time optimal control, Hamilton-Jacobi-Bellman equation, Pontryagin maximum principle.
9. Heuristics for complex problems I - evolution strategies.
10. Heuristics for complex problems II - genetic algorithms and ant colony optimization.
11. Approximate dynamic programming.
12. Rolling horizon and Model predictive control.
13. Process scheduling.

Computer-assisted exercise

26 hours, compulsory

Teacher / Lecturer

doc. Ing. Jakub Kůdela, Ph.D.

Syllabus

Implementation and analysis of the following problems:
1. - 3. Basic dynamic programming problems.
4. Problems with time delays.
5. Viterbi algorithm for decoding convolutional codes.
6. Shortest path problems.
7. Multiobjective problems.
8. LQR.
9. Infinite horizon problems.
10. Continuous-time problems.
11. Evolution strategies for weighted MAX-SAT.
12. Genetic algorithms and ant colony optimization for TSP.
13. Process scheduling problems.