|
Lecturer(s)
|
-
Ženčák Pavel, RNDr. Ph.D.
-
Vodák Rostislav, doc. 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
|
|
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.
KMA/DM and KAG/LA1A and KMI/ALGO1
|
|
Assessment methods and criteria
|
Mark, Oral exam, Student performance, Seminar Work
Oral exam. To obtain credit, active participation in exercises, preparation of a seminar paper and successful completion of credit tests are required.
|
|
Recommended literature
|
-
Applegate, D. L., Bixby, R. E., Chvátal, V., Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study.
-
Du, D. Z., Pardalos, P. M., Hu, X., Wu. (2022). Introduction to combinatorial optimization. Springer Optimization and Its Applications. Cham, Switzerland.
-
Korte, B., Vygen, J. (2018). Combinatorial Optimization. Theory and Algorithms. 6th edition. Springer.
-
Papadimitriou, Ch. H.,? Steiglitz K. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.
-
Pinar, M. Ç., Akkaya, D. (2023). Problems and Solutions for Integer and Combinatorial Optimization: Building Skills in Discrete Optimization. SIAM.
|