CourseWare Wiki
Switch Term
Summer 2023 / 2024
Summer 2022 / 2023
Summer 2021 / 2022
Summer 2020 / 2021
Summer 2019 / 2020
Summer 2018 / 2019
Summer 2017 / 2018
Search
Log In
b232
courses
ko
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Both sides previous revision
Previous revision
2024/06/26 17:27 medjaku1 [Exam results]
2024/06/18 16:08 medjaku1 [Exam results]
2024/06/05 19:27 heinzvil [Exam results]
2024/06/05 19:26 heinzvil [Exam results]
2024/05/28 17:15 heinzvil [Course overview]
2024/05/16 12:31 grusjose [Grading]
2024/04/22 12:22 heinzvil [Grading]
2024/04/22 12:09 heinzvil [Prerequisities]
2024/03/28 15:04 novakan9
2024/03/28 15:04 novakan9 [Course overview]
2024/03/27 17:02 heinzvil [Course overview]
2024/03/27 16:58 heinzvil [Course overview]
2024/03/27 16:58 heinzvil [Course overview]
2024/01/15 11:41 medjaku1 [Grading]
2024/01/15 11:40 medjaku1 [Grading]
2024/01/15 09:35 medjaku1 [Grading]
2024/01/15 09:34 medjaku1 [Grading]
2024/01/15 09:08 medjaku1 [Lectures]
2024/01/15 09:07 medjaku1 [Lectures]
2024/01/15 09:04 medjaku1 [Lectures]
2024/01/15 08:59 medjaku1 [Course overview]
2024/01/15 08:55 medjaku1 [Combinatorial Optimization (B4M35KO+BE4M35KO)]
2024/01/12 13:09 external edit
Go
Previous revision
2024/06/26 17:27 medjaku1 [Exam results]
2024/06/18 16:08 medjaku1 [Exam results]
2024/06/05 19:27 heinzvil [Exam results]
2024/06/05 19:26 heinzvil [Exam results]
2024/05/28 17:15 heinzvil [Course overview]
2024/05/16 12:31 grusjose [Grading]
2024/04/22 12:22 heinzvil [Grading]
2024/04/22 12:09 heinzvil [Prerequisities]
2024/03/28 15:04 novakan9
2024/03/28 15:04 novakan9 [Course overview]
2024/03/27 17:02 heinzvil [Course overview]
2024/03/27 16:58 heinzvil [Course overview]
2024/03/27 16:58 heinzvil [Course overview]
2024/01/15 11:41 medjaku1 [Grading]
2024/01/15 11:40 medjaku1 [Grading]
2024/01/15 09:35 medjaku1 [Grading]
2024/01/15 09:34 medjaku1 [Grading]
2024/01/15 09:08 medjaku1 [Lectures]
2024/01/15 09:07 medjaku1 [Lectures]
2024/01/15 09:04 medjaku1 [Lectures]
2024/01/15 08:59 medjaku1 [Course overview]
2024/01/15 08:55 medjaku1 [Combinatorial Optimization (B4M35KO+BE4M35KO)]
2024/01/12 13:09 external edit
Go
Next revision
Both sides next revision
courses:ko:start [2019/06/12 15:38]
courses:ko:start [2024/01/15 11:40]
medjaku1
[Grading]
Line 1:
Line 1:
+
====== Combinatorial Optimization (B4M35KO+BE4M35KO) ======
+
Lecturer: [[https://rtime.felk.cvut.cz/~hanzalek/| Zdeněk Hanzálek]]
+
+
Lab teachers:
+
[[https://usermap.cvut.cz/profile/1452ea3d-1e57-4422-bb02-72495b4a6b75| Vilém Heinz]],
+
[[https://usermap.cvut.cz/profile/6c4e58dd-4326-4d10-81da-efaadcb1f0cf| Josef Grus]],
+
[[https://usermap.cvut.cz/profile/437b3c93-6930-4517-b100-f4a0e81d6bcb| Jakub Med]] and
+
[[https://upload.wikimedia.org/wikipedia/commons/e/e3/Wild_Turkey.jpg| Theodor Krocan]]
+
+
[[https://cw.felk.cvut.cz/brute/|Brute]]
+
+
+
+
+
===== Course overview =====
+
{{:courses:ko:ko.png?300 |}}
+
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 | 19.2.-25.2. | Introduction of Basic Terms, Example Applications | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/Basic_e.pdf]] | [[https://youtu.be/G1mKKyGpp_k|Intro]] |
+
| 2 | 26.2.-3.3. | Integer Linear Programming - Algorithms | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf]] | [[https://youtu.be/hX9KE0DJJD4|ILP-I]] |
+
| 3 | 4.3.-10.3. | Integer Linear Programming - Problem Formulations | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf]] | [[https://youtu.be/90hs0gTgdHI|ILP-II]] |
+
| 4 | 11.3-17.3. | Shortest Paths | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf]] | [[https://youtu.be/90hs0gTgdHI?t=4516|SP-I]] \\ [[https://youtu.be/LCTwYILbmEY?t=44 | SP-II ]] \\ [[https://youtu.be/eFLIzXDeJ6U?t=33 | SP-III ]] |
+
| 5 | 18.3.-24.3. | Problem Formulation by Shortest Paths | **Theory test 1** | [[https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf]] | |
+
| 6 | 25.3.-31.3. | Flows and Cuts - Algorithms and Problem Formulation | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf]] | [[https://youtu.be/eFLIzXDeJ6U?t=5687 | Flows-I]] \\ [[https://youtu.be/xK3xiyEfG-k | Flows-II]] \\ [[https://youtu.be/71B1FMVVX_o?t=34 | Flows-III]]|
+
| 7 | 1.4.-7.4. | Bipartite Matching. Multi-commodity Network Flows | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf]] | |
+
| 8 | 8.4.-14.4. | Knapsack Problem, Pseudo-polynomial and Approximation Algorithms | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/knapsack_e.pdf]] | [[https://youtu.be/71B1FMVVX_o?t=3422 | Knapsack-I ]] |
+
| 9 | 15.4.-21.4. | Traveling Salesman Problem and Approximation Algorithms | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/TSP_e.pdf]] | [[https://youtu.be/p9qiafTnd6Q?t=25 | TSP-I]] |
+
| 10 | 22.4.-28.4. | Mono-processor Scheduling | **Theory test 2** | [[https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf]] |[[https://youtu.be/p9qiafTnd6Q?t=6439 | Sched-I]] \\ [[https://youtu.be/idc516WZZ1I?t=41 | Sched-II ]] \\ [[https://youtu.be/MjekjcErKPc?t=21|Sched-III]] \\ [[https://youtu.be/dhe54BPDNwo?t=67|Sched-IV]] |
+
| 11 | 29.4.- 5.5. | Scheduling on Parallel Processors | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf]] | |
+
| 12 | 6.5.-12.5. | Project Scheduling with Time Windows | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf]] | |
+
| 13 | 13.5.-19.5. | **No class on Tuesday** | | | |
+
| 14 | 20.5.-26.5. | Constraint Programming | | [[https://rtime.felk.cvut.cz/~hanzalek/KO/cp_e.pdf]] | [[https://youtu.be/SPsN60AC2jE| CP-I]] |
+
+
+
**Materials by topic**
+
+
^Title ^ Handouts ^ Stream^
+
|**Introduction** |[[https://rtime.felk.cvut.cz/~hanzalek/KO/Basic_e.pdf]]| [[https://youtu.be/G1mKKyGpp_k|Intro]] |
+
|**Integer Linear Programming** |[[https://rtime.felk.cvut.cz/~hanzalek/KO/ILP_e.pdf]]| [[https://youtu.be/hX9KE0DJJD4|ILP-I]] \\ [[https://youtu.be/90hs0gTgdHI|ILP-II]] |
+
| **Shortest paths** |[[https://rtime.felk.cvut.cz/~hanzalek/KO/SPT_e.pdf]]| [[https://youtu.be/90hs0gTgdHI?t=4516|SP-I]] \\ [[https://youtu.be/LCTwYILbmEY?t=44 | SP-II ]] \\ [[https://youtu.be/eFLIzXDeJ6U?t=33 | SP-III ]] |
+
| **Network flows** |[[https://rtime.felk.cvut.cz/~hanzalek/KO/Flows_e.pdf]]| [[https://youtu.be/eFLIzXDeJ6U?t=5687 | Flows-I]] \\ [[https://youtu.be/xK3xiyEfG-k | Flows-II]] \\ [[https://youtu.be/71B1FMVVX_o?t=34 | Flows-III]]|
+
|**Knapsack** |[[https://rtime.felk.cvut.cz/~hanzalek/KO/knapsack_e.pdf]]| [[https://youtu.be/71B1FMVVX_o?t=3422 | Knapsack-I ]]|
+
|**Traveling Salesman Problem** |[[https://rtime.felk.cvut.cz/~hanzalek/KO/TSP_e.pdf]]| [[https://youtu.be/p9qiafTnd6Q?t=25 | TSP-I]] |
+
|**Scheduling** |[[https://rtime.felk.cvut.cz/~hanzalek/KO/sched_e.pdf]]| [[https://youtu.be/p9qiafTnd6Q?t=6439 | Sched-I]] \\ [[https://youtu.be/idc516WZZ1I?t=41 | Sched-II ]] \\ [[https://youtu.be/MjekjcErKPc?t=21|Sched-III]] \\ [[https://youtu.be/dhe54BPDNwo?t=67|Sched-IV]] |
+
| **Constraint Programming** |[[https://rtime.felk.cvut.cz/~hanzalek/KO/cp_e.pdf]] | [[https://youtu.be/SPsN60AC2jE| CP-I]] |
+
+
+
+
===== 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 (4 assignments) | 15 | ::: |
+
| ::: | Theoretical tests (two tests, 8 points each)| 16 | ::: |
+
| ::: | Practical test | 8 | ::: |
+
| ::: | Semester project | 11 | **Minimum points** |
+
| ::: | **Total semester** <sup>1)</sup> | 50 | 30 |
+
| **Final exam** <sup>2)</sup> | Written part | 40 | 20 |
+
| ::: | Oral exam | 10 | 0 |
+
| **Total** || 100 | 50 |
+
+
<sup>1)</sup> 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 **25. 5. 2024 (Thursday) 23:59**. If you fail to fulfill the requirements by then, you will also fail the entire class.
+
+
<sup>2)</sup> Only the students, who obtained the ungraded assessment are allowed to take the exam.
+
The exam constitutes of the written part (40 points) and oral exam (10 points).
+
To pass the written exam, it is necessary to get at least 20 points.
+
The oral exam is **mandatory**.
+
+
**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
+
- Theoretical tests, 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.
courses/ko/start.txt
· Last modified: 2024/06/26 17:27 by
medjaku1