Matematické programování a polyedrální kombinatorika, zimní semestr 2014/15
Petr Kolman, Martin Loebl

Rozvrh

• Ctvrtek 10:40, chodba KAM, 2. patro, Mala Strana

Zapocet

• Ukol
• Data
• Dokumentace k AMPL
• Online resice - NEOS

Témata

• Elipsoidová metoda
• Metoda vnitřního bodu
• Submodularní optimalizace
• Enumerace

Uskutecnene prednasky

• 9.10.2014 Proc patri LP do NP i coNP. Uvod k elipsoidove metode.
• 16.10.2014 Pocatecni elipsoid. Iteracni krok ve zjednodusenem pripade.
• 23.10.2014 Iteracni krok v obecnem pripade. Odhad na potrebny pocet iteraci.
• 30.10.2014 Zjednodusujici predpoklady - jak je zajistit. Separacni oraculum.
• 6.11. - 11.12.2014 Submodularni optimalizace (prof. Loebl)
• 18.12.2014 Metoda vnitrniho bodu

Literatura

• Elipsoidová metoda
  • Skripticka Polynomialni algoritmy pro linearni programovani (vyslo v ITI Series, 2013-601)
  • Učebnice Geometric Algorithms And Combinatorial Optimization, Groetschel, Lovacz, Schrijver (Springer 1988)
• Metoda vnitřního bodu
  • Skripticka Polynomialni algoritmy pro linearni programovani (vyslo v ITI Series, 2013-601)
  • Linear programming (Lecture notes), Michel X. Goemans
  • Článek Polynomial-time Algorithms for linear programming based only on primal scaling and projected gradients of a potential function, Robert M. Freund, Mathematical Programming 51, pp. 203-222, 1991