Problémy kombinatorické optimalizace – formulace, rozbor složitosti, algoritmy a příklady aplikací.

Celočíselné lineární programování. Problém nejkratších cest a problém obchodního cestujícího - ILP formulace. Algoritmus Branch and Bound. Formulace problémů pomocí ILP. Speciální ILP problémy řešitelné v polynomiálním čase.
Problém nejkratších cest. Algoritmy Dijkstry, Bellman-Ford a Floyd-Warshall. Nejkratší cesty v orientovaných acyklických grafech. Formulace problémů s využitím nejkratších cest.
Síťové toky. Problémy maximálního toku a minimálního řezu. Algoritmus Ford-Fulkerson. Přípustný tok s bilancemi. Minimální nákladový tok a algoritmus rušení cyklů. Formulace problémů s využitím síťových toků. Párování s maximální mohutností.
Problém batohu. Aproximační algoritmus, přístup dynamického programování, aproximační schéma.
Problém obchodního cestujícího. Algoritmus Double-tree a Christofidesův algoritmus pro metrický problém. Lokální prohledávání k-OPT.
Plánování – popis problému a notace. Jeden zdroj – Bratleyho algoritmus, Hornův algoritmus. Paralelní identické zdroje – list scheduling, dynamické programování. Plánování projektů s časovými omezeními – ILP formulace relativního pořadí a časového indexu.
Problém splňování omezujících podmínek (CSP). Algoritmus AC3.

Trace: • b4m35ko