Celočíselné programování

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.