Interface course 
Stochastic Optimization for Large-Scale Systems
rom Monday 4th November 2019 to Friday 8th November 2019

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 possible scenarios) and thus risk. This leads to multi-stage stochastic optimization problems which enter the class of large-scale systems.

The 4-day session entitled ‘Interface 2019 Stochastic Optimization for Large-Scale Systems‘ will present tools and methods to formulate and solve such problems. To this end, various types of activities will take place including courses, computing sessions and interactive sessions.

The session addresses a mixed public, both from academia and from industry. These four days in immersion at CIRM will make discussions and exchanges possible, during and outside training sessions. Institutional organizers are ENSTA ParisTech and École des Ponts ParisTech.

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

November 4 (afternoon)
Introduction to Stochastic Optimization
Speaker: Michel De Lara
The course starts with basics in stochastic optimization
• One-stage Stochastic programming
• Practical work: the newsvendor problem

November 5 (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 lead- ing to an equivalent deterministic formulation. We present alternative equivalent deterministic formulations. We discuss the importance of information structure in multistage program, as well as how to modify theses structures to obtain computable bounds. We end the session with an hands-on project, that formulate a multistage version of the problem studied in session 1.
• Stochastic programming: from one-stage to
multistage problems
• break
• Practical work: the flower girl problem

November 5 (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 before
• Stochastic optimal control. Dynamic
Programming approach
• Practical work: the flower girl (continued)

November 6 – 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.
09:00–12:00: Discussion with industrials presenting their current problems. Among possible questions, let us mention
– how to take into account correlated noises,
– how to incorporate risk in the modeling,
– how to devise a good final cost.
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 Programme.

November 6 – Afternoon
Scenario Decomposition: Progressive Hedging Algorithm
Speakers: Jean-Philippe Chancelier and Vincent Leclère
When a stochastic multistage optimization is formulated on a large number of scenarios, decomposition techniques can be used in order to iteratively solve a collection of subproblems each formulated on a single scenario.
We present two approaches : (Augmented) Lagrangian decomposition of scenario, leading to the Progressive Hedging algorithm, and Bender’s decomposition leading to the L-Shaped method.
• Progressive Hedging algorithm
• L-Shaped method

November 7 – Morning
Stochastic Dual Dynamic Programming (SDDP)
Speakers: Michel De Lara and Vincent Leclère
In the framework of dynamic programming, the SDDP (Stochastic Dual DynamicProgramming) method allows to push forward the limits of the curse of dimensionality. Taking advantage of linearity and convexity, SDDP builds approximations of the Bellman value functions in an iterative way.
• General overview of decomposition methods
• Stochastic Dual Dynamic Programming algorithm

November 7 – Afternoon
Practical Works on SDDP
The afternoon is devoted to a computer session aiming at discovering SDDP algorithm through the Julia software (StochDynamicProgramming package). Practical work: SDDP in action

November 8 – 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 in order to solve several small-scale subproblems.
These methods allow to solve the subproblems by Dynamic Programming or SDDP.
• Mixing decomposition techniques and Dynamic Programming
• Dual Approximate Dynamic Programming and related methods