Combinatorial Optimization
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| A4M35KO | Z,ZK | 6 | 3+2c | Czech |
- Enrollement in the course requires an successful completion of the following courses:
- Advanced algorithms (A4M33PAL)
- Lecturer:
- Zdeněk Hanzálek (gar.)
- Tutor:
- Zdeněk Hanzálek (gar.), Zdeněk Bäumelt, Ondřej Nývlt, Demlová Uznáno, Roman Václavík
- 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 transport, flight transport, logistics, planning of human resources, scheduling in production lines, message routing, scheduling in parallel computers.
- Requirements:
-
Optimisation, Discrete mathematics, Logics and graphs
Web page: https://moodle.dce.fel.cvut.cz/
- Syllabus of lectures:
-
1. Introduction of Basic Terms of Combinatorial Optimization, Example Applications.
2. Integer Linear Programming - Algorithms.
3. Problem Formulation by Integer Linear Programming.
4. Shortest Paths. Test I.
5. Network Flows and Cuts - Problem Formulation and Algorithms. Bipartite Matching.
6. Multicommodity Network Flows.
7. Knapsack Problem, Pseudo-polynomial and Approximation Algorithms.
8. Traveling Salesman Problem and Approximation Algorithms. Test II.
9. Monoprocessor Scheduling.
10. Scheduling on Parallel Processors.
11. Project Scheduling with Time Windows.
12. Constraint Programming.
13. Reserve.
- Syllabus of tutorials:
-
1. Introduction to the Experimental Environment and Optimization library
2. Integer Linear Programming
3. Applications of Integer Linear Programming
4. Individual Project I - Assignment and Problem Classification
5. Shortest Paths
6. Individual Project II - Related Work and Solution
7. Applications of Network Flows and Cuts
8. Individual Project III - Consultation
9. Scheduling
10. Test III
11. Individual Project IV - hand in of code and written report
12. Credits
13. Reserve
- Study Objective:
- Study materials:
-
B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.
Springer, third ed., 2006.
J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,
second ed., 2001.
J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.
- Note:
- Time-table for winter semester 2011/2012:
- Time-table is not available yet
- Time-table for summer semester 2011/2012:
-
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 Fri Thu Fri - The course is a part of the following study plans:
-
- Otevřená informatika - Umělá inteligence (compulsory course in the program)
- Otevřená informatika - Počítačové inženýrství (compulsory course in the program)
- Otevřená informatika - Počítačové vidění a digitální obraz (compulsory course in the program)
- Otevřená informatika - Počítačová grafika a interakce (compulsory course in the program)
- Otevřená informatika - Softwarové inženýrství (compulsory course in the program)