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

[[https://fel.cvut.cz/cz/education/bk/predmety/46/79/p4679206.html|BE4M35KO]] [[https://cw.fel.cvut.cz/wiki/courses/ko/start|Webové stránky předmětu]]

  * **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.