Combinatorial Optimization

Přednášející:

Zdeněk Hanzálek (gar.)

Cvičící:

Zdeněk Hanzálek (gar.), Zdeněk Bäumelt

Předmět zajišťuje:

katedra řídicí techniky

Anotace:

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.

Požadavky:

Optimisation, Discrete mathematics, Logics and graphs

Osnova přednášek:

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

2. Integer Linear Programming - Algorithms

3. Problem Formulation by Integer Linear Programming

4. Heuristics, Test

5. Shortest Paths

6. Network Flows and Cuts

7. Multicommodity network flows

8. Dynamic Programming, Test

9. Knapsack Problem and Pseudo-polynomial Algorithms

10. Traveling Salesman Problem and Approximation Algorithms

11. Monoprocessor Scheduling

12. Scheduling on Parallel Processors

13. Project Scheduling with Time Windows

14. Constraint Programming

Osnova cvičení:

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

Cíle studia:

Studijní materiály:

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/

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+6c

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 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
Po
Út	místnost T2:C3-340 Hanzálek Z. 10:00–12:30 (přednášková par. 1) Dejvice Posluchárna
St	místnost KN:E-2 14:30–16:00 (přednášková par. 1 paralelka 101) Karlovo nám. Laboratoř PC
Čt
Pá

Předmět je součástí následujících studijních plánů:

• Open Informatics - Artificial Intelligence (povinný předmět programu)
• Open Informatics - Computer Engineering (povinný předmět programu)
• Open Informatics - Computer Vision and Image Processing (povinný předmět programu)
• Open Informatics - Computer Graphics and Interaction (povinný předmět programu)
• Open Informatics - Software Engineering (povinný předmět programu)