Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2019/2020

Combinatorial Optimization

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
B4M35KO Z,ZK 6 3P+2C Czech
The course cannot be taken simultaneously with:
Combinatorial Optimization (BE4M35KO)
The course is a substitute for:
Combinatorial Optimization (BE4M35KO)
Lecturer:
Zdeněk Hanzálek (guarantor)
Tutor:
Zdeněk Hanzálek (guarantor), Ondřej Benedikt, Anna Minaeva, István Módos, Antonín Novák, Marek Vlk
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 transportation, flight transportation, logistics, planning of human resources, scheduling in production lines, message routing, scheduling in parallel computers.

Requirements:

Optimisation, Discrete mathematics, Logics and graphs

Syllabus of lectures:

1. Introduction to Basic Terms of Combinatorial Optimization, Example Applications and a Test of Preliminary Knowledge

2. Integer Linear Programming - Algorithms

3. Problem Formulation by Integer Linear Programming

4. The Shortest Paths. Problem Formulation by Shortest Paths.

5. Problem Formulation by Shortest Paths.

6. Flows and Cuts - Algorithms and Problem Formulation. Test I.

7. Multicommodity network flows

8. Knapsack Problem and Pseudo-polynomial Algorithms

9. Traveling Salesman Problem and Approximation Algorithms

10. Monoprocessor Scheduling

11. Scheduling on Parallel Processors. Test II.

12. Project Scheduling with Time Windows.

13. Constraint Programming.

14. Reserved

Syllabus of tutorials:

1. Policy and Individual Project Market

2. Introduction to the Experimental Environment and Optimization Library

3. Integer Linear Programming

4. Individual Project I - Assignment and Problem Classification

5. Modeling Languages for Solving Combinatorial Problems

6. Individual Project II - Related Work and Solution

7. Applications of Network Flows and Cuts

8. Individual Project III - Consultation

9. Test III

10. Scheduling

11. Advanced Methods for Solving Combinatorial Problems

12. Individual Project IV - hand in a code and a written report

13. Ungraded Assessment

14. Reserved

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.

TORSCHE http://rtime.felk.cvut.cz/scheduling-toolbox/

Note:
Further information:
https://cw.fel.cvut.cz/wiki/courses/a4m35ko/start
Time-table for winter semester 2019/2020:
Time-table is not available yet
Time-table for summer semester 2019/2020:
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
roomT2:D3-309
Hanzálek Z.
11:45–14:15
(lecture parallel1)
Dejvice
Posluchárna
roomT2:H1-131
Benedikt O.
14:30–16:00
(lecture parallel1
parallel nr.101)

Dejvice haly
AlgDejvice
roomT2:H1-131
Benedikt O.
16:15–17:45
(lecture parallel1
parallel nr.103)

Dejvice haly
AlgDejvice
roomT2:H1-131
Hanzálek Z.
18:00–19:30
(lecture parallel1
parallel nr.104)

Dejvice haly
AlgDejvice
roomT2:H1-130
Novák A.
14:30–16:00
(lecture parallel1
parallel nr.102)

Dejvice haly
AlgDejvice - Veřejná
Fri
Thu
roomT2:H1-131
Novák A.
12:45–14:15
(lecture parallel1
parallel nr.105)

Dejvice haly
AlgDejvice
roomT2:H1-131
Vlk M.
14:30–16:00
(lecture parallel1
parallel nr.106)

Dejvice haly
AlgDejvice
roomT2:H1-131
Vlk M.
16:15–17:45
(lecture parallel1
parallel nr.107)

Dejvice haly
AlgDejvice
roomT2:H1-131
Hanzálek Z.
18:00–19:30
(lecture parallel1
parallel nr.108)

Dejvice haly
AlgDejvice
Fri
The course is a part of the following study plans:
Data valid to 2020-06-05
For updated information see http://bilakniha.cvut.cz/en/predmet4670806.html