Skip to main content
Skip header

Combinatorial Optimization

* Exchange students do not have to consider this information when selecting suitable courses for an exchange stay.

Course Unit Code460-4091/01
Number of ECTS Credits Allocated4 ECTS credits
Type of Course Unit *Choice-compulsory
Level of Course Unit *Second Cycle
Year of Study *First Year
Semester when the Course Unit is deliveredSummer Semester
Mode of DeliveryFace-to-face
Language of InstructionCzech
Prerequisites and Co-Requisites Course succeeds to compulsory courses of previous semester
Name of Lecturer(s)Personal IDName
SAW75doc. Ing. Zdeněk Sawa, Ph.D.
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.
Learning Outcomes of the Course Unit
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
Course Contents
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.
Recommended or Required Reading
Required Reading:
Jon Lee: A first course in combinatorial optimization, Cambridge
University Press, 2004
- Jon Lee: A first course in combinatorial optimization, Cambridge
University Press, 2004
Recommended Reading:
- 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.

- 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.

Planned learning activities and teaching methods
Lectures, Tutorials
Assesment methods and criteria
Task TitleTask TypeMaximum Number of Points
(Act. for Subtasks)
Minimum Number of Points for Task Passing
Credit and ExaminationCredit and Examination100 (100)51
        CreditCredit45 20
        ExaminationExamination55 6