Lecturer: Zdeněk Hanzálek
Lab teachers: Ondřej Benedikt, Vilém Heinz Antonín Novák and Theodor Krocan
Due to the current situation and the closure of the faculty, the teaching/learning is ongoing in a distance form.
This course is focusing on the problems and algorithms of combinatorial optimization (often called discrete optimization). 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, e.g. logistics, transportation, planning of human resources, scheduling in production lines, message routing and scheduling in parallel computers.
Optimization, Discrete Mathematics, Logics and Graph Theory.
This timetable is for the czech version (B4M35KO) of the course. The timetable of the english version (BE4M35KO) is provided by prof. Hanzálek.
Week No.  Dates  Title  Notes  Handouts  Stream 

1  15.2.21.2.  Introduction of Basic Terms, Example Applications  https://rtime.felk.cvut.cz/~hanzalek/KO/Basic_e.pdf  Intro  
2  22.2.28.2.  Integer Linear Programming  Algorithms  https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf  ILPI  
3  1.3.7.3.  Integer Linear Programming  Problem Formulations  https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf  ILPII  
4  8.3.14.3.  Shortest Paths  https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf  SPI SPII SPIII 

5  15.3.21.3.  Problem Formulation by Shortest Paths  Test 1  https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf  
6  22.3.28.3.  Flows and Cuts  Algorithms and Problem Formulation  https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf  FlowsI FlowsII FlowsIII 

7  29.3.4.4.  Bipartite Matching. Multicommodity Network Flows  https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf  
8  5.4.11.4.  Knapsack Problem, Pseudopolynomial and Approximation Algorithms  https://rtime.felk.cvut.cz/~hanzalek/KO/knapsack_e.pdf  KnapsackI  
9  12.4.18.4.  Traveling Salesman Problem and Approximation Algorithms  Test 2  https://rtime.felk.cvut.cz/~hanzalek/KO/TSP_e.pdf  TSPI 
10  19.4.25.4.  Monoprocessor Scheduling  Practical test  https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf  SchedI SchedII SchedIII SchedIV 
11  26.4.2.5.  Scheduling on Parallel Processors  https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf  
12  3.5.9.5.  Project Scheduling with Time Windows  https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf  
13  10.5.16.5.  Constraint Programming  https://rtime.felk.cvut.cz/~hanzalek/KO/cp_e.pdf  CPI  
14  17.5.23.5.  Reserve 
Materials by topic
Title  Handouts  Stream 

Introduction  https://rtime.felk.cvut.cz/~hanzalek/KO/Basic_e.pdf  Intro 
Integer Linear Programming  https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf  ILPI ILPII 
Shortest paths  https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf  SPI SPII SPIII 
Network flows  https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf  FlowsI FlowsII FlowsIII 
Knapsack  https://rtime.felk.cvut.cz/~hanzalek/KO/knapsack_e.pdf  KnapsackI 
Traveling Salesman Problem  https://rtime.felk.cvut.cz/~hanzalek/KO/TSP_e.pdf  TSPI 
Scheduling  https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf  SchedI SchedII SchedIII SchedIV 
Constraint Programming  https://rtime.felk.cvut.cz/~hanzalek/KO/cp_e.pdf  CPI 
Students may receive a total of 100 points. The final exam is worth 50% of the grade, while the other 50% can be obtained during the semester.
The points are distributed according to the following table.
Category  Maximum points  
Semester  Homeworks (5 assignments, 2 points each)  10  
Theoretical tests (two tests, 7 points each)  14  
Practical test  10  
Semester project  16  Minimum points  
Total semester ^{1)}  50  25  
Final exam ^{2)}  Written part  50  25 
Total  100  50 
^{1)} To get an ungraded assessment the following requirements have to be met:
The last date of awarding the ungraded assessments is 23. 5. 2021. If you will fail to fulfill the requirements by then, you will also fail the entire class.
^{2)} Only the students, who obtained the ungraded assessment are allowed to take the exam. The exam constitutes of the written part (50 points). To pass the written exam, it is necessary to get at least 25 points.
Final grading scale:
Points  [0,50)  [50,60)  [60,70)  [70,80)  [80,90)  [90,100] 

Grade  F  E  D  C  B  A 
The following applies only to students who got an ungraded assessment in the previous year (all other students have to undergo the course from scratch).
Although the assessments are not fully recognized, the students may optin to transfer some points from the previous year to the current one (they may also undergo the course from scratch to get a higher number of points). The following rules apply