# 460-4063/01 – Combinatorial Optimization (KO)

 Gurantor department Department of Computer Science Credits 5 Subject guarantor prof. RNDr. Petr Jančar, CSc. Subject version guarantor prof. RNDr. Petr Jančar, CSc. Study level undergraduate or graduate Requirement Optional Year Semester winter Study language Czech Year of introduction 2014/2015 Year of cancellation 2015/2016 Intended for the faculties FEI Intended for study types Follow-up Master
Instruction secured by
JAN59 prof. RNDr. Petr Jančar, CSc.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Part-time 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

Lectures
Tutorials
Project work

### 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:

• Bernhard Korte, Jens Vygen: Combinatorial Optimization (Theory and Algorithms), Springer (5th edition 2012)

### Recommended literature:

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

### Other requirements

During the semester, each student will elaborate an individual project. (S)he can choose an application-oriented or a theory-oriented project. In the case of an application-oriented project, the student gets a description of a concrete practically motivated task (as, e.g., design of optimal hole drilling at a printed circuit board) for which (s)he creates a model, suggests a suitable way of solving and implements this in a chosen software tool. In the case of a theory-oriented project the task will be, e.g., to prove some nontrivial properties of concrete methods and algorithms solving optimization problems.

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

Part-time form (validity from: 2014/2015 Winter semester, validity until: 2015/2016 Summer semester)
Min. number of pointsMax. počet pokusů
Exercises evaluation and Examination Credit and Examination 100 (100) 51
Exercises evaluation Credit 40  20
Examination Examination 60  25 3
Mandatory attendence participation:

Show history

Conditions for subject completion and attendance at the exercises within ISP:

Show history

### Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2014/2015 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava Optional study plan
2014/2015 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava Optional study plan
2014/2015 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava Optional study plan

### Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

### Assessment of instruction

Předmět neobsahuje žádné hodnocení.