1 of 75

2 of 75

Lecture 05: Multi-stage Stochastic Programming

2

Scan me:

Quizzes

​

Anonymous Questions (during or after the lecture)

The Lecture will be recorded

vevox.app�176-006-553

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

3 of 75

Course Plan

3

without�Uncertainty

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

4 of 75

Agenda for today

4

  1. Quick Recap: 2-stage Stochastic Lookahead policy
  2. Multi-stage Stochastic Lookahead as a policy for Sequential Decision-Making problems
  3. Nuts and Bolts
  4. Examples

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

5 of 75

Agenda for today

5

  1. Deterministic Lookahead policy recap
  2. reason why it might not perform well (e.g. skewed distributions, fat tails, the fact that the average scenario might be a non-existent scenario, etc)
  3. describe a simple, naturally 2-stage problem and introduce 2-stage SP
  4. present the general formulation
  5. present 2-stage SP as a policy for the student's (actually multistage) problem
  6. Number of variables as a function of scenarios
  7. Scenario reduction techniques.
  8. present a 2-stage SP policy for the lead example.
  9. present a 2-stage SP where the second stage actually looks multiple stages ahead, but without non-anticipativity constraints (so, it is technically still a 2-stage policy, because what matters is when information arrives…)
  10. Extra: other scenario generation techniques (e.g. bootstrapping)

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

6 of 75

Policies: The story so far

Expected Cost

Deterministic Lookahead policy

Optimal in Hindsight

Dummy policy

Optimal Policy

2-stage Stochastic Lookahead policy

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

7 of 75

Lookahead Policy

Optimal Policy:

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

8 of 75

Rolling Horizon Optimization

8

L

1 2 ... 22 23 24

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

9 of 75

Scenario Generation

Data

Model

Not in this course

Given to you

We assume the probability distribution of the uncertainty (given the state) is available.

Then, we can sample scenarios from that.

We need at least 100 samples to capture the statistical properties of the uncertainty.

�The challenge is that

more scenarios 🡪 more variables 🡪 higher computational time

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

10 of 75

Dinner Party problem: More than one uncertainties

10

First stage problem

 

 

 

To capture the statistical properties of the uncertainty, we now need at least 1000 scenarios (samples).

But we still can only afford 33.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

11 of 75

Scenario Reduction

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

12 of 75

2-stage Stochastic Lookahead Policy

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

13 of 75

2-stage Stochastic Lookahead Policy

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

14 of 75

2-stage Stochastic Lookahead Policy

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

15 of 75

Effective vs Prospective Decisions

Let’s say we are in stage 3. We observe the current state and make predictions for the state at stage 4, to inform the here-and-now decision

When stage 4 comes, we observe the new state and do the same to calculate the here-and-now decision for stage 4.

So, we solve an optimization problem again, and do not use the previously made prospective decisions.

1 2 3 4 5 6 � stages

1 2 3 4 5 6 � stages

Uncertainty Realization

Uncertainty Realization

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

16 of 75

Multi-stage Stochastic Programming

16

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

17 of 75

Extending the 2-stage Stochastic Program

 

 

2-stage Stochastic Lookahead Optimization

 

 

 

DTU Compute

24 May 2023

18 of 75

Extending the 2-stage Stochastic Program

 

 

2-stage Stochastic Lookahead Optimization

 

 

?-stage Stochastic Lookahead Optimization

“This is a [?]-stage Lookahead”

 

DTU Compute

24 May 2023

19 of 75

Extending the 2-stage Stochastic Program

 

 

2-stage Stochastic Lookahead Optimization

 

 

?-stage Stochastic Lookahead Optimization

“This is a [?]-stage Lookahead”

Looks like a 4-stage lookahead, but actually there is no new information after stage 2.

DTU Compute

24 May 2023

20 of 75

Extending the 2-stage Stochastic Program

 

4-stage Stochastic Lookahead Optimization

 

DTU Compute

24 May 2023

21 of 75

Extending the 2-stage Stochastic Program

 

4-stage Stochastic Lookahead Optimization

 

 

DTU Compute

24 May 2023

22 of 75

Extending the 2-stage Stochastic Program

 

