Combinatorial Optimization

Relations:

During a review of study plans, the course BE4M35KO can be substituted for the course B4M35KO.

It is not possible to register for the course B4M35KO if the student is concurrently registered for or has already completed the course BE4M35KO (mutually exclusive courses).

The requirement for course B4M35KO can be fulfilled by substitution with the course BE4M35KO.

Course guarantor:

Zdeněk Hanzálek

Lecturer:

Zdeněk Hanzálek, Antonín Novák

Tutor:

David Simon Fischer, Zdeněk Hanzálek, Viktor Emil Korladinov, Sylvain Lichau, Antonín Novák, Jan Pikman

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

14. Reserved

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

10. Scheduling

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/978-3-662-56039-6

J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,

second ed., 2001.

J. Demel, Grafy a jejich aplikace. Academia, second ed., 2015.

https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf

Note:

Further information:

https://cw.fel.cvut.cz/wiki/courses/ko/start

Time-table for winter semester 2026/2027:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue	roomKN:A-447 16:15–17:45 (lecture parallel1 parallel nr.106) Karlovo nám. roomKN:A-447 18:00–19:30 (lecture parallel1 parallel nr.107) Karlovo nám.
Wed	roomKN:A-447 Pikman J. 09:15–10:45 (lecture parallel1 parallel nr.108) Karlovo nám.
Thu	roomKN:A-447 Korladinov V. 09:15–10:45 (lecture parallel1 parallel nr.101) Karlovo nám. roomKN:A-447 Korladinov V. 11:00–12:30 (lecture parallel1 parallel nr.102) Karlovo nám. roomKN:A-447 Korladinov V. 12:45–14:15 (lecture parallel1 parallel nr.103) Karlovo nám. roomKN:A-447 Lichau S. Fischer D. 14:30–16:00 (lecture parallel1 parallel nr.104) Karlovo nám. roomKN:A-447 Lichau S. Fischer D. 16:15–17:45 (lecture parallel1 parallel nr.105) Karlovo nám. roomKN:A-447 Lichau S. Fischer D. 18:00–19:30 (lecture parallel1 parallel nr.109) Karlovo nám.
Fri

Time-table for summer semester 2026/2027:

Time-table is not available yet

The course is a part of the following study plans:

• Medical electronics and bioinformatics (PS)
• Open Informatics - Human-Computer Interaction 2018 (compulsory course in the program)
• Open Informatics - Cyber Security 2018 (compulsory course in the program)
• Open Informatics - Computer Graphics 2018 (compulsory course in the program)
• Open Informatics - Computer Engineering 2018 (compulsory course in the program)
• Open Informatics - Computer Vision and Image Processing 2018 (compulsory course in the program)
• Open Informatics - Software Engineering 2018 (compulsory course in the program)
• Open Informatics - Artificial Intelligence 2018 (compulsory course in the program)
• Open Informatics - Bioinformatics 2018 (compulsory course in the program)
• Open Informatics - Data Science 2018 (compulsory course in the program)
• Medical electronics and bioinformatics (compulsory elective course)
• Medical electronics and bioinformatics (PS)
• Medical electronics and bioinformatics (compulsory elective course)
• Open Informatics - Artificial Intelligence 2026 (compulsory course in the program)
• Open Informatics - Autonomous Systems 2026 (compulsory course in the program)
• Open Informatics - Computer Engineering 2026 (compulsory course in the program)
• Open Informatics - Computer Graphics 2026 (compulsory course in the program)
• Open Informatics - Computer Vision 2026 (compulsory course in the program)
• Open Informatics - Cyber Security 2026 (compulsory course in the program)
• Open Informatics - Data Science 2026 (compulsory course in the program)
• Open Informatics - Extended Reality and Game Development 2026 (compulsory course in the program)
• Open Informatics - Software Engineering 2026 (compulsory course in the program)