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