4-stage Stochastic Lookahead Optimization

 

But what should change in the actual optimization problem?

DTU Compute

24 May 2023

23 of 75

Extending the 2-stage Stochastic Program

 

 

4-stage Stochastic Lookahead Optimization

 

 

Non-anticipativity�Sets

DTU Compute

24 May 2023

24 of 75

Intuition for non-anticipativity

When should you sell your asset?

Full Recourse vs Binding Decisions

DTU Compute

24 May 2023

25 of 75

Multi-stage Stochastic Lookahead Policy

25

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

26 of 75

Multi-Stage SP policy: summary

26

New state revealed

Construct the non-anticipativity sets

Beginning from the new state, create scenario tree for the lookahead horizon

Solve the multi-stage �stochastic program

Implement the optimal here-and-now decision

DTU Compute

24 May 2023

27 of 75

Repeated Branch-out & Cluster

27

 

DTU Compute

24 May 2023

28 of 75

 

28

 

DTU Compute

24 May 2023

29 of 75

Cluster

29

 

DTU Compute

24 May 2023

30 of 75

Allocate Probability to each Centroid

30

 

DTU Compute

24 May 2023

31 of 75

Ready to Move on…

31

 

0.3

0.3

0.4

DTU Compute

24 May 2023

32 of 75

 

32

 

DTU Compute

24 May 2023

33 of 75

Cluster

33

 

DTU Compute

24 May 2023

34 of 75

Repeat…

34

 

DTU Compute

24 May 2023

35 of 75

Repeat…

35

 

0.3

0.3

0.4

0.3

0.3

0.4

0.3

0.6

0.1

0.2

0.3

0.5

DTU Compute

24 May 2023

36 of 75

Create Scenarios

36

 

1

2

3

4

5

6

9

7

8

0.3

0.3

0.4

0.3

0.3

0.4

0.3

0.6

0.1

0.2

0.3

0.5

Each path (ending up to a leaf node) is one scenario.

Calculate the probability of each scenario, by multiplying the probabilities across the path.

DTU Compute

24 May 2023

37 of 75

Multi-Stage Stochastic Programming policy

 

 

 

DTU Compute

24 May 2023

38 of 75

Multi-Stage Stochastic Programming policy

 

 

 

 

DTU Compute

24 May 2023

39 of 75

Multi-Stage Stochastic Programming policy

 

 

 

 

DTU Compute

24 May 2023

40 of 75

Multi-Stage Stochastic Programming policy

 

 

 

 

DTU Compute

24 May 2023

41 of 75

Multi-Stage Stochastic Programming policy

 

 

 

 

DTU Compute

24 May 2023

42 of 75

Multi-Stage Stochastic Programming policy

 

 

 

 

 

DTU Compute

24 May 2023

43 of 75

Multi-Stage Stochastic Programming policy

 

 

 

 

Iterative Branch & Cluster

DTU Compute

24 May 2023

44 of 75

Multi-Stage Stochastic Programming policy

 

 

 

 

Populating non-anticipativity sets

DTU Compute

24 May 2023

45 of 75

Multi-Stage Stochastic Programming policy

 

 

 

 

 

Iterative Branch & Cluster

Populating non-anticipativity sets

DTU Compute

24 May 2023

46 of 75

How many Scenarios?

46

 

1

2

3

4

5

6

9

7

8

0.3

0.3

0.4

0.3

0.3

0.4

0.3

0.6

0.1

0.2

0.3

0.5

 

DTU Compute

24 May 2023

47 of 75

How to build a Multi-Stage SP Policy

47

 

DTU Compute

24 May 2023

48 of 75

Student’s problem Example

48

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

49 of 75

Multi-stage Stochastic Lookahead Policy

The student’s problem: Multi-stage Stochastic Lookahead

Sequential Decision Problem

 

 

Let’s consider that the fatigue threshold is also uncertain

DTU Compute

24 May 2023

50 of 75

Multi-stage Stochastic Lookahead Policy

Sequential Decision Problem

 

 

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

The student’s problem: Multi-stage Stochastic Lookahead

DTU Compute

24 May 2023

