Kombinatorická optimalizace

B152 - Letní 15/16
Toto je tzv. shluknutý kurz. Skládá se z několika samostatných předmětů, které sdílejí výukové materiály, úkoly, testy apod. Níže si můžete zobrazit informace o jednotlivých předmětech tvořících tento shluk.

Kombinatorická optimalizace - A4M35KO

Hlavní kurz
Kredity 6
Semestry letní
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 3P+2C
Anotace
Cílem předmětu je seznámit studenty s problémy a algoritmy
kombinatorické optimalizace (často se nazývá diskrétní optimalizace,
významně se překrývá s pojmem operační výzkum). V návaznosti na
předměty z oblasti lineární algebry, algoritmizace, diskrétní
matematiky a základů optimalizace jsou ukázány techniky založené na
grafech, celočíselném lineárním programování, heuristikách,
aproximačních algoritmech a metodách prohledávání prostoru řešení.

Předmět je zaměřen na aplikace optimalizace ve skladech, pozemní a letecké dopravě, logistice, plánování lidských zdrojů, rozvrhování výrobních linek, směrování zpráv, rozvrhování v paralelních počítačích. \\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M35KO
Cíle studia
Žádná data.
Osnovy přednášek
1. Uvedení základních pojmů z kombinatorické optimalizace, příklady aplikací.
2. Celočíselné lineární programování - algoritmy.
3. Formulace problémů pomocí celočíselného lineárního programování.
4. Nejkratší cesty.
5. Formulace problémů pomocí nejkratších cest.
6. Toky a řezy v sítích - formulace problémů a algoritmy. Párování v bipartitních grafech. Test I.
7. Multi-komoditní toky.
8. Problém batohu, pseudo-polynomiální a aproximační algoritmy.
9. Úloha obchodního cestujícího.
10. Rozvrhování na jednom procesoru.
11. Paralelní procesory. Test II.
12. Rozvrhování projektu s časovými omezeními.
13. Programování s omezujícími podmínkami.
14. Rezerva
Osnovy cvičení
1. Seznámení s předmětem a pravidly.
2. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci
3. Celočíselné lineární programování
4. Samostatná úloha I - zadání a kategorizace
5. Modelovácí jazyky pro řešení problémů kombinatorické optimalizace
6. Samostatná úloha II - rešerše literatury a prezentace řešení
7. Aplikace toků a řezů v sítích
8. Samostatná úloha III - konzultace
9. Test III
10. Rozvrhování
11. Pokročilé metody pro řešení problémů kombinatorické optimalizace
12. Samostatná úloha IV - odevzdání algoritmu a písemné zprávy
13. Zápočet
14. Rezerva
Literatura
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/
Požadavky
Optimalizace, Diskrétní matematika, Logika a grafy

Kombinatorická optimalizace - AD4M35KO

Kredity 6
Semestry letní
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 21KP+6KC
Anotace
Cílem předmětu je seznámit studenty s problémy a algoritmy
kombinatorické optimalizace (často se nazývá diskrétní optimalizace,
významně se překrývá s pojmem operační výzkum). V návaznosti na
předměty z oblasti lineární algebry, algoritmizace, diskrétní
matematiky a základů optimalizace jsou ukázány techniky založené na
grafech, celočíselném lineárním programování, heuristikách,
aproximačních algoritmech a metodách prohledávání prostoru řešení.

Předmět je zaměřen na aplikace optimalizace ve skladech, pozemní a letecké dopravě, logistice, plánování lidských zdrojů, rozvrhování výrobních linek, směrování zpráv, rozvrhování v paralelních počítačích. \\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M35KO
Cíle studia
Žádná data.
Osnovy přednášek
1. Uvedení základních pojmů z kombinatorické optimalizace, příklady aplikací.
2. Celočíselné lineární programování - algoritmy.
3. Formulace problémů pomocí celočíselného lineárního programování.
4. Nejkratší cesty.
5. Formulace problémů pomocí nejkratších cest.
6. Toky a řezy v sítích - formulace problémů a algoritmy. Párování v bipartitních grafech. Test I.
7. Multi-komoditní toky.
8. Problém batohu, pseudo-polynomiální a aproximační algoritmy.
9. Úloha obchodního cestujícího.
10. Rozvrhování na jednom procesoru.
11. Paralelní procesory. Test II.
12. Rozvrhování projektu s časovými omezeními.
13. Programování s omezujícími podmínkami.
14. Rezerva
Osnovy cvičení
1. Seznámení s předmětem a pravidly.
2. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci
3. Celočíselné lineární programování
4. Samostatná úloha I - zadání a kategorizace
5. Modelovácí jazyky pro řešení problémů kombinatorické optimalizace
6. Samostatná úloha II - rešerše literatury a prezentace řešení
7. Aplikace toků a řezů v sítích
8. Samostatná úloha III - konzultace
9. Test III
10. Rozvrhování
11. Pokročilé metody pro řešení problémů kombinatorické optimalizace
12. Samostatná úloha IV - odevzdání algoritmu a písemné zprávy
13. Zápočet
14. Rezerva
Literatura
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/
Požadavky
Optimalizace, Diskrétní matematika, Logika a grafy

Combinatorial Optimization - AE4M35KO

Kredity 6
Semestry letní
Zakončení zápočet a zkouška
Jazyk výuky angličtina
Rozsah výuky 3P+2C
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.
\\Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/AE4M35KO
Cíle studia
Žádná data.
Osnovy 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
Osnovy 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. 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
Literatura
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/
Požadavky
Optimisation, Discrete mathematics, Logics and graphs