- The course is a substitute for:
- Combinatorial Optimization (B4M35KO)
- Zdeněk Hanzálek
- Ondřej Benedikt, Anna Minaeva, István Módos, Antonín Novák, Marek Vlk
- Department of Control Engineering
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.
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. Integer Linear Programming - Algorithms
3. Problem Formulation by Integer Linear Programming
4. The Shortest Paths. Problem Formulation by Shortest Paths.
5. Problem Formulation by Shortest Paths.
6. Flows and Cuts - Algorithms and Problem Formulation. Test I.
7. Multicommodity network flows
8. Knapsack Problem and Pseudo-polynomial Algorithms
9. Traveling Salesman Problem and Approximation Algorithms
10. Monoprocessor Scheduling
11. Scheduling on Parallel Processors. Test II.
12. Project Scheduling with Time Windows.
13. Constraint Programming.
- Syllabus of tutorials:
1. Policy and Individual Project Market
2. Introduction to the Experimental Environment and Optimization Library
3. Integer Linear Programming
4. Individual Project I - Assignment and Problem Classification
5. Traveling Salesman Problem
6. Individual Project II - Related Work and Solution
7. Applications of Network Flows and Cuts
8. Individual Project III - Consultation
9. Test III
11. Advanced Methods for Solving Combinatorial Problems
12. Individual Project IV - evaluation and written report
13. Ungraded Assessment
- Study Objective:
- Study materials:
B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.
Springer, sixth ed., 2018.
J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,
second ed., 2001.
J. Demel, Grafy a jejich aplikace. Academia, second ed., 2015.
- Further information:
- Time-table for winter semester 2022/2023:
- Time-table is not available yet
- Time-table for summer semester 2022/2023:
Mon Tue Wed ThuroomT2:H1-131
- The course is a part of the following study plans:
- Open Informatics - Artificial Intelligence (compulsory course in the program)
- Open Informatics - Computer Vision and Image Processing (compulsory course in the program)
- Open Informatics - Software Engineering (compulsory course in the program)
- Open Informatics - Human-Computer Interaction (compulsory course in the program)
- Open Informatics - Cyber Security (compulsory course in the program)
- Open Informatics - Computer Graphics (compulsory course in the program)
- Open Informatics - Computer Engineering (compulsory course in the program)
- Open Informatics - Bioinformatics (compulsory course in the program)
- Open Informatics - Data Science (compulsory course in the program)
- Medical Electronics and Bioinformatics - Specialization Image Processing (PS)
- Medical Electronics and Bioinformatics - Specialization Signal Processing (compulsory elective course)
- Medical Electronics and Bioinformatics - Specialization Bioinformatics (PS)
- Medical Electronics and Bioinformatics - Specialization Medical Instrumentation (compulsory elective course)