8. Stochastic programming

Question 1

How can we deal with uncertainty?

Answer 1

• Sensitivity analysis
• What-if analysis
• Scenario analysis
• Stress tests

Question 2

Fig. example stochastic modell

Answer 2

Question 3

Stochastic programming models

Answer 3

• parameters may be uncertain
• probability distribution of random parameters is assumed to be known
• two-stage recourse model:
  1. First-stage decisions (x) to be taken before the random parameter realizes
  2. Random parameter realization (ξ(ω))
  3. Second-stage decisions (y(ω, x)) to be taken after the random parameter realization

Question 4

Fig. scenario tree (ex. 3-2-3)

Answer 4

Question 5

Fig. scenario tree (ex. 3-1-1)

Answer 5

Question 6

How to generate scenarios?

Answer 6

• Historical data
• Simulation based on a mathematical/statistical model
• Expert opinion (subjective)
• A combination of the above options

Question 7

How to generate scenarios?

Answer 7

• Historical data
• Simulation based on a mathematical/statistical model
• Expert opinion (subjective)
• A combination of the above options

Question 8

Steps to deal with uncertainty

Answer 8

1 Decision model and stochasticity
2 Scenario tree
3 SP model

Question 9

How many scenarios to consider to satisfy the stability requirement?

Answer 9

1 In-sample stability analysis
2 Out-of-sample stability analysis

Question 10

In-sample stability analysis steps

Answer 10

1 Generate K scenario trees of different types and sizes
2 Solve the SP for different scenario trees and obtain solutions x∗_k,z∗_k, k = 1, . . . ,K
3 Select the smallest scenario cardinality on which the objective function value becomes stable

Question 11

Out-of-sample stability analysis

Answer 11

evaluate how the solutions obtained through the in-sample stability analysis perform in the benchmark scenario tree
Steps:
- For each scenario tree k ∈ K:
1. Get the optimal values for the decision variables x_k obtained in tree k
2. Evaluate how this solution x_k performs in the SP with the benchmark scenario tree (it requires setting x = x*_k in SP)
- Select the smallest cardinality converging to the “true” (the one of the benchmark tree) solution

Question 12

Expected value of perfect information (EVPI)

Answer 12

measures the maximum amount a decision-maker would be ready to pay for complete information about the future
EVPI = SP − WS (WS - SP if maximization problem)

Question 13

Here-and-now solution

Answer 13

optimal objective function value of the SP

Question 14

Wait-and-see solution (WS)

Answer 14

solution we would get if we could postpone
the decision in the future
1. Solve a SP for each scenario
→ Obtain the optimal decision variables values x(ξ) and objective function values z(x(ξ), ξ))
2. Take the expected value of the optimal objective function values

Question 15

Value of stochastic solution (VSS)

Answer 15

advantage a decision-maker gets by solving a stochastic program instead of a deterministic one
VSS = EEV − SP (SP - EEV if maximization problem)

Question 16

expected result of using the EV solution (EEV)

Answer 16

measures how bad a decision based on the deterministic consideration of the parameter is
1. Solve the expected value problem (EV): replace the random variable by its expected value and solve the SP
2 Compute the EEV (impose x = x^(ξ^) in the SP)

Question 17

Relations and bounds EVPI and VSS

Answer 17

WS ≤ SP ≤ EEV (EEV ≤ SP ≤ WS if maximization problem)

Question 18

EVPI = 0 and VSS = 0

Answer 18

EEV = EV
- Optimal solutions do not depend on the value of the random parameter
- Modeling the problem as a SP has no sense

Question 19

EVPI = 0 but VSS ≠ 0

Answer 19

WS = SP
Example: for all scenarios subproblems, the same optimal solution and equal to the SP one

Question 20

EVPI ≠ 0 but VSS = 0

Answer 20

EEV = SP

Question 21

Loss of using the skeleton solution (LUSS)

Answer 21

1. Solve the EV problem (obtain first-stage variable solutions x(ξ))
2. Fix at lower bound all first-stage variables which are their lower bound in the EV solution and solve the obtained SP
   → Obtain first-stage solutions xˆ
   imposing x = ˆx in the SP and evaluating the objective of the SP
   -> LUSS = ESSV - SP

Question 22

Relations and bounds LUSS

Answer 22

For any SP:
VSS ≥ LUSS ≥ 0
SP ≤ ESSV ≤ EEV (EEV ≤ ESSV ≤ SP if maximization problem)

Question 23

LUSS = 0

Answer 23

ESSV = RP: perfect skeleton solution
condition x_j = x̄j(ξ^), j ∈ J is satisfied by the SP solution x*
even without being enforced by a constraint

Question 24

0 < LUSS < VSS

Answer 24

there may be some variables not chosen by the EV solution,
which should be selected in the SP

Question 25

LUSS = VSS

Answer 25

EEV = ESSV
The SP, when not allowed to use/change the variables in J , chooses not to change the value of any of the remaining variables (xˆ = x̄(ξ^_))

Question 26

Loss of upgrading the deterministic solution (LUDS)

Answer 26

Can the deterministic solution be upgraded to become good or optimal for the SP?
1. Solve the EV problem (obtain first-stage variable solutions x̄(ξ^))
2. Add the constraint x ≥ x̄(ξ^) to the SP and solve it
→ Obtain first-stage solutions xˇ
imposing x = ˇx in the SP and evaluating the objective in the SP
-> LUDS = EIV − SP

Question 27

Relations and bounds LUDS

Answer 27

For any SP:
VSS ≥ LUDS ≥ 0
SP ≤ EIV ≤ EEV (EEV ≤ EIV ≤ SP if maximization problem)

Question 28

LUDS = 0

Answer 28

EIV = RP: deterministic solution is perfectly upgradeable
The condition x ≥ x̄(ξ^_) is satisfied by the SP solution x* even without being enforced by constraints

Question 29

0 < LUDS < VSS

Answer 29

deterministic solution is partially upgradeable
There exists one (at least) component i ∈ {1, . . . , n} such that x*_i < x̄_i, then xˇi = x̄_i