51 of 75

Multi-stage Stochastic Lookahead Policy

Sequential Decision Problem

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

The student’s problem: Multi-stage Stochastic Lookahead

 

DTU Compute

24 May 2023

52 of 75

Multi-stage Stochastic Lookahead Policy

Sequential Decision Problem

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

The student’s problem: Multi-stage Stochastic Lookahead

 

DTU Compute

24 May 2023

53 of 75

Multi-stage Stochastic Lookahead Policy

Sequential Decision Problem

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

The student’s problem: Multi-stage Stochastic Lookahead

 

DTU Compute

24 May 2023

54 of 75

Multi-stage Stochastic Lookahead Policy

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

 

 

 

 

 

The student’s problem: Multi-stage Stochastic Lookahead

DTU Compute

24 May 2023

55 of 75

Multi-stage Stochastic Lookahead Policy

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

 

 

 

 

The student’s problem: Multi-stage Stochastic Lookahead

DTU Compute

24 May 2023

56 of 75

Multi-stage Stochastic Lookahead Policy

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

 

 

 

 

 

 

 

The student’s problem: Multi-stage Stochastic Lookahead

DTU Compute

24 May 2023

57 of 75

Multi-stage Stochastic Lookahead Policy

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

 

 

 

 

 

 

 

 

The student’s problem: Multi-stage Stochastic Lookahead

DTU Compute

24 May 2023

58 of 75

Multi-stage Stochastic Lookahead Policy

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

1

2

3

4

5

6

9

7

8

The student’s problem: Multi-stage Stochastic Lookahead

DTU Compute

24 May 2023

59 of 75

Multi-stage Stochastic Lookahead Policy

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

1

2

3

4

5

6

9

7

8

 

 

The student’s problem: Multi-stage Stochastic Lookahead

DTU Compute

24 May 2023

60 of 75

Multi-stage Stochastic Lookahead Policy

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

1

2

3

4

5

6

9

7

8

 

 

The student’s problem: Multi-stage Stochastic Lookahead

 

DTU Compute

24 May 2023

61 of 75

Multi-stage Stochastic Lookahead Policy

  1. Specify the Lookahead Horizon Length.
  2. Specify the structure of the scenario tree.
  3. Create Scenarios and probabilities.
  4. Create non-anticipativity sets.
  5. Solve the L-stage stochastic program.

 

 

 

2

3

4

5

6

7

8

9

 

 

The student’s problem: Node-based formulation

10

11

12

13

 

DTU Compute

24 May 2023

62 of 75

Stochastic Lookahead Policy Evaluation

62

5-stage simulation horizon

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

63 of 75

Stochastic Lookahead Policy Evaluation

63

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

64 of 75

Stochastic Lookahead Policy Evaluation

64

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

65 of 75

Stochastic Lookahead Policy Evaluation

65

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

66 of 75

Stochastic Lookahead Policy Evaluation

66

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

67 of 75

Stochastic Lookahead Policy Evaluation

67

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

68 of 75

Stochastic Lookahead Policy Evaluation

68

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

69 of 75

Stochastic Lookahead Policy Evaluation

69

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

70 of 75

Stochastic Lookahead Policy Evaluation

70

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

DTU Compute

24 May 2023

71 of 75

Stochastic Lookahead Policy Evaluation

71

5-stage problem

Policy: Lookahead horizon of 3 stages with 6 scenarios

Stages: 1 2 3 4 5

To Evaluate the policy:

I evaluate the cost of the effective decisions

DTU Compute

24 May 2023

72 of 75

Multi-Stage SP policy: summary

72

New state revealed

Construct the non-anticipativity sets

Beginning from the new state, create scenario tree for the lookahead horizon

Solve the multi-stage �stochastic program

Implement the optimal here-and-now decision

DTU Compute

24 May 2023

73 of 75

Lead Example

73

Exercise:

Implement a multi-stage stochastic programming policy for the Energy Hub problem and compare it with the previous policies, using the evaluation environment of Week 2.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

74 of 75

Questions

74

vevox.app

176-006-553

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

75 of 75

Quiz

75

vevox.app

188-803-352

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty