Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Table of Contents

B4M35KO+BE4M35KO -- Combinatorial Optimization

Lecturer: Zdeněk Hanzálek

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

Brute Forum

Distance Learning

Due to the current situation and the closure of the faculty, the teaching/learning is ongoing in a distance form.

  • The lecture materials are available at CourseWare; the lectures are available on Youtube.
  • The lab assignments are appearing at CourseWare, and supplementary videos are available at our YouTube channel.
  • The instructions for the upcoming week are written in our forum, and are also sent to all students via e-mail.

Exam results

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.

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. Dates Title Notes Handouts Stream
1 17.2.-23.2. Introduction of Basic Terms, Example Applications Test 0 https://rtime.felk.cvut.cz/~hanzalek/KO/Basic_e.pdf
2 24.2.-1.3. Integer Linear Programming - Algorithms https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf
3 2.3.-8.3. Integer Linear Programming - Problem Formulations https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf
4 9.3.-15.3. Shortest Paths https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf
5 16.3.-22.3. Problem Formulation by Shortest Paths https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf
6 23.3.-29.3. Flows and Cuts - Algorithms and Problem Formulation Test I. https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf
7 30.3.-5.4. Bipartite Matching. Multi-commodity Network Flows https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf
8 6.4.-12.4. Knapsack Problem, Pseudo-polynomial and Approximation Algorithms https://rtime.felk.cvut.cz/~hanzalek/KO/knapsack_e.pdf
9 13.4.-19.4. Traveling Salesman Problem and Approximation Algorithms https://rtime.felk.cvut.cz/~hanzalek/KO/TSP_e.pdf
10 20.4.-26.4. Mono-processor Scheduling https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf
11 27.4.-3.5. Scheduling on Parallel Processors Test II. https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf
12 4.5.-10.5. Class is cancelled
13 11.5.-17.5. Project Scheduling with Time Windows https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf
14 18.5.-24.5. Constraint Programming Theory Test https://rtime.felk.cvut.cz/~hanzalek/KO/cp_e.pdf YT stream

Grading

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, 3 points per each) 15
Theoretical test (written online) 16
Practical test (written online) 8
Semester project 11 Minimum points
Total semester 1) 50 30
Final exam 2) Written part 50 20
Total exam 50 20
Total 100 50

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

  • successfully solve all homework assignments (i.e., accepted by BRUTE evaluation as correct)
  • obtain at least 30 from 50 points

The last date of awarding the ungraded assessments is 12. 6. 2020. If you will fail to obtain at least the required minimum of points for the assessment by then, you will fail also 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 20 points.

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

  1. Tests I, II, practical test and the homeworks have to be repeated.
  2. 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.
  3. The minimum number of points required to get an ungraded assessment is always taken from the current year grading table.
courses/ko/start.txt · Last modified: 2020/08/26 16:05 by benedond