Course Unit Code | 460-4091/01 |
---|
Number of ECTS Credits Allocated | 4 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 delivered | Summer Semester |
---|
Mode of Delivery | Face-to-face |
---|
Language of Instruction | Czech |
---|
Prerequisites and Co-Requisites | Course succeeds to compulsory courses of previous semester |
---|
Name of Lecturer(s) | Personal ID | Name |
---|
| SAW75 | doc. 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 Title | Task Type | Maximum Number of Points (Act. for Subtasks) | Minimum Number of Points for Task Passing |
---|
Credit and Examination | Credit and Examination | 100 (100) | 51 |
Credit | Credit | 45 | 20 |
Examination | Examination | 55 | 6 |