-
Computational Aspects of Optimization - lectures (ST 2024/2025)
- -
- Lectures devoted to algorithms, software and applications of mathematical optimization
- Webpages of exercises: HERE
- Moodle with videos (in Czech only): HERE
- Topics for the exam: Otazky_VAO_2022.pdf
- Literature:
- Bazaraa, M.S., Sherali, H.D., and Shetty, C.M. (2006). Nonlinear programming: theory and algorithms, Wiley, Singapore, 3rd edition.
- Boyd, S., Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press, Cambridge.
- Kall, P., Mayer, J. (2005). Stochastic Linear Programming: Models, Theory, and Computation, Springer, New York.
- Nocedal, J., Wright, J.S. (2006). Numerical optimization, Springer, New York, 2nd edition.
- Wolsey, L.A. (1998). Integer Programming, Wiley, New York.
- Text by prof. Lachout freely available THERE
-
Lectures and slides:
- 13.2.2023
- Lecture 1:
- Introduction
- Review of applications of mathematical programming and operations research
- Slides: 00_Branda_Appl_OR_2017.pdf
- TBD
- Lecture 2:
- Linear Programming - simplex algorithm, duality, dual simplex algorithm
- Slides: 01_Branda_DSimplex_2017.pdf
- FOR PRINT: 01_Branda_DSimplex_2017_PRINT.pdf
- TBD
- Lecture 3:
- Benders decomposition
- Slides: 03_Branda_Benders_2018.pdf
- FOR PRINT: 03_Branda_Benders_2018_PRINT.pdf
- TBD
- Lecture 4:
- Integer Linear Programming - applications, basic theory, cutting plane algorithm
- Slides: 04_Branda_ILP_2018.pdf
- FOR PRINT: 04_Branda_ILP_2018_PRINT.pdf
- TBD
- Lecture 5:
- Integer Linear Programming - complexity theory, branch-and-bound, duality, dynamic programming
- Slides: 05_Branda_Complexity_2018.pdf
- FOR PRINT: 05_Branda_Complexity_2018_PRINT.pdf
- TBD
- Lecture 6:
- Integer Linear Programming - network flow, interval scheduling, and vehicle routing problems
- Slides: 06_Branda_VRP_2018.pdf
- FOR PRINT: 06_Branda_VRP_2018_PRINT.pdf
- GAMS source code: CVaR.gms, Returns.txt
- TBD
- Lecture 7:
- Lagrangian duality in nonlinear, linear and integer programming
- Slides: 07_Branda_NLPduality_2017.pdf
- FOR PRINT: 07_Branda_NLPduality_2017_PRINT.pdf
- TBD
- Lecture 8:
- Algorithms for nonlinear programming problems I:
- Convergence, methods based on directions, cutting plane method, penalty method, augmented Lagrangian method
- Slides: 08_Branda_NLPalgorithms_2017.pdf
- FOR PRINT: 08_Branda_NLPalgorithms_2017_PRINT.pdf
- TBD
- Lecture 9:
- Algorithms for nonlinear programming problems II:
- Interior point method, sequential quadratic programming, conjugate gradients
- Slides: 09_Branda_NLPalgorithms_2017.pdf
- FOR PRINT: 09_Branda_NLPalgorithms_2017_PRINT.pdf
- Solver in MS Excel: VAO_Vyrobni_plan.xlsx
- TBD
- Lecture 10:
- Zero-sum games of two players
- Slides: 10_Branda_ZSGames_2017.pdf
- FOR PRINT: 10_Branda_ZSGames_2017_PRINT.pdf
- TBD
- Lecture 11:
- Dynamic programming in discrete time, Bellman principle
- Slides: 11_Branda_DynamicPrgm_2018.pdf
- FOR PRINT: 11_Branda_DynamicPrgm_2018_PRINT.pdf
- Multistage stochastic programming
- Slides 1-19 will be used: SP-multi.pdf
-
Computational Aspects of Optimization - lectures and exercises (ST 2018/2019)
- -
- Lectures devoted to algorithms, software and applications of optimization
- Conditions for the pass:
- 4 homework (will be specified during the semester)
- Homework 1: VAO_HW1.pdf (until March 20)
- Homework 2: VAO_HW2.pdf (until April 10)
- Homework 3: VAO_HW3.pdf (until May 8)
- Homework 4: VAO_HW4.pdf (until May 14)
- MATLAB instalation (in Czech only:(
- Topics for the exam: Otazky_VAO_2019.pdf
- Literature:
- Bazaraa, M.S., Sherali, H.D., and Shetty, C.M. (2006). Nonlinear programming: theory and algorithms, Wiley, Singapore, 3rd edition.
- Boyd, S., Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press, Cambridge.
- Kall, P., Mayer, J. (2005). Stochastic Linear Programming: Models, Theory, and Computation, Springer, New York.
- Nocedal, J., Wright, J.S. (2006). Numerical optimization, Springer, New York, 2nd edition.
- Wolsey, L.A. (1998). Integer Programming, Wiley, New York.
- Text by prof. Lachout freely available THERE
-
Lectures and slides 2019:
- 19. 2. 2019
- Lecture 1:
- Introduction
- Review of applications of mathematical programming and operations research
- 19. 2. 2019
- Lecture 2:
- Linear Programming - simplex algorithm, duality, dual simplex algorithm
- Slides: 01_Branda_DSimplex_2017.pdf
- FOR PRINT: 01_Branda_DSimplex_2017_PRINT.pdf
- 26. 2. 2019
- Lecture 3:
- Benders decomposition
- Slides: 03_Branda_Benders_2018.pdf
- FOR PRINT: 03_Branda_Benders_2018_PRINT.pdf
- 19. 3. 2019
- Lecture 4:
- Integer Linear Programming - applications, basic theory, cutting plane algorithm
- Slides: 04_Branda_ILP_2018.pdf
- FOR PRINT: 04_Branda_ILP_2018_PRINT.pdf
- 19. 3. 2019
- Lecture 5:
- Integer Linear Programming - complexity theory, branch-and-bound, duality, dynamic programming
- Slides: 05_Branda_Complexity_2018.pdf
- FOR PRINT: 05_Branda_Complexity_2018_PRINT.pdf
- 26. 3. 2019
- Lecture 6:
- Integer Linear Programming - network flow, interval scheduling, and vehicle routing problems
- Slides: 06_Branda_VRP_2018.pdf
- FOR PRINT: 06_Branda_VRP_2018_PRINT.pdf
- GAMS source code: CVaR.gms, Returns.txt
- 2. 4. 2019
- Lecture 7:
- Lagrangian duality in nonlinear, linear and integer programming
- Slides: 07_Branda_NLPduality_2017.pdf
- FOR PRINT: 07_Branda_NLPduality_2017_PRINT.pdf
- 9. 4. 2019
- Lecture 8:
- Algorithms for nonlinear programming problems I:
- Convergence, methods based on directions, cutting plane method, penalty method, augmented Lagrangian method
- Slides: 08_Branda_NLPalgorithms_2017.pdf
- FOR PRINT: 08_Branda_NLPalgorithms_2017_PRINT.pdf
- 16. 4. 2019
- Lecture 9:
- Algorithms for nonlinear programming problems II:
- Interior point method, sequential quadratic programming, conjugate gradients
- Slides: 09_Branda_NLPalgorithms_2017.pdf
- FOR PRINT: 09_Branda_NLPalgorithms_2017_PRINT.pdf
- Solver in MS Excel: VAO_Vyrobni_plan.xlsx
- 30. 4. 2019
- Lecture 10:
- Zero-sum games of two players
- Slides: 10_Branda_ZSGames_2017.pdf
- FOR PRINT: 10_Branda_ZSGames_2017_PRINT.pdf
- 7. 5. 2019
- Lecture 11:
- Dynamic programming in discrete time, Bellman principle
- Slides: 11_Branda_DynamicPrgm_2018.pdf
- FOR PRINT: 11_Branda_DynamicPrgm_2018_PRINT.pdf
-
Lectures and slides 2018:
- 23. 2. 2018
- Lecture 1:
- Introduction
- Review of applications of mathematical programming and operations research
- 2. 3. 2018
- Lecture 2:
- Linear Programming - simplex algorithm, duality, dual simplex algorithm
- Slides: 01_Branda_DSimplex_2017.pdf
- FOR PRINT: 01_Branda_DSimplex_2017_PRINT.pdf
- 9. 3. 2018
- Lecture 3:
- Benders decomposition
- Slides: 03_Branda_Benders_2018.pdf
- FOR PRINT: 03_Branda_Benders_2018_PRINT.pdf
- 16. 3. 2018
- Lecture 4:
- Integer Linear Programming - applications, basic theory, cutting plane algorithm
- Slides: 04_Branda_ILP_2018.pdf
- FOR PRINT: 04_Branda_ILP_2018_PRINT.pdf
- 23. 3. 2018
- Lecture 5:
- Integer Linear Programming - complexity theory, branch-and-bound, duality, dynamic programming
- Slides: 05_Branda_Complexity_2018.pdf
- FOR PRINT: 05_Branda_Complexity_2018_PRINT.pdf
- 6. 4. 2018
- Lecture 6:
- Integer Linear Programming - network flow, interval scheduling, and vehicle routing problems
- Slides: 06_Branda_VRP_2018.pdf
- FOR PRINT: 06_Branda_VRP_2018_PRINT.pdf
- 20. 4. 2018
- Lecture 7:
- Lagrangian duality in nonlinear, linear and integer programming
- Slides: 07_Branda_NLPduality_2017.pdf
- FOR PRINT: 07_Branda_NLPduality_2017_PRINT.pdf
- 27. 4. 2018
- Lecture 8:
- Algorithms for nonlinear programming problems I:
- Convergence, methods based on directions, cutting plane method, penalty method, augmented Lagrangian method
- Slides: 08_Branda_NLPalgorithms_2017.pdf
- FOR PRINT: 08_Branda_NLPalgorithms_2017_PRINT.pdf
- 4. 5. 2018
- Lecture 9:
- Algorithms for nonlinear programming problems II:
- Interior point method, sequential quadratic programming, conjugate gradients
- Slides: 09_Branda_NLPalgorithms_2017.pdf
- FOR PRINT: 09_Branda_NLPalgorithms_2017_PRINT.pdf
- 11. 5. 2018
- Lecture 10:
- Zero-sum games of two players
- Slides: 10_Branda_ZSGames_2017.pdf
- FOR PRINT: 10_Branda_ZSGames_2017_PRINT.pdf
- 18. 5. 2018
- Lecture 11:
- Dynamic programming in discrete time, Bellman principle
- Slides: 11_Branda_DynamicPrgm_2018.pdf
- FOR PRINT: 11_Branda_DynamicPrgm_2018_PRINT.pdf
-
Lectures and slides 2017:
- 20. 2. 2017
- Lecture 1:
- Introduction
- Review of applications of Mathematical Programming and Operations Research
- Slides: 00_Branda_Appl_OR_2017.pdf
- 27. 2. 2017
- Lecture 2:
- Linear Programming - simplex algorithm, duality, dual simplex algorithm
- Slides: 01_Branda_DSimplex_2017.pdf
- FOR PRINT: 01_Branda_DSimplex_2017_PRINT.pdf
- 6. 3. 2017
- Lecture 3:
- Benders decomposition
- Slides: 03_Branda_Benders_2017.pdf
- FOR PRINT: 03_Branda_Benders_2017_PRINT.pdf
- 13. 3. 2017
- Lecture 4:
- Integer Linear Programming - applications, basic theory, cutting plane algorithm
- Slides: 04_Branda_ILP_2017.pdf
- FOR PRINT: 04_Branda_ILP_2017_PRINT.pdf
- 20. 3. 2017
- Lecture 5:
- Integer Linear Programming - complexity theory, branch-and-bound, duality, dynamic programming
- Slides: 05_Branda_Complexity_2017.pdf
- FOR PRINT: 05_Branda_Complexity_2017_PRINT.pdf
- 3. 4. 2017
- Lecture 6:
- Integer Linear Programming - network flow, interval scheduling, and vehicle routing problems
- Slides: 06_Branda_VRP_2017.pdf
- FOR PRINT: 06_Branda_VRP_2017_PRINT.pdf
- 10. 4. 2017
- Lecture 7:
- Lagrangian duality in nonlinear, linear and integer programming
- Slides: 07_Branda_NLPduality_2017.pdf
- FOR PRINT: 07_Branda_NLPduality_2017_PRINT.pdf
- 24. 4. 2017
- Lecture 8:
- Algorithms for nonlinear programming problems I:
- Convergence, methods based on directions, cutting plane method, penalty method, augmented Lagrangian method
- Slides: 08_Branda_NLPalgorithms_2017.pdf
- FOR PRINT: 08_Branda_NLPalgorithms_2017_PRINT.pdf
- 15. 5. 2017
- Lecture 9:
- Algorithms for nonlinear programming problems II:
- Interior point method, sequential quadratic programming, conjugate gradients
- Slides: 09_Branda_NLPalgorithms_2017.pdf
- FOR PRINT: 09_Branda_NLPalgorithms_2017_PRINT.pdf
- 22. 5. 2017
- Lecture 10:
- Zero-sum games of two players
- Slides: 10_Branda_ZSGames_2017.pdf
- FOR PRINT: 10_Branda_ZSGames_2017_PRINT.pdf
- Dynamic programming in discrete time, Bellman principle
- Slides: 11_Branda_DynamicPrgm_2017.pdf
-
Výpočetní aspekty optimalizace - přednáška a cvičení (LS 2015/2016)
- -
- Podmínky pro udělení zápočtu:
- Vypracování a odevzdání 5 domácích úloh - nutné získat 80% bodů
- Okruhy otázek ke zkoušce: Otazky_VAO_2016.pdf
- Literatura:
- Bazaraa, M.S., Sherali, H.D., and Shetty, C.M. (2006). Nonlinear programming: theory and algorithms, Wiley, Singapore, 3rd edition.
- Boyd, S., Vandenberghe, L. (2004). Convex Optimization, Cambridge University Press, Cambridge.
- Kall, P., Mayer, J. (2005). Stochastic Linear Programming: Models, Theory, and Computation, Springer, New York.
- Nocedal, J., Wright, J.S. (2006). Numerical optimization, Springer, New York, 2nd edition.
- Wolsey, L.A. (1998). Integer Programming, Wiley, New York.
- Skripta doc. Lachouta volně ke stažení ZDE
-
Program 2016 (přednáška bude česky, podpůrné materiály převážně anglicky):
- 23. 2. 2016
- Lecture 0:
- Introduction
- Review of applications of Mathematical Programming and Operations Research
- Presentation: 00_Branda_Appl_OR_en.pdf
- 1. 3. 2016
- Lecture 1:
- Linear Programming - simplex algorithm, duality, dual simplex algorithm
- Presentation: 01_Branda_DSimplex.pdf
- Presentation - with added explanation: 01_Branda_DSimplex_mod.pdf
- 8. 3. 2016
- Lecture 2:
- Linear Programming - duality and shadow prices
- Quadratic Programming - Wolfe algorithm
- Presentation: 02_Branda_LPduality_Wolfe.pdf
- Solver in MS Excel: VAO_Vyrobni_plan.xlsx
- Homework 1: VAO_HW1.pdf
- 15. 3. 2016
- Lecture 3:
- Benders decomposition
- Presentation: 03_Branda_Benders_en.pdf
- 22. 3. 2016
- Lecture 4:
- Integer Linear Programming - theory and algorithms
- Presentation: 04_Branda_ILP_en.pdf
- 29. 3. 2016
- Lecture 5:
- Introduction to computational complexity
- Software tools NOT ONLY for mixed-integer programming problems
- Presentation: 05_Branda_Complexity_en.pdf
- GAMS source code: CVaR.gms, Returns.txt
- 5. 4. 2016
- Lecture 6:
- Mixed-Integer Linear Programming - real-life problems
- Presentation: 06_Branda_VRP_en.pdf
- CCP, VaR, Homework 2: 06_Branda_CCP_VaR_en.pdf
- 12. 4. 2016
- Lecture 7:
- Lagrangian duality in nonlinear programming I
- Presentation: 07_Branda_NLPduality_eng.pdf
- 19. 4. 2016
- Lecture 8:
- Lagrangian duality in nonlinear programming II
- Algorithms for nonlinear programming problems (Wolfe alg.)
- Algorithm tracking: Algorithm_tracking.nb
- 26. 4. 2016
- Lecture 9:
- Algorithms for nonlinear programming problems I
- Presentation: 08_Branda_NLPalgorithms_en.pdf
- 3. 5. 2016
- Lecture 10:
- Algorithms for nonlinear programming problems II
- Presentation: 09_Branda_NLPalgorithms_en.pdf
- Interior Point Method example: IPM_Example.nb
- Homework 3: VAO_HW3.pdf
- 10. 5. 2016
- Lecture 11: RNDr. Michal Červinka, Ph.D. (UTIA AV, FSV UK)
- Introduction to equilibrium problems and application to emission allowances markets
- Presentation: 10_Cervinka_MFF_2016.pdf
- 17. 5. 2016
- Lecture 12:
- Zero-sum games of two players
- Optimization in SAS and Matlab
- Presentation: 11_Branda_ZSGames_en.pdf
- X. X. 2016
- Self-study:
- Dynamic programming in discrete time (Bellman principle) - Examples
- Presentation: 12_Branda_DynamicPrgm_en.pdf
-
Výpočetní aspekty optimalizace - seminář (LS 2014/2015)
- -
- Podmínky pro udělení zápočtu:
- Aktivní účast na semináři (max. 2 neomluvené absence)
- Vypracování a odevzdání 4 domácích úloh - nutné získat 80% bodů
- Literatura:
- Bazaraa, M.S., Sherali, H.D., and Shetty, C.M. (2006). Nonlinear programming: theory and algorithms, Wiley, Singapore, 3rd edition.
- Nocedal, J., Wright, J.S. (2006). Numerical optimization, Springer, New York, 2nd edition.
- Pedegral, P. (2004). Introduction to optimization, Springer-Verlag, New York.
- Bude doplňována v průběhu semestru.
-
Program semináře 2015:
- 23. 2. 2015
- 1. seminář - doc. Kopa:
- Algoritmy a software pro (velké) úlohy lineárního programování
- 2. 3. 2015
- 2. seminář - dr. Branda:
- Software pro úlohy nelineárního programování (data)
- Přehled software: VAO_software.pdf
- Markowitzův model v GAMSu: MVmodel.gms
- Zadání DÚ: VAO_zadani_DU1.pdf
- 16. 3. 2015
- 3. seminář - dr. Branda:
- Algoritmy pro úlohy nelineárního programování
- 30. 3. 2015
- 4. seminář - dr. Branda:
- Algoritmy a software pro úlohy celočíselné optimalizace
- Slajdy: Branda_MIP_2015.pdf
- Zadání DÚ: VAO_zadani_DU2.pdf
- 13. 4. 2015
- 5. seminář - doc. Michal Černý:
- Příběhy o optimalizaci a výpočetní složitosti
- (ne nutně s dobrým koncem)
- 27. 4. 2015
- 6. seminář - doc. Milan Hladík:
- Hledání globálního minima pomocí intervalového počítání
- Slajdy: Hladik_glob_opt_2015.pdf
- 11. 5. 2015
- 7. seminář - Mgr. Němeček, dr. Branda:
- Seminář o řešení náročných úloh plánování rozvozu
- (Vehicle routing problems)
- Slajdy: Branda_VRP_2015.pdf
- Zadání DÚ: VAO_zadani_DU3.pdf
-
Výpočetní aspekty optimalizace (LS 2013/2014) - společně s doc. Kopou
- -
- Podmínky pro udělení zápočtu:
- Aktivní účast na semináři
- Vypracování a odevzdání 4 domácích úloh
- Literatura:
- Bazaraa, M.S., Sherali, H.D., and Shetty, C.M. (2006). Nonlinear programming: theory and algorithms, Wiley, Singapore, 3rd edition.
-
Program semináře 2014:
- 1. seminář (doc. Kopa):
- Algoritmy a software pro (velké) úlohy lineárního programování
- Zadání DÚ
- 2. seminář (doc. Kopa):
- Algoritmy a software pro úlohy nelineárního programování
- 3. seminář (Mgr. Adam):
- Algoritmy a software pro úlohy nelineárního programování
- 4. seminář (dr. Branda):
- Algoritmy a software pro úlohy celočíselné optimalizace:
- - Metoda sečných nadrovin a Gomoryho řezy.
- - Branch and bound.
- 5. seminář (dr. Branda):
- Algoritmy a software pro úlohy s pravděpodobnostními omezeními:
- - Formulace pro diskrétní rozdělení pomocí binárních proměnných.
- - Zobecnění kvantilu pro vícerozměrná diskrétní rozdělení (PLEPS).
- - Investiční problém s pravpěpodobnostním omezením: článek.
- Zadání DÚ
- 6. seminář (dr. Kozmík):
- Vícestupňové úlohy stochastického programování
- Bendersova dekompozice ve stochastickém programování: Slajdy
- 7. seminář (doc. Kopa):
- Vícekriteriální optimalizace
- Zadání a kontrola DÚ: doc. Kopa
Martin Branda
Univerzita Karlova, Matematicko-fyzikální fakulta
Katedra pravděpodobnosti a matematické statistiky
Katedra pravděpodobnosti a matematické statistiky
Sokolovská 83, 186 75 Praha 8
branda@karlin.mff.cuni.cz
branda@karlin.mff.cuni.cz
Copyright © JČ, MB 2011