Interface Course 2019
Stochastic Optimization for Large-Scale Systems
November 4 to 8, 2019

P. Carpentier1, J.-P. Chancelier2, M. De Lara3, V. Leclère4
ENSTA ParisTech and École des Ponts ParisTech

Image ensta                                                  Image ecole_ponts_CMJN


Sensors and data abound. This spatial and temporal information is supposed to allow a better management -- in new energy systems, transport or eco-industrial parks, to quote a few examples. This leads to problems of large-scale optimization, the formulation of which is delicate. Indeed, one needs to take into account at least three dimensions: temporal (stages of decision, dynamics, inertia), spatial (different decision units connected by flows), stochastic (various scenarios are possible) and thus risk. This leads to multi-stage stochastic optimization problems which enter the class of large-scale systems.

The 4 days session Interface 2019 Stochastic Optimization for Large-Scale Systems will present tools and methods to formulate and solve such problems. For this purpose, courses, computing sessions and interactive sessions will alternate.

The school addresses a mixed public, in the academy and in the industry. These four days of immersion in the CIRM (International Center of Mathematical Meetings, Marseille) will make discussions and exchanges possible, be it during or outside the training sessions. The institutional organizers are the ENSTA ParisTech and the École des Ponts ParisTech.

Keywords: stochastic programming, scenario trees, progressive hedging, stochastic optimal control, stochastic dynamic programming, stochastic dual dynamic programming, spatial decomposition.



pdf version of this document

1 Organizing committee, speakers and participants

1.1 Organizing committee

The organizing committee is made of the following French researchers

1.2 Scientific committee

1.3 Target audience and preriquisites

The course mainly deals with optimization in a dynamical setting and subject to uncertain perturbations. The iconic example consists of managing a stock when facing an uncertain demand over a given time span. The decisions of refilling the stock are taken at given discrete instants, knowing the past demand uncertainties.

Such optimization problems occur in most industries and services dealing with stochastic dynamical systems, such as dam management, battery aging, smart-grid control in the energy field, or managing dynamic equilibrium between demand and offer in a context where production and transport are coupled via a network (petroleum industry).

Prerequisites are:

Computer and softwares:

2 Program

During the first part of the course (sessions 1 to 3), we will present the two standard mathematical approaches dealing with stochastic multistage optimization problems, that is, stochastic programming and stochastic optimal control. The sessions include several practical works in Julia.

Multistage stochastic optimization problems are often too large to be solved in a straightforward manner. During the second part of the course (sessions 5 to 8), we will present advanced methods allowing to solve such problems by decomposition, that is, by iteratively (in parallel or sequentially) solving subproblems of a reasonable size rather than the whole one. We will recall the notions from convex optimization and duality theory necessary for devising such methods.

2.1 Session 1: November 4, 2019 (afternoon).
Introduction to Stochastic Optimization

Speaker: Michel De Lara

The course starts with basics in stochastic optimization.

2.2 Session 2: November 5, 2019 (morning).
Stochastic Multistage Optimization

Speaker: Michel De Lara

When the problem incorporates several time steps, the stochastic programming approach proposes to build a scenario tree of uncertainties, and to attach one control per node, hence leading to an equivalent deterministic formulation. We present alternative equivalent deterministic formulations.

We discuss the importance of information structures in multistage optimization, as well as how to use such structures to obtain computable bounds.

We end the session with an hands-on project, that tackles a multistage version of the problem studied in Session 1.

2.3 Session 3: November 5, 2019 (afternoon).
Stochastic Optimal Control and Dynamic Programming

Speaker: Jean-Philippe Chancelier

The stochastic optimal control approach looks at the problem from a Markovian point of view, where uncertainties are stagewise independent. We present a generic way of solving this problem by Dynamic Programming.

We end the session by applying Dynamic Programming to the problem studied in Session 2.

2.4 Session 4: November 6, 2019 (morning).
Interactive Session

During this morning, industrials will present their current problems. It will be the occasion to address some specific difficulties encountered when dealing with real-life problems.

Based on industrial participant's proposals, we will organize small groups to tackle specific issues during the numerous ``course free'' periods enabled by the immersive nature of the Interface program.

2.5 Session 5: November 6, 2019 (afternoon).
Scenario Decomposition: Progressive Hedging Algorithm

Speaker: Jean-Philippe Chancelier and Vincent Leclère

When a stochastic multistage optimization optimization is formulated on a large number of scenarios, decomposition techniques can be used to iteratively solve a collection of subproblems, each formulated along a single scenario.

We present two approaches : (augmented) Lagrangian decomposition along scenarios, leading to the Progressive Hedging algorithm, and Bender's decomposition leading to the L-Shaped method.

2.6 Session 6: November 7, 2019 (morning).
Stochastic Dual Dynamic Programming (SDDP)

Speaker: Michel De Lara and Vincent Leclère

In the framework of dynamic programming, the SDDP (Stochastic Dual Dynamic Programming) method allows to push forward the limits of the curse of dimensionality. Taking advantage of linearity and convexity, SDDP builds (lower) approximations of the Bellman value functions in an iterative way.

2.7 Session 7: November 6, 2019 (afternoon).
Practical Works on SDDP

The afternoon is devoted to a computer session aiming at discovering SDDP algorithm through the Julia software (StochDynamicProgramming package).

2.8 Session 8: November 8, 2019 (morning).
Spatial Decomposition Methods

Speaker: Pierre Carpentier

During this last session, we will explore different decomposition schemes allowing to split a stochastic optimal control problem -- involving a large number of units -- so as to obtain several small-scale subproblems. These methods allow to solve the subproblems by Dynamic Programming or SDDP.


D. P. Bertsekas.
Dynamic Programming and Optimal Control.
Athena Scientific, Belmont, Massachusetts, second edition, 2000.
Volumes 1 and 2.

P. Carpentier, J.-P. Chancelier, G. Cohen, and M. De Lara.
Stochastic Multi-Stage Optimization. At the Crossroads between Discrete Time Stochastic Control and Stochastic Programming.
Springer-Verlag, Berlin, 2015.

R.T. Rockafellar and R. J-B. Wets.
Scenarios and policy aggregation in optimization under uncertainty.
Mathematics of operations research, 16(1):119-147, 1991.

A. Shapiro, D. Dentcheva, and A. Ruszczynski.
Lectures on stochastic programming: modeling and theory.
The society for industrial and applied mathematics and the mathematical programming society, Philadelphia, USA, 2009.


... Carpentier1
... Chancelier2
... Lara3