Combinatorial Optimization

Vztahy:

Předmět BE4M35KO může při kontrole studijních plánů nahradit předmět B4M35KO

Předmět BE4M35KO může být splněn v zastoupení předmětem B4M35KO

Předmět BE4M35KO nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět B4M35KO (vztah je symetrický)

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.

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.

Požadavky:

Optimisation, Discrete mathematics, Logics and graphs

Osnova přednášek:

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

Osnova cvičení:

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. Traveling Salesman Problem

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 - evaluation and written report

13. Ungraded Assessment

14. Reserved

Cíle studia:

Studijní materiály:

B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.

Springer, sixth ed., 2018.

http://dx.doi.org/10.1007/978-3-662-56039-6

J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,

second ed., 2001.

J. Demel, Grafy a jejich aplikace. Academia, second ed., 2015.

https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf

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ů:

• Open Informatics - Artificial Intelligence (povinný předmět programu)
• Open Informatics - Computer Vision and Image Processing (povinný předmět programu)
• Open Informatics - Software Engineering (povinný předmět programu)
• Open Informatics - Human-Computer Interaction (povinný předmět programu)
• Open Informatics - Cyber Security (povinný předmět programu)
• Open Informatics - Computer Graphics (povinný předmět programu)
• Open Informatics - Computer Engineering (povinný předmět programu)
• Open Informatics - Bioinformatics (povinný předmět programu)
• Open Informatics - Data Science (povinný předmět programu)
• Medical Electronics and Bioinformatics - Specialization Image Processing (PS)
• Medical Electronics and Bioinformatics - Specialization Signal Processing (povinně volitelný předmět)
• Medical Electronics and Bioinformatics - Specialization Bioinformatics (PS)
• Medical Electronics and Bioinformatics - Specialization Medical Instrumentation (povinně volitelný předmět)