Stochastic Linear Programming - Multiple Randomness

GAMS
1

Hi Experts,

I am new to Stochastic Programming in GAMS, so sorry if this question is dumb.

I have one small and simple linear programming problem with 16 variables and 9 constraints. Three of the 9 constraints have their right hand side parameters random, which are also obeying a discrete distribution. Then I modeled this problem and used the following codes trying to solve them.

File emp / '%emp.info%' /;
put emp '* problem %gams.i%'/;
$onput
randvar d1 discrete 0.00005 0.5 0.00125 1.0 0.02150 2.5 0.28570 3.5 0.38300 5.0 0.28570 6.5 0.02150 7.5 0.00125 9.0 0.00005 9.5
randvar d2 discrete 0.00130 0.0 0.02150 1.5 0.28570 2.5 0.38300 4.0 0.28570 5.5 0.02150 6.5 0.00125 8.0 0.00005 8.5
randvar d2 discrete 0.00130 0.0 0.02150 0.5 0.28570 1.5 0.38300 3.0 0.28570 4.5 0.02150 5.5 0.00125 7.0 0.00005 7.5

$offput
putclose emp;

Set scen           "scenarios" / s1*s576 /;
Parameter
     s_d1(scen)     "demand realization by scenario"
     s_d2(scen)     "demand realization by scenario"
     s_d3(scen)     "demand realization by scenario";

Set dict / scen .scenario.''
           d1    .randvar .s_d1
           d2    .randvar .s_d2
           d3    .randvar .s_d3
/;

solve prob minimizing obj use EMP scenario dict;

The codes are nothing new. I just copied and pasted the two-stage SP problem codes in the documentation. Then I ran the codes and found that it returned no solution, saying that “Random variable d3_var in stage 1 with fixed value 3” and “Stage 1 RV [d1] with more than one realization”, “cannot build regular tree from random variables”.

Actually I thought my problem is a one-stage problem so I did not define stages. And I also defined d1, d2, d3 as scalars giving them values as 5, 4 and 3 at the beginning of the model.

Thank you for any suggestion for this issue!

Gabriel

2

If it is needed, the model detail is as follows. Nothing but a simple linear programming problem.

Positive Variables
         a1
         a2
         a3
         a4
         e1d1
         e1d2
         e1d3
         e2d1
         e2d2
         e2d3
         e3d1
         e3d2
         e3d3
         e4d1
         e4d2
         e4d3
         p1
         p2
         p3
         p4;

Scalars
         d1   /5/
         d2   /4/
         d3   /3/  ;

Free Variable
         obj;

Equations
         objj
         mxdemd
         budget
         capeq1
         capeq2
         capeq3
         capeq4
         dnode1
         dnode2
         dnode3;

objj..           obj =e= 10 * a1 + 7 * a2 + 16 * a3 + 6 * a4
                         + 40 * e1d1 + 24 * e1d2 + 4 * e1d3 + 45 * e2d1 + 27 * e2d2 + 4.5 * e2d3
                         + 32 * e3d1 + 19.2 * e3d2 + 3.2 * e3d3 + 55 * e4d1 + 33 * e4d2 + 5.5 * e4d3
                         + 1000 * p1 + 1000 * p2 + 1000 * p3 + 1000 * p4;
mxdemd..         a1 + a2 + a3 + a4 =g= 15;
budget..         10 * a1 + 7 * a2 + 16 * a3 + 6 * a4 =l= 220;
capeq1..         - a1 + e1d1 + e1d2 + e1d3 - p1 =l= 0;
capeq2..         - a2 + e2d1 + e2d2 + e2d3 - p2 =l= 0;
capeq3..         - a3 + e3d1 + e3d2 + e3d3 - p3 =l= 0;
capeq4..         - a4 + e4d1 + e4d2 + e4d3 - p4 =l= 0;
dnode1..         e1d1 + e2d1 + e3d1 + e4d1 =g= d1;
dnode2..         e1d2 + e2d2 + e3d2 + e4d2 =g= d2;
dnode3..         e1d3 + e2d3 + e3d3 + e4d3 =g= d3;
[\code]
Thanks!
3

Gabriel,

There are two problems which I found in your model:

The first one is an easy one, probably just a typo: In the emp.info file you defined “randvar d2 …” twice. I guess the second one should actually be “randvar d3 …”.

The second problems seems to be deeper: You say that your model should be a 1-stage model. However, in the way GAMS looks at SP problems, there cannot be uncertainty in stage 1 (if we ignore chance constraints for now). So it is not really clear to me, how you want to model uncertainty here in stage 1? Maybe you can also find some useful information here: https://www.gams.com/latest/docs/UG_EMP_SP.html

Best regards,
Lutz

4

Thank you so much Lutz. I have solved this problem by using just a deterministic equivalent form, since it just involves a simple LP and discrete uncertainty. But still I have some questions regarding GAMS’ Stochastic Programming (SP). Let me reply your answer first.

  1. Yeah that is a typo…sorry for that…
  2. I managed to make it a 2-stage problem in the end, and used deterministic equivalent form (just probability multiply with discrete scenarios) to solve it.

Now my question is, what actually does GAMS EMS solver solve, a mean-value problem? a deterministic equivalent problem? a wait-and-see problem? I am not really sure how EMS dictionary solve, especially for continuous distribution. Does EMS do sampling automatically if I call a dictionary to deal with a continuous-distributed uncertainty without identifying the sampling information? I can hardly find information in the SP documentation of GAMS about it.

Thank you!

5

Hi,

First, EMP is not a solver itself, it is a model class. This class can be solved by three different Solvers which are part of GAMS: DE, DECIS and LINDO. Note that dependent on the solver selected limitations what can be solved might apply (see https://www.gams.com/latest/docs/UG_EMP_EMPKeywords.html#UG_EMP_EMPKeywords_SP).

In general you can select, if you want to optimize the expected value problem (default), value at risk or conditional value at risk.

DE is basically a reformulation tool. It automatically formulates the deterministic equivalent of your problem and calls another solver to solve this.

DECIS employs Benders decomposition and advanced Monte Carlo sampling techniques.

These two solvers cannot deal with continuous distribution functions directly and need additional sampling information.

LINDO in contrast does the sampling on its own if needed (but gives the users some options to influence the sampling). I has different ways to solve the problem, e.g. deterministic equivalent and Benders decomposition, which can be triggered through options.

More info about these solvers can be found in the solvers manual:

I hope that helps,
Lutz

6

It does help a lot! Thank you so much!