460-4091/01 – Combinatorial Optimization (KO)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantordoc. Ing. Zdeněk Sawa, Ph.D.Subject version guarantordoc. Ing. Zdeněk Sawa, Ph.D.
Study levelundergraduate or graduateRequirementOptional
Year1Semestersummer
Study languageCzech
Year of introduction2015/2016Year of cancellation
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 10+0

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.

Way of continuous check of knowledge in the course of semester

E-learning

Další požadavky na studenta

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

Full-time form (validity from: 2015/2016 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Credit and Examination Credit and Examination 100 (100) 51
        Credit Credit 45  20
        Examination Examination 55  6
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2019/2020 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2019/2020 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2019/2020 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2018/2019 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2018/2019 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2018/2019 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2017/2018 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2017/2018 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2017/2018 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2016/2017 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2016/2017 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2016/2017 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan
2015/2016 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 1 Optional study plan
2015/2016 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 1 Optional study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 1 Choice-compulsory study plan
2015/2016 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 1 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner