|
Lecturer(s)
|
-
Marek Josef, doc. Ing. Ph.D.
|
|
Course content
|
1. Linear programming. Geometry of linear inequalities. Polyhedra. 2. Polyhedral combinatorics. Farkas lemma. Duality. Matrix games. 3. Simplex method. Dual simplex method. Sensitivity analysis. 4. Homotopy. Parametric programming. Revised simplex method. 5. Column generation method. Dantzig-Wolfe decomposition. 6. Integer and mixed integer linear programming. Cuts. LP and Lagrangian relaxation. Branch and bounds, branch and price, branch and cuts methods. 7. Nonlinear optimisation. Convex optimisation. KKT conditions. Duality. 8. Interior point methods for linear programming. Central path. Quadratic programming. 9. Semidefinite programming. Spectrahedrons. Duality. Vector programming. Interior points methods. 10. Cone programming. Nonlinear integer programming. 11. Multicriteria optimisation. Fuzzy optimisation. Stochastic optimisaton. 12. Robust optimisation. Hierarchical (multilevel) optimisation. Stackelberg games. 13. Approximation algorithms. Modern heuristics methods. Solution space of discrete optimisation problems and its analysis. Constraint programming. 14. Parallel algorithms for linear and semidefinite programming.
|
|
Learning activities and teaching methods
|
Interactive lecture, Lecture, Practicum
- Preparation for an examination (30-60)
- 56 hours per semester
- Preparation for comprehensive test (10-40)
- 35 hours per semester
- Contact hours
- 52 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| vysvětlit základní pojmy lineární algebry |
| vysvětlit základní pojmy matematické analýzy |
| vysvětlit základní pojmy teorie pravděpodobnosti |
| Skills |
|---|
| vyřešit základní úlohy lineární algebry |
| analyzovat jednoduché úlohy optimalizace funkcí |
| zhodnotit výpočetní složitost jednoduchých algoritmů |
| Competences |
|---|
| N/A |
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| formulovat standardní úlohy diskrétní optimalizace |
| vysvětlit základní optimalizační metody |
| vysvětlit použití relaxačních metod |
| klasifikovat optimalizační úlohy podle jejich aproximovatelnosti |
| Skills |
|---|
| řešit standardní úlohy diskrétní optimalizace |
| aplikovat aproximační algoritmy na standardní optimalizační úlohy |
| analyzovat složitější úlohy diskrétní optimalizace |
| posoudit vhodnost aproximačních a heuristických algoritmů pro danou úlohu |
| Competences |
|---|
| N/A |
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecture |
| Interactive lecture |
| Practicum |
| Skills |
|---|
| Practicum |
| Interactive lecture |
| Competences |
|---|
| Practicum |
| Interactive lecture |
| assessment methods |
|---|
| Knowledge |
|---|
| Oral exam |
| Skills |
|---|
| Skills demonstration during practicum |
| Test |
| Oral exam |
| Competences |
|---|
| Oral exam |
| Test |
|
Recommended literature
|
-
Ehrgott, Matthias. Multicriteria optimization. Second edition. 2010. ISBN 978-3-642-05975-9.
-
Korte, Bernhard; Vygen, Jens. Combinatorial optimization : theory and algorithms. 2nd ed. Berlin : Springer, 2002. ISBN 3-540-43154-3.
-
Schrijver, A. Combinatorial optimization polyhedra and efficiency. Berlin : Springer-Verlag, 2004. ISBN 3-540-20456-3.
-
Vanderbei, Robert J. Linear programming : foundations and extensions. Fifth edition. 2020.
|