PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Celočíselné programování - NOPT016
Anglický název: Integer Programming
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: doc. Mgr. Milan Hladík, Ph.D.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Optimalizace
Anotace -
Poslední úprava: T_KAM (26.04.2017)

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.
Cíl předmětu -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (07.04.2016)

Seznámení studentů s celočíselným programováním, a to nejen s klasickými výsledky, ale i s novými trendy. Absolventi by měli být schopni aplikovat metodologii v praxi stejně dobře jako navázat na aktuální výzkum v oboru.

Literatura -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (07.04.2016)

[1] G.L. Nemhauser, L.A. Wolsey. Integer and combinatorial optimization. Wiley, New York, 1999.

[2] A. Schrijver. Theory of linear and integer programming. Repr. Wiley, Chichester, 1998.

[3] L.A. Wolsey. Integer programming. Wiley, Chichester, 1998.

Sylabus -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (07.04.2016)

  • 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

 
Univerzita Karlova | Informační systém UK