Software tools for the investigation of stochastic programming problems

Introduction and background 
2 
Consider for instance the future prices of the stocks in a financial planning model, or the 
demand for products in a supply chain planning model: assuming these parameters as known 
with certainty will almost surely lead to such a degree of inaccuracy in the model that its 
solution may not be of any practical use to the decision maker.  
The class of problems for which the assumption of a deterministic world is relaxed is often 
referred to as optimum decision making under uncertainty.  
1.2 Uncertainty and optimisation 
The future, due to its own very nature, is often linked with uncertainty. This concept is central 
in every human activity, and decision making is no exception. When using LP or IP for 
optimum decision making, modellers are required to analyse the real problem’s data in order 
to identify the parameters which are to be considered in the model. Aggregation and 
estimation intervene in this important phase of the LP/IP modelling process. But what 
happens if the estimates are not precise or correct? In other words: what if one or more of 
the parameters are not known with certainty? 
These questions imply that the modeller needs to take into account the effects induced by 
uncertainty into the underlying optimisation models. A common approach in the 
investigation of these effects is provided by sensitivity analysis.  
Sensitivity analysis was introduced to study the robustness of the solution of LP/IP models 
when there is cause for concern regarding the accuracy of the data used. To be more precise, 
sensitivity analysis aims to determinate the manner in which the solution changes as the 
model data change. If upon perturbation of the data (which “simulates” the uncertainty 
associated with the parameters) the solution remains unchanged, then the solution is 
considered robust. Unfortunately, as shown in (Higle and Wallace 2002) this approach shows 
a number of limitations, and may provide misleading conclusions on the nature of the 
solutions. In general it is now well accepted (Wallace 1998) that sensitivity analysis is not a 
suitable approach for understanding the effects of random behaviour of the model’s 
parameters. This topic, however, is out of the scope of this thesis, and will not be discussed 
in greater detail. Readers are referred to (Higle and Wallace 2002) and (Dupacová 2002) for a 
discussion of the limitations of sensitivity analysis. 
Introduction and background 
3 
In many real world problems, the uncertainty relating to one or more parameters can be 
modelled by means of probability distributions. In essence, every uncertain parameter is 
represented by a random variable over some canonical probability space; this in turn 
quantifies the uncertainty. Stochastic Programming (SP) enables modellers to incorporate this 
quantified uncertainty into an underlying optimisation model. Stochastic Programming 
models combine the paradigm of dynamic linear programming with modelling of random 
parameters, providing optimal decisions which hedge against future uncertainties. Advances 
in hardware as well as software techniques and solution methods have made SP a viable 
optimisation tool for decision making under uncertainty. 
1.3 Brief  history of  stochastic programming 
Stochastic Programming was first introduced in the 1950’s in (Dantzig 1955), (Beale 1955) 
and (Charnes and Cooper 1959). The central question in these early works is the fact that for 
many applications of linear programming, the exact values of some of the coefficients were 
not available. Instead, the authors suggested these parameters should be replaced by random 
variables (which are also referred to as random parameters, to avoid confusion with the 
decision variables of the problems), with a known probability distribution, which is 
independent of the decision variables (Dupacová 2002). The resulting model is a linear 
program with uncertain elements, known as a Stochastic Linear Program (SLP).  
In a stochastic linear program, the realisations of the random parameters are not known at 
the time the decisions are taken. However, the actual realisations do influence the outcome 
for a given decision x (which is also subject to a set of linear constraints). The value of the 
objective function is therefore a random variable itself, and depends on the decision x and on 
the realisations of the random parameters. If the random parameters are discretely 
distributed, the model can be seen as a multiobjective linear program, where the modeller 
aims at the minimisation (or maximisation) of the expected value of the objective function. 
This is the essence of stochastic linear programming. In this context, (Charnes and Cooper 
1959) also introduced the concept of chance-constrained programming. A chance-
constrained program is a stochastic program where some of the constraints are relaxed in a 
probabilistic sense: more specifically, these constraints need to be satisfied with a finite 
likelihood which is less than 1. 
Introduction and background 
4 
Since the basic paradigm of stochastic programming was first introduced, considerable 
advances have taken place in the understanding of the theoretical properties of SP models, as 
well as in the practical use of these models for real life applications. Indeed, the ability of 
stochastic programming to provide decision makers with optimum strategies which are 
hedged against future uncertainties has made SP the leading approach in many industry 
sectors. For instance, SP models are now widely applied in supply chain management, where 
the uncertainty in the products demand, costs and supply makes it necessary to take into 
account the variability of these parameters. Examples of large scale stochastic programming 
applications in supply chain management are found in (Escudero, Galindo et al. 1999), 
(Escudero, Kamesan et al. 1993), (Eppen, Martin et al. 1989), see also (MirHassani, Lucas et 
al. 2000) and (Infanger 1994).  
Traditionally, stochastic programming has also been deployed in a number of applications of 
water resources management, see for instance (Somlyódy and Wets 1988), (Dupacová, 
Gaivoronski et al. 1991), (Watkins Jr, McKinney et al. 2000), (Escudero 2000), and power 
generation planning (Dantzig and Infanger 1997), (Pereira and Pinto 1991), (Pereira and 
Pinto 1985).  
Other application areas include environmental and agricultural planning (Gassmann 1989; 
Darby-Dowman, Barker et al. 2000), (Bosetti, Messina et al. 2002), telecommunications 
(Gaivoronski 1995), and network design management (Medova 1998). 
The field that has most benefit from the deployment of stochastic programming techniques 
is represented by the financial planning area. The importance of dynamic aspects in portfolio 
selection is widely recognized by both practitioners and modellers and stochastic 
programming models represent one of the most promising approaches for dynamic portfolio 
selection (Kusy and Ziemba 1986; Mulvey and Vladimirou 1992; Dantzig and Infanger 1993; 
King 1993; Zenios 1993; Carino and Ziemba 1998; Consigli and Dempster 1998; 
Gaivoronski and De Lange 2000). In particular, asset and liability models can be formulated 
as multistage stochastic programming models with recourse; this is an extension of the 
original stochastic programming models formulation.  
As an evidence of the growing importance of stochastic programming as a decision making 
tool, a number of research text books have appeared covering both theory and applications. 
Introduction and background 
5 
The following is a non exhaustive list of recent publications: (Ermoliev and Wets 1988; 
Infanger 1994; Kall and Wallace 1994; Prékopa 1995; Higle and Sen 1996; Birge and 
Louveaux 1997; Ziemba and Mulvey 1998; Wets and Ziemba 1999). 
1.4 Alternative stochastic programming models 
Stochastic Programming is a general term used to indicate mathematical programming 
models which explicitly incorporate uncertainty in the form of probability distributions of 
some parameters. These models can be further categorised taking into account the way in 
which such uncertainty is expressed and dealt with in the underlying linear optimisation 
model.  
The classification of stochastic programming problems introduced by (Gassmann and 
Ireland 1996), with a small extension given by the addition of the Expected Value models as 
a subclass of the distribution problems, leads to a working taxonomy shown in Figure 1. 
SP problems 
Chance 
Constrained 
Problems 
Recourse 
Problems 
Distribution 
Problems 
Scenario-
based 
Distribution-
based 
Wait and See 
Expected 
Value 
Stochastic Measures: EVPI and VSS 
 
