B4M35KO+BE4M35KO -- Combinatorial Optimization

Lab teachers: Anna Minaeva, Theodor Krocan, Ondřej Benedikt, Antonín Novák and Marek Vlk

Course overview

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.

Exam results

Prerequisities

Optimization, Discrete Mathematics, Logics and Graph Theory.

Lectures

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.	Title	Notes	Handouts
1	Introduction of Basic Terms, Example Applications	Test 0	https://rtime.felk.cvut.cz/~hanzalek/KO/Basic_e.pdf
2	Integer Linear Programming - Algorithms		https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf
3	Integer Linear Programming - Problem Formulations		https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf
4	Shortest Paths		https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf
5	Problem Formulation by Shortest Paths		https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf
6	Flows and Cuts - Algorithms and Problem Formulation	Test I.	https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf
7	Bipartite Matching. Multi-commodity Network Flows		https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf
8	Knapsack Problem, Pseudo-polynomial and Approximation Algorithms		https://rtime.felk.cvut.cz/~hanzalek/KO/knapsack_e.pdf
9	Traveling Salesman Problem and Approximation Algorithms		https://rtime.felk.cvut.cz/~hanzalek/KO/TSP_e.pdf
10	Mono-processor Scheduling		https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf
11	Scheduling on Parallel Processors	Test II.	https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf
12	Project Scheduling with Time Windows		https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf
13	class is cancelled
14	Constraint Programming		https://rtime.felk.cvut.cz/~hanzalek/KO/cp_e.pdf

Grading

To get an ungraded assessment the following requirements have to be met:

obtain at least 30 from 50 points:
- 8 points for Test I. (written at lecture)
- 8 points for Test II. (written at lecture)
- 8 points for practical test (written at lab)
- 11 points for semester project
- 15 points for homework assignments No. 1 to 5 (3 points per assignment)
successfully solve all homework assignments

To pass the exam it is necessary to get at least 20 points (maximum 40 points) from the written exam. The oral exam is mandatory and gives 10 points at maximum.

Final grading scale:

Points	[0,50)	[50,60)	[60,70)	[70,80)	[80,90)	[90,100]
Grade	F	E	D	C	B	A

Assessment recognition

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 opt-in 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

Tests I, II, practical test and the homeworks have to be repeated.
Students may transfer points from the semester project. If the grading table of the course changes between the years, the points are scaled accordingly. It is also possible to work on the same topic to increase/decrease the number of received points.
The minimum number of points required to get an ungraded assessment is always taken from the current year grading table.

Table of Contents