Combinatorial optimization
Code  Completion  Credits  Range  Language 

MIKOP  Z,ZK  5  2P+2C  Czech 
 Lecturer:
 Jan Schmidt (guarantor)
 Tutor:
 Jan Schmidt (guarantor), Petr Fišer
 Supervisor:
 Department of Digital Design
 Synopsis:

The students will gain knowledge and understanding necessary deployment of combinatorial heuristics at a professional level. They will be able not only to select and implement but also to apply and evaluate heuristics for practical problems.
 Requirements:
 Syllabus of lectures:

1. Discrete optimization, examples of practical tasks. Combinatorial problems. Algorithm complexity, problem complexity.
2. Models of computation. The classes P and NP. Polynomial hierarchy.
3. The notion of completeness. Complexity comparison techniques. The classes NPcomplete, NPhard and NPI.
4. The classes PO and NPO and their structure. Deterministic approximation algorithms. Classification of approximative problems. Pseudopolynomial algorithms. Randomization and randomized algorithms.
5. Communication and circuit complexity
6. Practical deployment of heuristic and exact algorithms. Experimental evaluation.
7. Local methods: state space and search space, exact methods, heuristics.
8. Simulated annealing.
9. Simulated evolution: taxonomy, genetic algorithms.
10. Advanced genetic algorithms: competent GA, fast messy GA, Stochastic optimization: models and applications. Bayesian optimization.
11. Tabu search.
12. Global methods, taxonomy of decompositionbased methods. Exact and heuristic global methods, the DavisPutnam procedure seen as a global method.
13. Reserved
 Syllabus of tutorials:

1. Seminar: terminology, examples of complexity.
2. Seminar: examples of state space.
3. Homework consultation when required, selfstudy: dynamic programming revision.
4. Solved problems session: the classes P and NP, complexity proofs, problems beyond NP.
5. Solved problems session: completeness, reductions.
6. Homework consultation when required.
7. Homework consultation when required.
8. Homework consultation when required.
9. Midterm test.
10. Homework consultation when required.
11. Solved problems session: advanced heuristics, applications.
12. Homework consultation when required.
13. Homework consultation when required.
14. Backup test term, evaluation.
 Study Objective:

Many practical tasks are computationally infeasible. The course is about fast algorithms for such problems, both exact and heuristic. Heuristic algorithms tend to be simple to program, but difficult to configure and deploy. Their successful application requires a deeper understanding of their operation and complexity theory. A series of individual works guides the student from simple techniques to solutions of practically significant problems.
 Study materials:

1. Arora, S. : Computational Complexity: A Modern Approach. Cambridge University Press, 2017. ISBN 9781316612156.
2. Hromkovic, J. : Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics 2nd Edition. Springer, 2004. ISBN 978 3540441342.
3. Kučera, L. : Kombinatorické algoritmy. SNTL, 1993.
4. Ausiello, G.  Crescenzi, P.  Kann, V.  Gambosi, G.  Spaccamela, A. M. : Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 2003. ISBN 3540654313.
 Note:
 Further information:
 https://moodle.fit.cvut.cz/courses/MIKOP/
 Timetable for winter semester 2018/2019:

06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Fri Thu Fri  Timetable for summer semester 2018/2019:
 Timetable is not available yet
 The course is a part of the following study plans:

 Specialization Computer Science, Presented in Czech, Version 2018 to 2019 (compulsory course in the program)