Figure 1 Taxonomy of SP problems. 
These classes can be illustrated by first considering the linear programming problem: 
mnnm
RbRxcRAwhere
x
bAxtosubject
cxZ
∈∈∈
≥
=
=
×
;,;
min
0
 
(1) 
 
Let (Ω, ℑ, P) denote a (discrete) probability space where ),(ωξ  ω∈Ω denote the realizations 
of the uncertain parameters. Let the realizations of A, b, c for a given event ω be defined as: 
Introduction and background 
6 
()
ωω
ξωξ ),,(  cbAor =  
(2) 
 
The associated probabilities of these realizations are often denoted as .  ))((
)(ωξ
ωξ porp  For 
notational convenience these probabilities are denoted as )(ωp . The classes of stochastic 
models illustrated in Figure 1 are defined below. 
 Distribution problems 
The optimisation problems which provide the distribution of the objective function value for 
different realisations of the random parameters and also for the expected value of such 
parameters are broadly known as the distribution problems. 
The Expected Value Problem 
The Expected Value (EV) model is constructed by replacing the random parameters by their 
expected values. Such an EV model is thus a linear program, as the uncertainty is dealt with 
before it is introduced into the underlying linear optimisation model. It is common practice 
to formulate and solve the EV problem in order to gain some insight into the decision 
problem. Let the feasible regions corresponding to the problem stated in (1) and (2) be 
defined as: 
{}() ()ωξ
ω
ω
orcbAforxbAxxF ,,,| 0≥==  (3) 
 
We can reconsider (1) as an expected value or an average value problem where: 
()[] ()()


Ω∈
===
ω
ωξωωξξ pEcbA ),,(
(4) 
 
and the optimisation problem is defined as: 
{ }bxAxFx
where
xcZ
EV
=≡∈
=
|
min
 
(5) 
 
Introduction and background 
7 
Let 
*
EV
x  denote an optimal solution to the above problem. This solution can be evaluated for 
all possible realisations of the random parameters )(ωξ | Ω∈ω . The resulting objective 
function values are thus defined as: 
*
*
)()(
EVEV
xcZ ωω = (6)
 
The expected value of this distribution is called the expectation of the expected value 
solution: 
[ ]
*
)(
EVEEV
xcEZ ω= (7)
 
If for some Ω∈ω , 
ω
Fx
EV
∉
*
, that is 
*
EV
x is not feasible for some realisation )(ωξ of the 
random parameters, Z
EEV
 is set to: 
+∞→
EEV
Z  
(8) 
 
This definition, however, has certain implications regarding the usefulness of stochastic 
measures such as the Value of Stochastic Solution (VSS); this topic is revisited and fully 
discussed in Chapter 5. 
Wait and See Problems 
Wait and See (WS) problems assume that the decision-maker is somehow able to wait until 
the uncertainty is resolved before implementing the optimal decisions. This approach 
therefore relies upon perfect information about the future. Because of its very assumptions 
such solution cannot be implemented and is known as the “passive approach”. Wait and see 
models are often used to analyse the probability distribution of the objective value, and 
consist of a family of LP models, each associated with an individual scenario. The 
corresponding problem is stated as: 
ω
ωω
Fxtosubject
xcZ
∈
= )(min)(
 
(9) 
 
Introduction and background 
8 
The expected value of the wait and see solutions is defined as: 
[] ()


Ω∈
==
ω
ωωω pZZEZ
WS
)()(
 
(10)
 
 Stochastic Programming Problems with Recourse 
A simple (single stage) stochastic programming model can be formulated as follows: 
[]
Fxwhere
xcEZ
HN
∈
= )(min ω
 
(11)


Ω∈
=
ω
ω
FFand  
(12)
 
The optimal objective function value Z
HN 
denotes the minimum expected costs of the 
stochastic optimisation problem. The optimal solution x*∈F hedges against all possible 
events ω∈Ω that may occur in the future. 
Stochastic Programming Problems with recourse are dynamic LP models characterised by 
uncertain future outcomes for some parameters. The classical stochastic linear program with 
recourse makes the dynamic nature of SP explicit, by separating the model' s decision 
variables into first stage strategic decisions which are taken facing future uncertainties and 
second stage recourse (corrective) actions, taken once the uncertainty is revealed. The 
formulation of the classical two-stage SP model with recourse is as follows: 
()
,0
min
≥
=
+=
x
bAxtosubject
xQcxZ
 
 
where: 
 
() ()()[]
()() () ()
()
Ω∈
≥
+=
=
ω
ω
ωωωω
ωω
ω
                   
.0                   
min
y
xBhyDtosubject
yqExQ
 
(13)
 
Introduction and background 
9 
The matrix A and the vector b are known with certainty. The function Q(x,
 
ω) is a non-linear 
term which is referred to as the recourse function. The technology matrix B(ω), the recourse 
matrix D(ω), the right-hand side vector h(ω), and the vector of objective function coefficients 
q(ω) of this linear program may be random. For a given first stage decision x, the 
corresponding recourse actions y(ω) are obtained by solving the sub-problem associated with 
the recourse function Q(x).  
As the future unfolds in several sequential steps and subsequent recourse actions are taken, 
one deals with the generalisation of the two-stage recourse problem, known as multistage 
stochastic programming problem with recourse. A decision made in stage t should take into 
account all future realisations of the random parameters and such decision only affects the 
remaining decisions in stages t+1 … T. In Stochastic Programming this concept is known as 
non-anticipativity. The general formulation of a multistage recourse problem is set out in 
equations (14) below: 









	






	




++++=
−
TT
xxx
x
HN
xcExcExcExcZ
T
TT
min...minminmin
|...|||
21
3
23
2
2
1
332211 ξξξξξξ
 
subject to: 
TTTTTTT
bxAxAxAxA
bxAxAxA
bxAxA
bxA
=++++
=++
=+
=
...
         
       
           
332211
3333232131
2222121
1111



 
;            
ttt
ux ≤≤
  
(14)
 
where: Tt ,...,1=  represents the stages in the planning horizon and the vectors: 
[]TAAcb
tTtttt
,...,t    ),...,,( 2
1
∈∀=ξ  
(15)
 
are random vectors on a probability space (Ω, ℑ, P).  
It is important to stress the difference between decision stages and model time periods. 
Although these coincide in many applications, a stage can be regarded in general as a time 
Introduction and background 
10 
period where new information about the state of nature is provided, that is the realisation of 
the random vectors can be observed.  The term “Here and Now” is often used to refer to the 
recourse problem, reflecting the fact that decisions are taken before perfect information on 
the states of nature is revealed.  
Scenario based recourse problems 
Let us reconsider the random parameter vector ξ(ω) introduced in (2) and used in the 
definition of the given classes of models.  In the discrete statement of the problem the event 
parameter takes the range of values ω = 1,…,|Ω|; there are associated random vector 
realisations ξ(ω) and probabilities p(ω) such that: 


Ω∈ Ω∈
=Ξ=
ω ω
ωξω


)(     and       )( 1p
(16)
 
In (17), Ξ is the set of all random vectors and is often called the set of scenarios. 
For the multistage recourse problem in (14), if the probability distribution of the random 
parameter vectors is discrete, the uncertainty defines a random structure in the form of an 
event tree, which represents the possible sequence of realisations (scenarios) over the time 
horizon (see Figure 2).  In general, individual scenarios are interpreted as leaf enumeration of 
the event tree (Messina and Mitra 1997). When the event tree is explicitly given, we refer to 
the model as a scenario based recourse problem.  
ξ
2
2
k
ξ
2
2
k
ξ
T
...... ...... ...... ...... ...... ...... ...... ............
...... ...... ..........................................
... ...
... ...... ... ... ...
ξ
2
ξ
3
ξ
3
ξ
3
ξ
4
 
Figure 2. Event tree and scenarios 
In the multistage problem (scenario based), the event tree serves two purposes:  
Introduction and background 
11 
• it specifies the model of randomness (the scenario generation) and  
• it defines the algebraic model structure including hierarchal (or recursive) non 
anticipativity restrictions.   
These issues are discussed in detail in Chapter 3, section 3.2. 
Distribution based recourse problems 
An event tree can be also implied by defining the probability distributions of the random 
parameters, in which case the model is called a distribution based recourse problem. Gassmann and 
Ireland (Gassmann and Ireland 1996) expand this concept in their work. This second class of 
problems, however, introduces various difficulties in the model specification using algebraic 
modelling languages and in terms of the solution process, in particular when some of the 
random parameters are continuously distributed. An approximation can be achieved by 
adopting appropriate sampling procedures, whereby the distributions may be replaced by an 
event tree (Kall, Ruszczynski et al. 1988),(Frauendorfer 1996).  
 Chance-Constrained Problems  
Chance-Constrained Problems (CCP) (Charnes and Cooper 1959) are dynamic or static 
models where one or more constraints are probabilistic. The general formulation of a chance-
constrained problem is: 
 
{} ,..      
..
min
IihxAP
bxA
ts
cxZ
iii
CCP
1
00
=≥≥
=
=
β
 
(17)
 
where: 
]1,0[∈
i
β
  
 
is a vector of probability levels and: 
Introduction and background 
12 
IihA
iii
..   ),( 1=∀=ξ  
 
are random vectors on the probability space (Ω, ℑ, P).  
If A
i
 is a row vector, the i-th constraint is called individual chance constraint.  
If A
i
 is a cr ×  matrix with 1>r , then the i-th constraint is referred to as joint chance constraint. 
It is easily seen that chance constraints are meaningful only when the underlying algebraic 
constraint is an inequality (>= or <=) defining a closed half space.  
1.5 Stochastic measures in SP recourse problems :EVPI and VSS 
It can be shown that the three objective function values Z
EEV
, Z
HN,
 Z
WS
 are connected by the 
following ordered relationship (Birge and Louveaux 1997): 
EEVHNWS
ZZZ ≤≤ (18)
 
The inequality: 
EEVHN
ZZ ≤ (19)
 
can be argued in the following way: any feasible solution of the average value approximation 
is already considered in the Here and Now model, therefore the optimal Here and Now 
objective must be better. The difference between these two solutions defines the Value of the 
Stochastic Solution (VSS): 
HNEEV
ZZVSS −= (20)
 
This is a measure of how much can be saved by implementing the (computationally 
expensive) Here and Now solution as opposed to the deterministic expected value solution. 
The practical computation of VSS is strictly related to the approach used in the computation 
of Z
EEV 
. This topic is revisited and fully discussed in Chapter 5, section 5.4. 
Introduction and background 
13 
Another important index is represented by the Expected Value of Perfect Information (EVPI): 
WSHN
ZZEVPI −= (21)
 
This property of stochastic optimisation problems is interpreted as the expected value of the 
amount the decision maker is willing to pay to have perfect information (i.e. knowledge) 
about the future scenarios. A relatively small EVPI indicates that better forecasts will not lead 
to much improvement; a relatively large EVPI means that incomplete information about the 
future may prove costly. In (Birge and Louveaux 1997) some useful bounds on the EVPI and 
VSS are discussed: 
EVEEVEVHN
ZZZZEVPI −≤−≤≤0 (22)
EVEEV
ZZVSS −≤≤0 (23)
 
These can help in estimating the relative benefit of implementing the computationally costly 
Stochastic Programming solution, as opposed to approximate solutions obtained by 
processing the Expected Value LP problem. 
1.6 On the use of  computer tools for modelling and solving SP 
problems  
In recent years, the implementation and the solution of LP and IP models have taken 
advantage of the ever growing computational power and availability of modelling and solving 
software tools. In particular, the Algebraic Modelling Languages (AML) have played an 
important role in the acceptance of mathematical programming techniques as an aid to 
decision making. AMLs are declarative languages which enable practitioners to rapidly build 
structured and scalable optimisation models. Modern systems based on algebraic modelling 
languages support the formulation and implementation of Linear Programming (LP), Mixed 
Integer Programming (MIP), Quadratic Programming (QP), and to some extent Non-Linear 
Programming (NLP) models. These systems are readily connected to linear or non-linear 
optimisers for the solution of the models under investigation, and are able to interact with 
corporate data warehouses and data marts stored in relational, object oriented or in other 
emerging standards.  
Introduction and background 
14 
Until recently, however, the investigation of stochastic programming models could not take 
advantage of comparable tools. In fact, the practical exploitation of SP presents various 
difficulties, which affect the whole process of modelling, instantiation, solution and analysis 
of the results of SP problems.  
This thesis addresses some of the issues related to the investigation of stochastic 
programming models and is concerned more specifically with the following problems:  
• the need for a clear understanding of the mechanisms underlying the links between 
the structure of stochastic programming models and the models of randomness 
which provide the quantification of the uncertainty, and how this interaction 
intervenes in the adoption of specific solution techniques, 
• the adaptation of algebraic modelling languages for the formulation of stochastic 
programming models, and subsequent design of extended language constructs for the 
definition of the random nature of SP problems, 
• the adaptation of linear programming optimisers to the special structures which are 
inherent of stochastic programming problems, either via the use of deterministic 
equivalent forms and appropriate matrix factorisation or via the implementation of 
suitable decomposition methods, 
• the integration of scenario generators, modelling systems based on extended algebraic 
modelling languages, solution algorithms and analysis tools in a single software 
environment which supports the creation and investigation of stochastic 
programming problems. 
1.7 Outline of  the thesis 
The rest of this thesis is organised in the following way. Chapter two provides an overview of 
the software tools currently available for stochastic programming and contains a broad 
overview on the current state-of-the-art in modelling techniques for stochastic programming 
problems. The process of modelling and solving mathematical programming problems using 
algebraic modelling languages is described, and the concept of deterministic equivalent 
program is introduced. A review of language extensions which enable the definition of 
Introduction and background 
15 
stochastic programming models in a natural and concise way are also presented, together 
with a list of currently available software tools specifically designed for stochastic 
programming problems. Chapter three contains an analysis of the modelling requirements for 
stochastic programming, and considers the issues which concern the process of modelling 
and solving SP problems with the existing tools. This Chapter highlights the difficulties 
associated with the modelling of the random parameters for SP problems. Some standard 
models of randomness are defined, and the need for the seamless integration of scenario 
generators with modelling systems is discussed. The problem of representing SP models in a 
machine-readable form suitable for processing by stochastic solvers is also addressed in this 
Chapter. Taking into consideration the modelling requirements for stochastic programming, 
an approach to extending algebraic modelling languages is proposed in Chapter four. The 
extended syntax of AMPL (called SAMPL) and the corresponding language constructs are 
presented. A simple production-distribution problem is used to explain the use of the 
SAMPL constructs to formulate SP models. The approach to extending algebraic modelling 
languages is generic, and its implementation in respect of another language (MPL) is 
summarised in Appendix B. Chapter five addresses the computational issues related to the 
investigation of stochastic programming problems. The performance and scale-up properties 
of alternative algorithms for the solution of recourse problems are investigated and evaluated. 
An approach to solve scenario-based chance-constrained problems is then illustrated, 
together with the issues related to the computation of the stochastic metrics EVPI and VSS. 
The language extensions for SP modelling proposed in Chapter four and the solution 
algorithms are brought together to create a Stochastic Programming Integrated Environment 
(SPInE). The features of SPInE in terms of modelling and solving are illustrated, together 
with the framework for the analysis and simulation of stochastic programming solutions 
which is also supported by the system. Chapter six contains a case study of an environmental 
land management problem; this application is introduced to explain the use of SPInE in the 
investigation of a real life application. The results analysis features of SPInE are also 
illustrated through the use of simulation and computing the Value at Risk measure for this 
model. Conclusions and directions for further research are presented in Chapter seven.