1 of 76

2 of 76

Lecture 04: 2-stage Stochastic Programming

2

Scan me:

Quizzes

​

Anonymous Questions (during or after the lecture)

The Lecture will be recorded

vevox.app�105-453-184

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

3 of 76

Course Plan

3

without�Uncertainty

Today: 2-stage

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

4 of 76

Agenda for today

4

  1. Quick Recap: Deterministic Lookahead policy
  2. 2-stage Stochastic programming for 2-stage problems
  3. 2-stage Stochastic programming as a policy for Sequential Decision-Making problems
  4. Applying what we learned on the Lead Example

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

5 of 76

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 76

Markov Decision Process (MDP)

  •  

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

7 of 76

Policies: The story so far

Expected Cost

Deterministic Lookahead policy

Optimal in Hindsight

Dummy policy

Optimal Policy

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

8 of 76

Lookahead Policy

Optimal Policy:

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

9 of 76

Rolling Horizon Optimization

9

L

1 2 ... 22 23 24

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

10 of 76

10

Deterministic Lookahead Policy – General Formulation

 

 

 

Weather

Traffic

Prices

Demand for some good

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

11 of 76

11

Deterministic Lookahead Policy

 

 

 

 

Deterministic Lookahead Policy – General Formulation

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

12 of 76

Rolling Horizon Optimization

12

At each stage:

  1. Forecast uncertainties for a lookahead horizon
  2. Solve a deterministic optimization program (similar to the OiH) for the lookahead horizon

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

13 of 76

The problem with the Deterministic Lookahead

13

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

14 of 76

The problem with the Deterministic Lookahead

14

  1. The average may not correspond to any realistic trajectory
  2. Outlier trajectories affect the average disproportionately
  3. Skewed distributions are not well accounted for
  4. Cost asymmetry is not well accommodated

…which motivate a �Stochastic Lookahead

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

15 of 76

Inventory (or Dinner Party) problem

15

You are throwing a dinner party…

Time

 

 

You prepare food

Guests arrive

Follow-up action

 

…

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

16 of 76

Dinner Party problem: Optimal In Hindsight

16

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

17 of 76

Dinner Party problem: Optimal In Hindsight

17

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

18 of 76

Dinner Party problem: Deterministic Lookahead

18

 

First stage problem

Second stage problem

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

19 of 76

Dinner Party problem: Deterministic Lookahead

19

 

 

 

 

First stage problem

Second stage problem

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

20 of 76

Dinner Party problem: Deterministic Lookahead

20

 

 

 

 

 

First stage problem

Second stage problem

 

But, is this a good decision?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

21 of 76

Dinner Party problem: Deterministic Lookahead

21

 

 

 

 

First stage problem

Second stage problem

 

No, because costs are asymmetric (and maybe the uncertainty as well)

But, is this a good decision?

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

22 of 76

Dinner Party problem: Deterministic Lookahead

22

 

 

 

 

First stage problem

Second stage problem

 

No, because costs are asymmetric (and maybe the uncertainty as well)

But, is this a good decision?

Additionally, you are being naively optimistic in the first stage: you think you will do great

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

23 of 76

Dinner Party problem: Deterministic Lookahead

23

 

 

 

 

First stage problem

Second stage problem

 

No, because costs are asymmetric (and maybe the uncertainty as well)

But, is this a good decision?

Additionally, you are being naively optimistic in the first stage: you think you will do great

 

Not to be used as a prediction of the costs

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

24 of 76

Dinner Party problem: 2-stage Stochastic Program

24

 

First stage problem

Second stage problem

Depending on the uncertainty realization you get to act differently in the second stage

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

25 of 76

Dinner Party problem: 2-stage Stochastic Program

25

First stage problem

Second stage problem

Depending on the uncertainty realization you get to act differently in the second stage

And you can take that fact into account when making your first stage decisions

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

26 of 76

Dinner Party problem: 2-stage Stochastic Program

26

 

 

 

First stage problem

Second stage problem

 

 

Same as before

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

27 of 76

Dinner Party problem: 2-stage Stochastic Program

27

 

 

 

First stage problem

Second stage problem

 

 

Same as before

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

28 of 76

Dinner Party problem: first stage problem

28

 

First stage problem

 

Low Demand Scenario (D = 5)

 

Medium Demand Scenario (D = 10)

 

High Demand Scenario (D = 15)

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

29 of 76

Dinner Party problem: first stage problem

29

 

First stage problem

 

Low Demand Scenario (D = 5)

 

Medium Demand Scenario (D = 10)

 

High Demand Scenario (D = 15)

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

30 of 76

Dinner Party problem: 2-stage Stochastic Program

30

 

 

 

First stage problem

Second stage problem

 

 

Same as before

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

31 of 76

Scenario Creation

31

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

32 of 76

2-stage SP for 2-stage problems

Expected Cost

Deterministic Lookahead policy

Optimal in Hindsight

Dummy policy

Optimal Policy

2-stage SP

Value of Perfect Information

Value of �Stochastic Solution

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

33 of 76

2-stage SP for 2-stage problems

Expected Cost

Deterministic Lookahead policy

Optimal in Hindsight

Dummy policy

Optimal Policy

2-stage SP

