Combinatorial Algorithms
Code  Completion  Credits  Range  Language 

RM35KOA  Z,ZK  6  2P+2C  Czech 
 Garant předmětu:
 Lecturer:
 Tutor:
 Supervisor:
 Department of Control Engineering
 Synopsis:

The goal is to show the problems and algorithms of combinatorial optimization (often called discrete optimization; there is a strong overlap with the term operations research).
Following the courses on linear algebra, graph theory, and basics of optimization, we show optimization techniques based on graphs, integer linear programming, heuristics, approximation algorithms and state space search methods.
We focus on application of optimization in stores, ground transportation, flight transportation, logistics, planning of human resources, scheduling in production lines, message routing, scheduling in parallel computers.
 Requirements:

Optimisation, Discrete mathematics, Logics and graphs
 Syllabus of lectures:

1. Introduction to Basic Terms of Combinatorial Optimization, Example Applications, and a Test of Preliminary Knowledge
2. Complexity of combinatorial problems
3. Integer Linear Programming  Algorithms
4. Problem Formulation by Integer Linear Programming
5. The Shortest Paths. Problem Formulation by Shortest Paths.
6. Problem Formulation by Shortest Paths. Test I.
7. Flows and Cuts  Algorithms.
8. Flows and Cuts  Problem Formulation.
9. Multicommodity network flows.
10. Knapsack Problem and Pseudopolynomial Algorithms.
11. Traveling Salesman Problem and Approximation Algorithms.
12. Monoprocessor Scheduling.
13. Scheduling on Parallel Processors.
14. Reserved
 Syllabus of tutorials:

1. Introduction to the Experimental Environment and Optimization Library
2. SAT and nteger Linear Programming
3. Integer Linear Programming
4. Integer Linear Programming
5. Individual Project I  Assignment and Problem Classification
6. Traveling Salesman Problem
7. Individual Project II  Related Work and Solution
8. Applications of Network Flows and Cuts
9. Individual Project III  Consultation
10. Scheduling. Test II
11. Advanced Methods for Solving Combinatorial Problems
12. Individual Project IV  evaluation and written report
13. Ungraded Assessment
14. Reserved
 Study Objective:
 Study materials:

B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.
Springer, sixth ed., 2018.
http://dx.doi.org/10.1007/9783662560396
J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,
second ed., 2001.
J. Demel, Grafy a jejich aplikace. Academia, second ed., 2015.
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans: