Sylabus
- Formulace celočíselných úloh
- Celočíselný polyedr, unimodulární matice, NP-úplnost
- Metody sečných nadrovin a branch & bound
- První a druhý Gomoryho algoritmus
- Preprocessing. Heuristiky
- Problém batohu
- Set covering
- Problém obchodního cestujícího
Předpokládají se základní znalosti lineárního programování.
Anotace
Přednáška se zabývá optimalizačními problémy, kde některé proměnné mohou nabývat jen celočíselných hodnot.
Úlohy celočíselného programování se často vyskytují v praktických problémech a mají silnou formulační schopnost.
Díky vysoké výpočetní složitosti zároveň představují aktuální a důležitý směr výskumu.
Poznámka: Předmět se obvykle koná jednou za dva roky.