A two-stage stochastic program with an exact expectation (infinitely many scenarios) is an optimal policy for a “truly” 2-stage problem

 

Optimal Policy:

 

Value of Perfect Information

Value of �Stochastic Solution

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

34 of 76

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

35 of 76

How many scenarios can we afford?

How many variables can we afford?

How many variables do we have?

Say 100

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

36 of 76

How many scenarios can we afford?

How many variables can we afford?

 

How many variables do we have?

Say 100

So, how many scenarios can we afford?

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

37 of 76

How many scenarios can we afford?

How many variables can we afford?

 

How many variables do we have?

Say 100

So, how many scenarios can we afford?

Around 99 / 3 = 33

 

 

So, we would like to have 100 scenarios and can afford 33. Not too bad.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

38 of 76

Dinner Party problem: More than one uncertainties

38

First stage problem

 

 

 

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

But we still can only afford 33.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

39 of 76

We need to capture the information of 10K scenarios into just 33

39

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

40 of 76

K-means Clustering

1) We generate a lot of scenarios by Monte Carlo sampling (with uniform probabilities).��2) We specify how many scenarios we can afford (here, say for example: 4).��3) We reduce the initial set of scenarios to 4 representative centroids/scenarios.��4) We assign a probability to each of the 4 final scenarios.

�

Demand

Per unit cost of ordering

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

41 of 76

K-means Clustering

Place centroids randomly

Assign each scenario to its closest centroid

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

42 of 76

K-means Clustering

Move each centroid to the “center” of its cluster

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

43 of 76

K-means Clustering

With the new centroids…�re-assign each scenario to its closest centroid

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

44 of 76

K-means Clustering

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

45 of 76

K-means Clustering

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

46 of 76

K-means Clustering

Centroids did not move 🡪 Algorithm Terminates

K-medoids is similar but using the median of each cluster instead of the mean

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

47 of 76

Scenario Reduction

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

48 of 76

K-means Clustering

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

49 of 76

K-means Clustering

Is this a deterministic algorithm?

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

50 of 76

2-stage SP: Summary

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

51 of 76

2-stage Stochastic Programming as a policy

51

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

52 of 76

The student’s problem: Deterministic Lookahead

 

Sequential Decision Problem

 

 

 

 

 

 

Same type of action at each stage

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

53 of 76

The student’s problem: 2-stage Stochastic Lookahead

 

Stochastic Lookahead Optimization (Horizon 2)

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

54 of 76

 

Stochastic Lookahead Optimization (Horizon 2)

 

 

 

 

 

Is this correct?

The student’s problem: 2-stage Stochastic Lookahead

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

55 of 76

 

Stochastic Lookahead Optimization (Horizon 2)

 

 

 

 

 

The student’s problem: 2-stage Stochastic Lookahead

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

56 of 76

Stochastic Lookahead Optimization (Horizon 2)

 

 

 

 

 

 

 

 

 

 

 

 

 

The student’s problem: 2-stage Stochastic Lookahead

Non-anticipativity constraints

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

57 of 76

2-stage Stochastic Lookahead policy:

General Formulation

57

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

58 of 76

2-stage Stochastic Lookahead Policy: General Formulation

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

59 of 76

2-stage Stochastic Lookahead: General Formulation

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

60 of 76

2-stage Stochastic Lookahead Policy

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

61 of 76

2-stage Stochastic Lookahead Policy

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

62 of 76

2-stage Stochastic Lookahead Policy

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

63 of 76

2-stage Stochastic Lookahead Policy

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

64 of 76

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

65 of 76

Lead Example

65

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

66 of 76

The Lead Example

66

 

 

 

 

 

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

67 of 76

The Deterministic Lookahead Policy for the Lead Example

  •  

67

 

Deterministic Lookahead Policy

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

68 of 76

The 2-stage Stochastic Lookahead Policy for the Lead Example

  •  

68

2-stage Stochastic Lookahead Policy

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

69 of 76

The 2-stage Stochastic Lookahead Policy for the Lead Example

  •  

69

2-stage Stochastic Lookahead Policy

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

70 of 76

The 2-stage Stochastic Lookahead Policy for the Lead Example

  •  

70

2-stage Stochastic Lookahead Policy

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

71 of 76

The 2-stage Stochastic Lookahead Policy for the Lead Example

71

2-stage Stochastic Lookahead Policy

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

72 of 76

The 2-stage Stochastic Lookahead Policy for the Lead Example

72

2-stage Stochastic Lookahead Policy

 

 

 

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

73 of 76

The 2-stage Stochastic Lookahead Policy for the Lead Example

73

 

2-stage Stochastic Lookahead Policy

 

 

 

 

 

 

 

 

 

 

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

74 of 76

The 2-stage Stochastic Lookahead Policy for the Lead Example

74

 

2-stage Stochastic Lookahead Policy

 

 

 

 

 

 

 

 

 

 

Exercise:

Implement this and compare it with the Deterministic Lookahead Policy of last week, using the evaluation environment of Week 2.

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

75 of 76

Questions

75

vevox.app�105-453-184

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty

76 of 76

Quiz

76

vevox.app

191-005-483

DTU Compute

2 February 2021

Welcome to 02435�Decision-making under uncertainty