Combinatorial Optimization

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Digital Design

Synopsis:

The students will gain the knowledge and understanding necessary to judge combinatorial problems by their complexity and deployment target (on-line, multicriterial, etc.).

They will be able not only to select and implement but also to apply and evaluate heuristics for practical problems.

Requirements:

Algorithm, computational complexity, asymptotic complexity. Formal languages. Basic graph theory. Random variable. Boolean logic. Branch and bound algorithm. Basic dynamic programming. Practical programming in any imperative language.

Syllabus of lectures:

1. Combinatorial problems and algorithms.

2. Experimental algorithmics, experimental evaluation of algorithms.

3. The P a NP classes, complementary problems, polynomial hierarchy.

4. NP-complete decision problems, NP-hard optimization problems.

5. Decision problems in practice: transformations to SAT and SMT.

6. Optimization problems in practice: transformation to ILP and CSP.

7. State space, search state, movements in state space, local heuristics, branch and bound

8. Randomized algorithms. Experimental tuning and deployment of parametrized heuristics.

9. Simulated annealing.

10. Simulated evolution I: taxonomy, genetic algorithms, genetic programming.

11. Simulated evolution II: evolution strategy, fast messy GA, Stochastic optimization: models and applications. Bayesian optimization.

12. Global methods, taxonomy of decomposition-based methods. Exact and heuristic global methods, the Davis-Putnam procedure seen as a global method.

13. Multicriterial optimization.

Syllabus of tutorials:

1. Introduction, Satisfiability Problem (SAT), Knapsack Problem.

2. Problem examples, finding configuration variables.

3. Simple SAT algorithms: evaluation on a single instance.

4. Simple SAT algorithms: evaluation on ensembles.

5. Classes P, NP, NPC, NPH, completeness, reductions.

6. State space

7. Midterm test.

8. Simulated annealing: deployment and evaluation I

9. Homework consultation when required.

10. Simulated annealing: deployment and evaluation II

11. Simulated evolution: deployment and evaluation I

12. Simulated evolution: deployment and evaluation I

13. Backup test term, evaluation.

Study Objective:

The students will gain the knowledge and understanding necessary to judge combinatorial problems by their complexity and deployment target (on-line, multicriterial, etc.).

They will be able not only to select and implement but also to apply and evaluate heuristics for practical problems.

Study materials:

1. Arora, S. : Computational Complexity: A Modern Approach. Cambridge University Press, 2017. ISBN 978-1316612156.

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:

The course is presented in Czech.

Further information:

https://courses.fit.cvut.cz/ANI-KOP/

No time-table has been prepared for this course

The course is a part of the following study plans:

• Mgr. programe Applied informatics (code ANIE) for the phase of study without specialization (compulsory course in the program)
• Master specialization Business Informatics, 2026 (compulsory course in the program)