|
Lecturer(s)
|
-
Ženčák Pavel, RNDr. Ph.D.
|
|
Course content
|
1. The linear programming and simplex method. 2. The principle of duality in linear programming. 3. Dual simplex method, integer programming methods. 4. Transport task: problem formulation and solution methods. 5. Assignment problem: problem formulation and solution methods. 6. Flows in networks: search for minimum and maximum flow. 7. The business traveler's problem (as a sample task): exact methods of solution. 8. Heuristics and meta-heuristics: genetic algorithms, simulated annealing, taboo search, ant colonies. 9. Other applications of combinatorial optimization.
|
|
Learning activities and teaching methods
|
Monologic Lecture(Interpretation, Training), Demonstration
- Attendace
- 52 hours per semester
- Semestral Work
- 50 hours per semester
- Homework for Teaching
- 40 hours per semester
|
|
Learning outcomes
|
The purpose of the course is to supplement the classical (continuous) optimization with knowledge of discrete optimization and to acquaint students with modern methods of solving such problems. A deeper understanding of the given methods will follow in the master program.
Understanding Understand the basic problems of discrete optimization and different approaches to their solution.
|
|
Prerequisites
|
Basic knowledge of numerical methods and classical optimization methods.
|
|
Assessment methods and criteria
|
Student performance, Seminar Work
Colloquium: elaboration of a selected problem by one of the methods of combinatorial optimization, defense in the form of a presentation.
|
|
Recommended literature
|
-
Online přednáška.
-
Online přednáška.
-
Alexander Schrijver. A Course in Combinatorial Optimization.
-
Bernhard Korte, Jens Vygen. (2018). Combinatorial Optimization Theory and Algorithms (6th ed.). Springer.
-
David L. Applegate, Robert E. Bixby, Vašek Chvátal, William J. Cook. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press.
-
Christos H. Papadimitriou,? Kenneth Steiglitz. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.
|