Deterministic Equivalent Linear Program

With a finite number of scenarios, two-stage stochastic linear programs like the gas company example can be modelled as large linear programming problems. This formulation is often called the deterministic equivalent linear program, or abbreviated to deterministic equivalent. (Strictly speaking a deterministic equivalent is any mathematical program that can be used to compute the optimal first-stage decision, so these will exist for continuous probability distributions as well, when one can repesent the second-stage cost in some closed form.)

For the gas company example with three scenarios, the deterministic equivalent problem has the following form.
min
c'x
+
p1 d1'y1
+
p2 d2'y2
+
p3 d3'y3
s.t.
A x
=
b
T x
+
W y1
=
h1
T x
+
W y2
=
h2
T x
+
W y3
=
h3
x,  yi
≥
0         
Here the deterministic equivalent linear program uses x for the first-stage variables (i.e. how much gas to purchase in year 1 and how much to store) and introduces a different second-period variable yi for each scenario to represent how much gas to purchase in that scenario. The gas cost for each scenario is given by di and the three blocks of constraints require that demand hi for gas is met in the second year under every scenario. The scenarios are assumed to occur with probabilities given by pi.

The NEOS server provides an online version of the gas problem: you can try different values of the data and look at the results. Alternatively, you may use the following AMPL files to solve the deterministic equivalent problem with your own LP solver.