srpchase.gms : Scenario Tree Construction Example

Description

```SCENRED2 - 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)
```

Reference

• H. Heitsch, W. Roemisch, and C. Strugarek, Stability of Multistage Stochastic Programs. SIAM Journal on Optimization 17 (2006), 511-525.

Small Model of Type : LP

Category : GAMS Model library

Main file : srpchase.gms

``````\$title Scenario Tree Construction Example (SRPCHASE,SEQ=344)

\$onText
SCENRED2 - 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 ScenRed2
\$set sr2prefix srpchase
\$libInclude scenred2

File fopts 'Scenred option file' / 'sr2%sr2prefix%.opt' /;
putClose fopts 'order           1'
/ 'section   epsilon'
/ ' 2           0.05'
/ ' 3           0.05'
/ 'end';

* Scenred2 method choice
ScenRedParms('construction_method') = 2;
ScenRedParms('reduction_method'   ) = 2;
ScenRedParms('sroption'           ) = 1;

* Scenred2 call
\$libInclude runscenred2 %sr2prefix% 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;
``````