TIEJ6800 COM1: Stochastic Optimization - Models, Algorithms and Applications (JSS30) (3 cr)

Open the course unit brochure on Sisu

Study level:

Postgraduate studies

Grading scale:

Pass - fail

Language:

English

Responsible organisation:

Faculty of Information Technology

Curriculum periods:

2020-2021, 2021-2022

Description

This course is an introduction to basic models and algorithms of optimization under uncertainty. This course will cover both stochastic programming and robust optimization. Models will include single-, two-, and multi-stage models; pure linear, nonlinear and mixed integer (linear and nonlinear) models. Beneﬁts, strength, necessity and challenges of these models will be discussed versus deterministic optimization. Solution algorithms such as reformulation and decomposition methods will be introduced since these models are usually large-scale and complex. In addition, applications in various areas (e.g., electrical power and energy systems engineering, transportation, business, economics, etc.) will be given to motivate research and enhance students understanding of the methodologies.

Tentative Topics: This course will include two-stage stochastic programming (LP, MILP, NLP, etc.) models, the concept of expected value of perfect information and value of stochastic solutions, L-shaped (Benders decomposition) algorithm for two-stage stochastic programming, integer L-shaped method, formulations of multi-stage stochastic programming models using scenario tree, stochastic dual dynamic programming (nested Benders decomposition), column or nested column generation (Dantzig-Wolfe decomposition) methods for both scenario based and node based formulations, risk-constrained stochastic programming models, chance-constrained models, Conditional Value at Risk based models, single-stage robust optimization models (both continuous and discrete), two-stage robust optimization models, Benders decomposition applied to RO, the concept of budget of uncertainty.

A variety of real-world applications in various areas (e.g., energy/power engineering, transportation, business, economics, etc.) will be given to motivate research and enhance students understanding of the methodologies.

If time allowed, we will try to cover more advanced decomposition algorithm for both SP and RO, and endogenous versus exogenous uncertainty handling.

Learning outcomes

This course is an introduction to basic models and algorithms of optimization under uncertainty. This course will cover both stochastic programming and robust optimization. Models will include single-, two-, and multi-stage models; pure linear, nonlinear and mixed integer (linear and nonlinear) models. Benefits, strength, necessity and challenges of these models will be discussed versus deterministic optimization.

Solution algorithms such as reformulation and decomposition methods will be introduced since these models are usually large-scale and complex. In addition, applications in various areas (e.g., electrical power and energy systems engineering, transportation, business, economics, etc.) will be given to motivate research and enhance students understanding of the methodologies.

The main learning outcomes are to grasp those knowledge points, be able to identify and formulate the right models in reality, and to solve them using advanced algorithms with the assists of state of the art optimization solvers.

Additional information

Software: GAMS (no need to know it before) and Python (some basics is helpful but not required). We also want to encourage students to start using LaTex to write papers.

Useful Links: http://www.gams.com
http://www-03.ibm.com/software/products/us/en/ibmilogcpleoptistud/
http://www.convexoptimization.com/
http://www.miktex.org/
http://www.ctan.org/
http://en.wikipedia.org/wiki/Comparison of TeX editors

Description of prerequisites

Calculus (including multi-variate), Matrix and Linear Algebra (basics), Operations Research (basics of Optimization, e.g., linear, nonlinear, and mixed integer programming), Probability and Statistics (basics).

Literature

J. R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer Verlag, New York, 1997
Aharon Ben-Tal, Laurent El Ghaoui, Arkadi Nemirovski, Robust Optimization, Princeton University Press, 2009

Completion methods

Method 1

Evaluation criteria:

Final grade (Pass/Fail) will be based on homework assignments and course project (analysis of a real-world stochastic optimization applications using the techniques learned in class)

Select all marked parts

Parts of the completion methods

Participation in teaching (3 cr)

Type:

Participation in teaching