Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Combinatorial Optimization

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
AE4M77KO Z,ZK 6 3P+2C anglicky
Garant předmětu:
Přednášející:
Cvičící:
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.

Požadavky:
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 Optimisation library

2. Integer Linear Programming

3. Applications of Integer Linear Programming

4. Assignment of Term Projects

5. Branch and Bound Technique

6. Shortest Paths

7. Applications of Network Flows and Cuts

8. Presentation of Term Projects

9. Monoprocessor Scheduling - Earliest Deadline First

10. Approximation Algorithms - List Scheduling

11. Reserved

12. Test

13. Giving over Term Projects

14. Credits

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.

Poznámka:

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

Další informace:
https://cw.fel.cvut.cz/wiki/courses/a4m35ko/start
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 6. 11. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet12825304.html