Course detail

Optimization Methods II

FSI-VPP-AAcad. year: 2021/2022

The course deals with the following topics: Dynamic programming and optimal control of stochastic processes. Bellman optimality principle as a tool for optimization of multistage processes with a general nonlinear criterion function. Optimum decision policy. Computational aspects of dynamic programming in discrete time. Hidden Markov models and the Viterbi algorithm. Project management, CMP and PERT methods. Algorithms for shortest paths in graphs and the branch and bound method. Multicriteria control problems. Deterministic optimal control in continuous time, Hamilton-Jacobi-Bellman equation, Pontryagin maximum principle. LQR and Kalman filter. Process scheduling and planning. Problems with infinitely many stages. Applications of the methods in solving practical problems.

Language of instruction

English

Number of ECTS credits

6

Mode of study

Not applicable.

Guarantor

Ing. Jakub Kůdela, Ph.D.

Department

Institute of Automation and Computer Science (ÚAI)

Offered to foreign students

Of all faculties

Learning outcomes of the course unit

Knowledge: Students will know basic principles and algorithms of methods applicable to the optimization of the deterministic and stochastic, discrete and continuous. They will be made familiar with basic principles and algorithms of methods that are appropriate to creation of decision-support systems for project management, as the tool for the identification, selection and realization of projects. Skills: Students will be able to apply the above methods to the solution of the practical problems from economic decision, problems of increasing the reliability of technological devices, problems of automation control of technological processes and problems of project management, by using contemporary tools of computer science.

Prerequisites

Knowledge of the basics of programming, mathematical analysis, algebra, theory of sets, statistics and probability.

Co-requisites

Not applicable.

Planned learning activities and teaching methods

The course is taught through lectures explaining the basic principles and theory of the discipline. Exercises are focused on practical topics presented in lectures.

Assesment methods and criteria linked to learning outcomes

Course-unit credit: Active participation in the seminars, elaboration of a given project. Examination: Written and oral.

Course curriculum

Not applicable.

Work placements

Not applicable.

Aims

The aim of the course is to inform the students about creations and applications of mathematical methods for optimal control of technological and economic processes e.g. in the automation of mechanical systems, in the management of production in mechanical engineering, in project management and in optimization of information systems, using contemporary tools of computer science.

Specification of controlled education, way of implementation and compensation for absences

Attendance at seminars is required. An absence can be compensated for via solving additional problems.

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. I. Athena Scientific, Nashua. 2017.
Puterman, M. L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience, New Jersey, 2005.
Brucker, P.: Scheduling Algorithms. Springer-Verlag, Berlin, 2010.
Bazaraa, M, S.; Sherali, H. D.; Shetty, C. M.: Nonlinear Programming. Wiley, 2013.

Recommended reading

Bertsekas, D. P.: Dynamic Programming and Optimal Control: Vol. II: Approximate Dynamic Programming. Athena Scientific, Nashua. 2012.
Pinedo, M. L.: Scheduling: Theory, Algorithms, and Systems. Springer-Verlag, Cham, 2016.
Kerzner, H.: Project Management: A Systems Approach to Planning, Scheduling, and Controlling. Wiley, New Jersey, 2009.
Klapka, J.; Dvořák, J.; Popela, P.: Metody operačního výzkumu. VUTIUM, Brno, 2001.
Winston W.L.: Operations Research. Applications and Algorithms. Thomson - Brooks/Cole, Belmont 2004.
Volek, J; Linda, B.: Teorie grafů - aplikace v dopravě a veřejné správě. Univerzita Pardubice, 2012.
Boyd, S; Vandenberghe, L.: Convex Optimization. Cambridge University Press, 2004.
Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B.: Network Flows. Prentice Hall, Upper Saddle River, New Jersey, 1993.

Classification of course in study plans

  • Programme N-ENG-Z Master's, 1. year of study, winter semester, recommended
    , 2. year of study, winter semester, recommended

Type of course unit

 

Lecture

39 hours, optionally

Teacher / Lecturer

Ing. Jakub Kůdela, Ph.D.

Syllabus

1. Basics of mathematical processes theory. Bellman optimality principle and dynamic programming.
2. Minimax (robust) formulation. Reformulations and state augmentation.
3. Deterministic finite-state problems. Forward DP algorithm.
4. Hidden Markov models and the Viterbi algorithm.
5. Basics of network analysis, topological ordering, CPM.
6. Calculation by stochastic evaluation of activities (PERT method).
7. Algorithms for shortest paths in a graph, the branch and bound method.
8. Multicriteria and constrained optimal control problems.
9. Deterministic continuous time optimal control, Hamilton-Jacobi-Bellman equation, Pontryagin maximum principle.
10. LQR a Kalman filter.
11. Problems with an infinite number of stages.
12. Process scheduling.
13. Approximate dynamic programming and Model predictive control.

Computer-assisted exercise

26 hours, compulsory

Teacher / Lecturer

Ing. Jakub Kůdela, Ph.D.

Syllabus

1. Solving dynamic programming problems in Matlab.
2. Resource allocation problems.
3. Dynamic programming in stochastic processes, optimizing a repair schedule.
4. State augmentation, optimal inventory control.
5. Viterbi algorithm, decoding of convolutional codes.
6. Examples of project graphs and networks. Implementation of CPM.
7. Numerical applications of the PERT method.
8. Algorithms for shortest paths in a graph, implementation of the A* algorithm.
9. Implementation of the branch and bound method.
10. Multicriteria knapsack problem.
11. LQR, drone control.
12. Job scheduling.
13. Semestral projects.