460-4091/01 – Combinatorial Optimization (KO)
| Gurantor department | Department of Computer Science | Credits | 4 |
| Subject guarantor | doc. Ing. Zdeněk Sawa, Ph.D. | Subject version guarantor | doc. Ing. Zdeněk Sawa, Ph.D. |
| Study level | undergraduate or graduate | Requirement | Optional |
| Year | 1 | Semester | summer |
| | Study language | Czech |
| Year of introduction | 2015/2016 | Year of cancellation | 2022/2023 |
| Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
Students after successful completion of this subject:
- understand basic notions from the area of combinatorial optimization
(including the relevant notions from graph theory, linear programming,
computational complexity etc.)
- can classify practical problems that can be suitably modelled as problems of
combinatorial optimization
- are able to construct the respective models to practical problems
- can classify which practical problems are solvable by polynomial algorithms
and which are NP-hard
- have an overview of solution methods for problems of linear programming and
integer linear programming, and they can use the methods
- understand the ideas of basic polynomial algorithms
- have an overview of basic approximation algorithms for NP-hard problems and
of generally applicable heuristic approaches
- can work with software tools for solving combinatorial optimization tasks
Teaching methods
Lectures
Tutorials
Summary
Many problems of everyday (industrial) practice are de facto optimization
problems: in a set of feasible solutions (e.g., assigning tasks to workers or
processors, scheduling of trucks and their routes, design of layout of
electronic components at printed circuit boards) we search for a solution that
is optimal in some respect (like cost, time). These problems can be often
formulated as problems of combinatorial (or discrete) optimization, mostly in
the terms of graphs and (integer) linear inequalities. Some problems can be
satisfactorily solved by quick polynomial algorithms, at others (NP-hard
problems) we have to be satisfied with algorithms that only approximate
optimal solutions, or with other (heuristic) algorithms that give reasonable
outcomes though their quality is not guaranteed generally.
The goal of the course is to explain the area of combinatorial optimization,
the classification of problems that belong here, and the methods used for
their solving in practice.
Compulsory literature:
Jon Lee: A first course in combinatorial optimization, Cambridge
University Press, 2004
Recommended literature:
- Bernhard Korte, Jens Vygen: Combinatorial Optimization (Theory and Algorithms), Springer (5th edition 2012)
- Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization:
Algorithms and Complexity, Dover Publications, 1998.
- Malik Ghallab, Dana Nau, Paolo Traverso: Automated Planning: Theory & Practice, Morgan Kaufmann, 2004.
- Alexander Schrijver: Combinatorial Optimization (3 volume, A,B, & C),
Springer, 2003.
Additional study materials
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
No additional requirements are put on students.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
1. Course overview. General definitions of (discrete) optimization problems.
Examples of typical combinatorial optimization tasks modelled by using the
notions of graph theory. Examples of problems solvable by greedy approaches
(as, e.g., the minimum spanning tree problem). A general proof of correctness
by using notions from matroid theory.
2. Further concrete problems solvable by quick (polynomial) algorithms.
Recalling of problems of shortest paths, maximal network flows, maximal
bipartite matchings; the ideas of respective algorithms. Polynomial
reducibility among problems.
3. NP-hard problems (problems SAT and MAX-SAT, Travelling Salesman Problem
[TSP], scheduling problems, etc.). The idea of Cook's theorem (NP-completeness
of the problem SAT), and proofs of NP-hardness by polynomial reducibility.
4. Integer linear programming (ILP). Formulations of combinatorial
optimization problems as instances of ILP. NP-hardness of ILP.
5. Linear programming (i.e. "relaxed" ILP). Formulations of linear programming
tasks. The duality principle.
6. Solving of linear programming tasks; the simplex method. Discussion of
polynomial complexity of linear programming.
7. Solving of ILP tasks. Totally unimodular matrices. The branch and bound method.
8. Further methods of solving ILP tasks. The method of cutting planes.
9. Pseudopolynomial algorithms and approximation algorithms illustrated on the
knapsack problem. Remarks on heuristic approaches to solving NP-hard problems.
10. Further approximation algorithms and approaches (approximation of TSP, the
simulated annealing method).
11. Problems that are hard to approximate. Probabilistically Checkable Proofs;
PCP-theorem, and its application to the maximum clique problem.
12. and 13. Several variants of planning and scheduling problems, and their
solutions. (Task scheduling for one processor, and for parallel processors.)
14. Summary of the main notions and ideas.
Tutorials:
----------
Exercises will also comprise problem solving by software tools (e.g., for
linear programming tasks). A significant part will be devoted to solving the
problems at the board. The content will correspond to lectures.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction