Matematické programování a polyedrální kombinatorika, zimni semestr 2008/2009 (P. Kolman, M. Loebl)

1. přednáška  (8. 10. 2008) Lineární programování v průniku P a NP; úvod k elipsoidové metodě
2. přednáška  (15. 10. 2008) pokracovani elip. met.
3. přednáška  (22. 10. 2008) pokracovani elip. met.
4. přednáška  (29. 10. 2008) dokonceni elip. met.; uvod k metodam vnitrniho bodu

5. přednáška  (6. 11. 2008) metoda vnitrniho bodu - potencial, jak zacit, kdy skoncit, primarni krok

6. přednáška  (13. 11. 2008) metoda vnitrniho bodu - pokles potencialu v primarnim kroku, dualni krok, pokles potencialu v dualnim kroku

7. přednáška  (20. 11. 2008) metoda vnitrniho bodu - dokonceni
Lagrangeova relaxace - uvod

8. přednáška  (27. 11. 2008) Lagrangeova relaxace - dokonceni

9. přednáška  (4.12. 2008) Řezací nadroviny (cutting planes)

10. přednáška  (11.12. 2008) Řezací nadroviny - dokonceni

Literatura:

  • Elipsoidova metoda

    Geometric Algorithms And Combinatorial Optimization
    Groetschel, Lovacz, Schrijver (Springer 1988)

  • Metoda vnitrniho bodu

    Linear programming (Lecture notes)
    Michel X. Goemans
    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

  • Lagrangeova relaxace (kap. 16)

    Network Flows: Theory, Algorithms, and Applications
    Ravindra K. Ahuja, Thomas L. Magnanti, and James Orlin Prentice Hall, 1993

  • Řezací nadroviny (cutting planes)

    Combinatorial Optimization (kap. 6.7)
    Cook W.J., Cunningham William H., Pulleybank W. R., Schriver A.: John Wiley And Sons Ltd (United States), 1997


    listopad 2008