11
1.2. Taxonomy of SP Problems
Stochastic Programming is now a well-established mathematical programming paradigm,
which explicitly incorporates 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 leads to a working taxonomy
shown in figure 1.1.
Figure 1.1 Taxonomy of SP problems.
These problem classes can be illustrated by first considering the linear programming
problem:
mnnm
RbRxcRAwhere
x
bAxtosubject
cxZ
τ
υ
;,;
0
min
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:
Ζ Ζ
[Ζ [ ),,( cbAor
The associated probabilities of these realizations are often denoted as . ))((
)( Ζ [
Ζ [ porp
For notational convenience these probabilities are denoted simply as )( Ζp .
12
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.
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.
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 a 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.
Recourse Problems.
Assuming Z are solutions of the objective functions, simple (single stage) stochastic
programming model can be formulated as follows:
∩
:
Ζ
Ζ
FFand
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.
> ≅
Fxwhere
xcEZ
HN
)(min Ζ
13
Here and Now Problems
The formulation of the classical two-stage SP model with recourse is as follows:
)(min xQcxZ
bAxtosubject
0 τx
where :
)]()([min)( Ζ ΖyqExQ
w
xBhyDtosubject )()()()( Ζ Ζ Ζ Ζ
:
τ
Ζ
Ζ 0)(y
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 decisions only affect
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 the equations below:
↵
↓
→
↑
≈
…
≡
↔
←
♠
≈
…
≡
↔
←
♠
TT
xxx
x
HN
xcExcExcExcZ
T
TT
min...minminmin
|...|||
21
3
23
2
2
1
332211 [ [ [ [ [ [
14
subject to:
TTTTTTT
bxAxAxAxA
bxAxAxA
bxAxA
bxA
...
332211
3333232131
2222121
1111
#%#
;
ttt
ux δ δA
where: Tt ,...,1 represents the stages in the planning horizon and the vectors:
> ≅TAAcb
tTtttt
,...,t ),...,,( 2
1
[
are random vectors on a probability space (Ω, , P).
Stochastic Measures
It can be shown that the three objective function values Z
EEV
, Z
HN,
Z
WS
are connected by
the following ordered relationship:
EEVHNWS
ZZZ δ δ
The inequality:
EEVHN
ZZ δ
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 value of the stochastic solution (VSS)
The difference between these two solutions defines the Value of the Stochastic Solution
(VSS) for a minimisation problem:
HNEEV
ZZVSS
15
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
.
The expected value of perfect information (EVPI)
Another important index is represented by the Expected Value of Perfect Information
(EVPI):
WSHN
ZZEVPI
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.
Bounds on EVPI and VSS
Some useful bounds on the EVPI and VSS are presented below:
EVEEVEVHN
ZZZZEVPI δ δ δ0
EVEEV
ZZVSS δ δ0
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.
16
1.3. Modelling Systems, Database and Constituents
In the different stages of the optimisation process, various constituents undertake different
roles and interact with each other. These constituents and their interaction are set out in
Figure 1.2.
Figure 1.2 Optimisation Process and Constituents
The technical experts (modelling experts, database experts, solver experts, and domain experts,
depending on their expertise) have access to all system components including the
underlying models, databases, and can change the solver strategy. The different technical
experts collaborate to create a domain-specific application by integrating the different tools
for the different stages of the process. The decision maker(s) are the constituents that utilise
the (application) system. Typically the decision makers have access to the data and solution
analysis routines available in the database, and use the underlying models and data as a
black box. These are only interested in the solution values, which are expressed in terms of
decisions. Hereafter, they analyse and report the results that are in the analytic database.
Accordingly, there is a need to have integrated optimisation tools for all the constituents
involved. These tools must be capable of providing a set of features that ideally allow the
different experts and problem owner(s) to complete the life cycle of the LP, MIP, IP, QP,
SP based optimisation application. The traditional view of a mathematical programming
based modelling and solving environment is shown in Figure 1.3.
Decision-Maker
Model
Specialist -Analyst,
Database expert
Solving Expert
Analytic Database, Solution
Analysis, Reporting:
high interaction with users
Algebraic Form Modelling,
Data Modelling:
medium interaction with users
Solution:
low Interaction with users
Domain Expert
17
Analytic
Data
Modelling
systems
Models
Solution
algorithms
End User Interface
Figure 1.3 Traditional view of an optimisation-based application
The architecture is centred on the (algebraic) modelling systems, which process one or
more algebraic models and the analytical data in order to generate a model instance. The
instance is then passed onto the solvers (which implement one or more of solution
algorithms). These optimise the model instance and return the values of the optimum
decisions and objective (decision data) to the modelling system, which in turn stores them
into the database. The components are typically controlled by a Graphical User Interface
(GUI).
18
1.4. SP Software Tools
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.
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. Recently there has been considerable progress in the
development and application of SP:
ξ The links between the structure of stochastic programming models and the models
of randomness which provide the quantification of the uncertainty and their joint
adoption for a given problem are better understood.
ξ Integrated modelling environments have been developed which combine scenario
generators, modelling systems based on extended algebraic modelling languages,
solution algorithms and analysis tools in a single software environment.
19
SP Software Tools
Name Affiliation System Name Type
JJ Bisshop, et al. Paragon Decision Tech. AIMMS Modelling System
A Meeraus, et al. GAMS GAMS Modelling System
B Kristjansson Maximal Software MPL Modelling System
R Fourer, et al. Northwestern University AMPL Modelling System
MAH Dempster, et al. Cambridge University STOCHGEN Modelling System
E Fragniere, et al. University of Geneva SETSTOCH Modelling System
A King, et al. IBM/COIN-OR OSL/SE, SMI Solver
HI Gassmann, et al. Dalhousie University MSLiP Solver
G Infanger et. Al. Stanford University DECIS Solver
P Kall, et al. University of Zürich SLP-IOR Modelling System / Solver
G Mitra, et al. Brunel University SPInE Modelling System / Solver
Table 1.1 SP Software tools
20
1.5. Algebraic Modelling Languages for LP Modelling
Models allow complex systems to be understood and their behaviour predicted within the
scope of the model, but may give incorrect descriptions and predictions for situations
outside the realm of their intended use. Modelling involves capturing the relevant
information and entities from the underlying real world problem in order to abstract a
simplified version of the problem (that is, the model). The quality of a model is a direct
consequence of the ability of the modeller in identifying such relevant information;
however, the availability of appropriate tools also plays a major role in the modelling
process.
The process of conceptualisation, formulation, solution and analysis of the results of
mathematical programming models involves several steps (see Dominguez-Ballesteros et
al., 2002), as illustrated in the following figure (Figure 1.4):
Figure 1.4 The modelling and solution process.
21
The model conceptualisation stage involves an analysis of the real world decision problem.
The available information is collected and used to understand the data and the decision-
making requirement of the application under investigation. The data modelling stage
involves the extraction and classification of the available information. The items of
information are therefore analysed and subdivided into ‘categories’. The categories
obtained by this analysis provide the sets and parameters, which are used in the algebraic
formulation of the model.
The typical mathematical programming modelling strategy enables the modeller to move
from the conceptualisation to the creation of an algebraic linear programming model. The
steps to be followed are set out below:
1) Identify the entities and their ranges, that is, the sets and dimensions that define the
categories by which the problem data is structured.
2) Define model variables, model constraints and technology coefficients (data tables) in
terms of the dimensions identified in step (1).
3) Specify the linear relationships, which connect the items introduced in step (2) in
terms of the dimensions identified in step (1). These relationships lead to the
definition of constraints.
The algebraic formulation of the model is generally implemented using an Algebraic
Modelling Language (AML), which translates the abstract modeller’s form into a
machine-readable form. The translation can be considered as model instantiation. After
supplying appropriate data, the combined model and data instance can be subsequently
processed by a suitable solver, which in turn produces the model’s results.
The algebraic models have in general, as main components, Indices, Parameters (data),
Decision variables, Constraints, and an Objective function. The relationships between
these components are illustrated in Figure 1.5.
22
Figure 1.5 Main components in an algebraic model
That is, the indices can be used in the definition of the data tables, the variables, in the
constraints, and in the objective function. In the same way, data tables, variables, and
scalars are used to compose the constraints and the objective function (See MPL Manual).
Indices
Indexes define the domains of the model, encapsulate the problem dimensions, and make
it easy to quickly adjust the problem size. Once you have defined the indexes for a model,
you can then use them to define data, variable, and constraint vectors.
Variables
The first step when formulating a model is to identify and give names to the decision
variables. Decision variables are the elements of the model that the decision maker controls
and those values determine the solution of the model.
Data Tables
When formulating small simple models it is reasonable to leave the data definitions inside
the model. As soon as you start working with multi-dimensional models, this becomes
difficult to manage, and it is necessary to move the data into separate data files. Keeping
the data separate from the model enhances the readability of the model and make the data
easier to maintain. (See also Sections 4.1, 4.2, 4.3).
23
Scalars
Scalars or Data Constants are used in the model to aid readability, and make the model
easier to maintain. They are assigned a specific value, but not defined over a specific index.
Constraints
Constraints are the real world limitations on the decision variables. A constraint restricts or
constrains the possible values, which the variable can take. An example of a constraint
could be, for example, that certain resources, such as machine capacity or manpower, are
limited.
Objective Function
The objective function is where you specify the goal you are trying to achieve. The goal can
either be to maximize or to minimize the value of the objective function. We sometimes
use the phrase that we want to optimize the model. This means we want to find the values
for the decision variables, which gives either the maximum, or the minimum value of the
objective function. In many cases, the objective function has a monetary value, for example
to maximize profit or minimize cost, although this is not always the case.
Considering models of randomness, the extensions needed to create an SP model are
explained in Section 4.4.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
