Description
SCENRED - Scenario Tree Construction Example 3-stage stochastic purchase example problem Analytical solution: OPT = 4.167 (Optimal value) VOPI = 3.667 (Value of perfect information) H. Heitsch, W. Roemisch, and C. Strugarek Stability of Multistage Stochastic Programs SIAM Journal on Optimization 17 (2006), 511-525 Keywords: linear programming, stochastic programming, scenario tree construction Dimension (even number)
Small Model of Type : LP
Category : GAMS Model library
Main file : srpchase.gms
$title Scenario Tree Construction Example (SRPCHASE,SEQ=344)
$onText
SCENRED - Scenario Tree Construction Example
3-stage stochastic purchase example problem
Analytical solution:
OPT = 4.167 (Optimal value)
VOPI = 3.667 (Value of perfect information)
H. Heitsch, W. Roemisch, and C. Strugarek
Stability of Multistage Stochastic Programs
SIAM Journal on Optimization 17 (2006), 511-525
Keywords: linear programming, stochastic programming, scenario tree construction
$offText
* Dimension (even number)
$if not set DIM $set DIM 1000
$ifE mod(%DIM%,2)=1 $eval DIM %DIM%+1
Set
n 'nodes' / n0*n%DIM% /
t 'time periods' / t1*t3 /
stage(n,t) 'stage mapping'
ancestor(n,n) 'ancestor matrix'
leaf(n) 'leaf nodes';
* Build a fan
* Assign stage mapping and leaf nodes
stage('n0','t1') = yes;
stage( n ,'t2') = ord(n) > 1 and ord(n) <= %DIM%/2 + 1;
stage( n ,'t3') = ord(n) > %DIM%/2 + 1;
leaf(n) = stage(n,'t3');
* Build ancenstor relations to represent the fan
ancestor(n,'n0')$stage(n,'t2') = yes;
ancestor(n,n-card(leaf))$stage(n,'t3') = yes;
* Random variables (price) and probabilities
Parameter
price(n) 'node prices'
prob(n) 'node probabilities';
prob(n) = 1/card(leaf);
* First stage
price('n0') = 1;
prob('n0') = 1;
* Second stage - price is uniformly distributed in [0,1]
price(n)$stage(n,'t2') = uniform(0,1);
* Third stage - price is conditional linearly distributed
Scalar alpha, beta;
loop(stage(n,'t3'),
alpha = 1 - price(n - card(leaf));
beta = 1 - 2*price(n - card(leaf));
price(n) = uniform(0,1);
price(n)$beta = alpha/beta - sign(beta)*sqrt(sqr(alpha/beta) - price(n)/beta);
);
* Initialize ScenRed
$set srprefix srpchase
$libInclude scenred
File fopts 'Scenred option file' / 'sr2%srprefix%.opt' /;
putClose fopts 'order 1'
/ 'section epsilon'
/ ' 2 0.05'
/ ' 3 0.05'
/ 'end';
* Scenred method choice
ScenRedParms('construction_method') = 2;
ScenRedParms('reduction_method' ) = 2;
ScenRedParms('sroption' ) = 1;
* Scenred call
$libInclude scenred %srprefix% tree_con n ancestor prob ancestor prob price
Variable
x(n) 'amount of purchase'
y(n) 'slack variable'
cost 'objective value';
Positive Variable x, y;
Equation
objective 'expected cost'
slack(n) 'slack equation'
demand(n) 'demand inequality';
Set srn(n) 'subset of nodes after tree construction';
srn(n) = prob(n);
objective.. cost =e= sum(srn, prob(srn)*price(srn)*x(srn));
slack(srn)$(not leaf(srn)).. y(srn) =e= x(srn) + sum(ancestor(srn,n), y(n));
demand(leaf(srn)).. x(srn) + sum(ancestor(srn,n), y(n)) =g= 1;
Model purchase / all /;
solve purchase minimizing cost using lp;