The SMPS format for stochastic linear programs

<![if !supportEmptyParas]> <![endif]>

Last modified 08 April 2003.

<![if !supportEmptyParas]> <![endif]>

H.I. Gassmann,

School of Business Administration

Dalhousie University

Halifax, Canada B3H 3J5

<![if !supportEmptyParas]> <![endif]>

<![if !supportEmptyParas]> <![endif]>

This site explains the complete SMPS format used to describe stochastic linear programs. The format is based on the well-known MPS format for deterministic linear programs and derives from previous work by Edwards et al<![if !supportNestedAnchors]><![endif]>., Birge et al., and Gassmann and Schweitzer.

<![if !supportEmptyParas]> <![endif]>

Examples of stochastic programs are given elsewhere. (See, for instance, the books by Birge and Louveaux and Kall and Wallace.)

<![if !supportEmptyParas]> <![endif]>

Please send comments and feedback to the author.

Contents

<![if !supportEmptyParas]> <![endif]>

Design philosophy

Core file

Core file sections: NAME, ROWS, COLUMNS, RHS, RANGES, BOUNDS

Fine points: MPS record format, Network format, Mixed LP and networks, Integer variables, Quadratic objectives, Probabilistic objectives, Quantile objectives

Time file

Time file sections: TIME, PERIODS, ROWS, COLUMNS

Fine points: Implicitly named columns

Stoch file

Stoch file sections: STOCH, SIMPLE, ROBUST, PLINQUAD, CHANCE, ICC, SCENARIOS, NODES, INDEP, BLOCKS, DISTRIB

Fine points: Linking constraints

Order of processing

Solver capabilities and error recovery

References

<![if !supportEmptyParas]> <![endif]>

Design philosophy

<![if !supportEmptyParas]> <![endif]>

The SMPS format was designed to make it easy to convert existing deterministic linear programs into stochastic ones by adding information about the dynamic and stochastic structure. This is done using three text files, the core file, time file and stochastics file (or stoch file, for short). Each file consists of several sections, which must appear in predefined order. The first record of each section is a header record, which is followed by zero or more data records. Empty sections (containing no data) may be omitted. The records in each file are organized into fields according to the MPS record layout.

<![if !supportEmptyParas]> <![endif]>

Core file

<![if !supportEmptyParas]> <![endif]>

The core file lists all the deterministic information of the problem, in either MPS format for linear programs or in NETGEN format for problems in network format. Core file information includes the name and type of each constraint, the names of rows and columns, a column-ordered list of coefficients in the constraint matrix, right-hand side coefficients and any bounds and ranges on the variables and slacks. The core file also provides placeholders for all the stochastic elements (which must be mentioned in the core file and given a preliminary value that may or may not be meaningful). The core file thus represents a deterministic problem, which may be thought of as a typical scenario, an average case, a baseline case or similar.

<![if !supportEmptyParas]> <![endif]>

Sections in the core file

<![if !supportEmptyParas]> <![endif]>

Section	Purpose
NAME	Gives a name to the problem in name field 2
ROWS	Gives the name and type of each constraint and objective
COLS	Gives the nonzero coefficients in column order
RHS	For non-zero entries of the right-hand side vector (optional)
RANGES	For range constraints (optional)
BOUNDS	For bounds on decision variables. Different codes identify different types of bounds (optional)
ENDATA	End of problem data

<![if !supportEmptyParas]> <![endif]>

The small print:

<![if !supportEmptyParas]> <![endif]>

Integer variables

Network format and mixed LP-network

Quadratic objectives

Probabilistic objectives

Quantile objectives

<![if !supportEmptyParas]> <![endif]>

NAME section

<![if !supportEmptyParas]> <![endif]>

The name of the problem is given in the second name field. This name is verified against the name in the time and stoch files.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789

NAME Example

<![if !supportEmptyParas]> <![endif]>

ROWS Section

<![if !supportEmptyParas]> <![endif]>

The type of each row is given in the code field (‘L’ indicates that the constraint is of the form _{<![if !vml]><![endif]>}, ‘U’ is for constraints of the form _{<![if !vml]><![endif]>}, ‘E’ is for equality constraints, ‘N’ indicates a free row (no constraint) or potential objective row. By default the first ‘N’-type row is used as the objective. Each row is given a name in the first name field.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789

ROWS

N OBJECT

G ROW2

<![if !supportEmptyParas]> <![endif]>

COLUMNS section

<![if !supportEmptyParas]> <![endif]>

The nonzero coefficients of the constraint matrix are given in column order. The code field is empty. The first name field contains the name of the column, the second name field must match the name of a row, and the first numeric field gives the value of the corresponding coefficient in the constraint matrix. A second coefficient may appear on the same record using the third name field for the name of another row and the second numeric field for the corresponding coefficient.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

COLS

COL1 ROW2 2.0 OBJECT 100.

<![if !supportEmptyParas]> <![endif]>

RHS section

<![if !supportEmptyParas]> <![endif]>

The first name field on a data record contains an identifying name (that must match information given externally), the second name field contains the name of a constraint mentioned in the ROWS section. The first numeric field contains the value of the right-hand side in this constraint. The third name field and second numeric field may contain the information corresponding to one further constraint. Only nonzero right-hand side values require an entry in this section, and the order does not matter.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789

RHS

RHS1 ROW2 50.

<![if !supportEmptyParas]> <![endif]>

RANGES section

<![if !supportEmptyParas]> <![endif]>

The RANGES section allows the user to set up constraints that act as both L and G-type constraints. The first name field on a data record contains an identifying name (that must match information given externally), the second name field contains the name of a constraint mentioned in the ROWS section. The first numeric field contains a range for the value of the right-hand side in this constraint. The third name field and second numeric field may contain the information corresponding to one further constraint. The order of constraints does not matter.

<![if !supportEmptyParas]> <![endif]>

Assume that the right-hand side value for the row is b_i and the entry in the ranges section is r_i. Then the action of the range command is as follows:

<![if !supportEmptyParas]> <![endif]>

Row type	<![if !supportEmptyParas]> <![endif]>	Effect	<![if !supportEmptyParas]> <![endif]>	<![if !supportEmptyParas]> <![endif]>
G	_{<![if !vml]><![endif]>}	_{<![if !vml]><![endif]>}	_{<![if !vml]><![endif]>}	<![if !supportEmptyParas]> <![endif]>
L	_{<![if !vml]><![endif]>}	_{<![if !vml]><![endif]>}	_{<![if !vml]><![endif]>}	<![if !supportEmptyParas]> <![endif]>
E	_{<![if !vml]><![endif]>}	_{<![if !vml]><![endif]>}	_{<![if !vml]><![endif]>}	if r_i > 0
E	_{<![if !vml]><![endif]>}	_{<![if !vml]><![endif]>}	_{<![if !vml]><![endif]>}	if r_i < 0

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789

RANGES

RANGE1 ROW2 10.

<![if !supportEmptyParas]> <![endif]>

If ROW2 is a G-type row with previously defined right-hand side 50, then this declaration defines a range of [50,60].

<![if !supportEmptyParas]> <![endif]>

BOUNDS section

<![if !supportEmptyParas]> <![endif]>

The first name field on a data record contains an identifying name (that must match information given externally), the second name field contains the name of a variable mentioned in the COLUMNS section. The first numeric field contains a value associated with this bound. The type of bound is clarified in the code field. The third name field and second numeric field are not used. The order of the columns does not matter.

<![if !supportEmptyParas]> <![endif]>

Code	Interpretation
LO	Lower bound
UP	Upper bound
FX	Fixed value
FR	Free variable
MI	Nonpositive variable. (Lower bound is _{<![if !vml]><![endif]>})
PL	Nonnegative variable (Upper bound is _{<![if !vml]><![endif]>})
BV	Binary variable (0-1 variable)
UI	Upper bound. If the variable was declared as integer in the COLUMNS section, the upper bound is rounded down to the nearest integer.

<![if !supportEmptyParas]> <![endif]>

If the code field contains the values FX, MI, PL or BV, the value in the first numeric field is ignored. Default bounds are 0 and _{<![if !vml]><![endif]>} for continuous variables and 0 and 1 for integer variables.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789

BOUNDS

UP BOUND1 COL1 20.

<![if !supportEmptyParas]> <![endif]>

This example defines an explicit upper bound of 20 for decision variable COL1.

<![if !supportEmptyParas]> <![endif]>

MPS record layout

<![if !supportEmptyParas]> <![endif]>

One must distinguish between header records and data records.

<![if !supportEmptyParas]> <![endif]>

Header records contain up to three name fields, normally in these positions:

<![if !supportEmptyParas]> <![endif]>

columns 1–14	first word field
columns 15–24	second word field
columns 40–49	third word field

<![if !supportEmptyParas]> <![endif]>

Data records contain up to three name fields, two numeric fields and a code field, normally in these positions:

<![if !supportEmptyParas]> <![endif]>

columns 2 and 3	code field
columns 5–12	first name field
columns 15–22	second name field
columns 25–36	first numeric field
columns 40–47	third name field
columns 50–61	second numeric field

<![if !supportEmptyParas]> <![endif]>

Names are normally restricted to eight characters and may contain any ASCII symbol; numerical input is limited to twelve characters (including digits, signs, exponents and a decimal point). Free format input can be used if these limits are too restrictive. However, in order to allow for correct parsing of data records, some fairly non-restrictive rules must be followed:

<![if !supportEmptyParas]> <![endif]>

Each field is surrounded by white space (one or more blanks) and does not contain an embedded blank.:
The first name field of a header record must start in column 1.
Names and numeric information on data records start in column 5 (or further to the right). The first four columns must be reserved for the code field (which is to be placed into columns 2 and 3).
Numbers (numerical strings) must start with a digit (or a decimal point immediately followed by a digit). Exponential notation (e.g., 1.E–5 or .3e+6) is allowed.
Names (character strings) have no embedded blanks and must start with a non-numeric character. (‘plus2’, ‘an_extremely_long_and_tedious_name’, ‘.cost’ and ‘$1000’ are all valid names, but ‘sp ace’, ‘2B’ and ‘.5off’ are not.)

<![if !supportEmptyParas]> <![endif]>

Network format

<![if !supportEmptyParas]> <![endif]>

The format used for network sections is modified somewhat from the proposal by Klingman et al. As in the MPS format there are header records and data records. The data records are organized in the following manner:

<![if !supportEmptyParas]> <![endif]>

Data record for networks

<![if !supportEmptyParas]> <![endif]>

columns 2–4	code field
columns 7–12	first name field (from-node)
columns 13–18	second name field (to-node)
columns 21–30	first numeric field (unit flow cost)
columns 31–40	second numeric field (optional: maximum flow)
columns 41–50	third numeric field (optional: minimum flow)
columns 51–60	fourth numeric field (optional: multiplier)
columns 63–70	third name field (optional: see below)

<![if !supportEmptyParas]> <![endif]>

Note that in this format the name fields are only six characters wide and the numeric fields hold ten characters each.

<![if !supportEmptyParas]> <![endif]>

The following modifications to the NETGEN format are made in SMPS: For consistency, the BEGIN record is changed to a NAME record, and the END record is replaced by ENDATA. More importantly, since arcs are named only implicitly, it is important that each node is associated unequivocally with its time period. This requires a separate NODES section, which follows the same rules as the ROWS section. The two sections can be used interchangeably.

<![if !supportEmptyParas]> <![endif]>

Even this is not enough to ensure that implicitly named arcs are assigned to the correct time period. The convention is that an arc belongs to the earlier of the periods containing the origin and destination nodes, unless otherwise specified. This convention can be overridden by placing the name of the period to which the arc belongs into the third name field.

<![if !supportEmptyParas]> <![endif]>

Core file sections for networks

<![if !supportEmptyParas]> <![endif]>

Section	Purpose
NAME	Gives a name to the problem in name field 2
NODES	Gives the name of each node
ARCS	Specifies the cost, flow limits and multiplier of each arc
SUPPLY	Gives supply at each supply node
DEMAND	Gives demand at each demand node
ENDATA	End of problem data

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

NAME Network format

ARCS

NODE1 NODE2 cost upper lower multiplier

1 NODE1 NODE3 cost upper lower multiplier

2 NODE1 NODE3 cost upper lower multiplier

...

NODEk NODEn cost upper lower multiplier

SUPPLY

...

NODE1 amount

DEMAND

...

ENDATA

<![if !supportEmptyParas]> <![endif]>

Note the two parallel arcs connecting node1 and node3.

<![if !supportEmptyParas]> <![endif]>

Mixed LP and network problems

<![if !supportEmptyParas]> <![endif]>

Network and LP sections can be mixed. It might be useful, for example to set up a two-stage problem in which the first stage is an LP model concerned with facility location and capacity planning, while the second stage is a network flow problem that allocates random demands once the facilities have been opened. Another example is a network with side constraints, which can easily arise in financial applications.

<![if !supportEmptyParas]> <![endif]>

Mixed LP and network problems use all the sections described previously under LP and network problems. The following sections serve the same purpose and may be alternated freely:

<![if !supportEmptyParas]> <![endif]>

ROWS and NODES sections,

COLUMNS and ARCS sections,

SUPPLY, DEMAND and RHS sections.

<![if !supportEmptyParas]> <![endif]>

The general order of sections of mixed LP and network problems is as follows:

<![if !supportEmptyParas]> <![endif]>

Section	Purpose
NAME	Gives a name to the problem in name field 2
ROWS	Give the name of each row/node.
NODES	Give the name of each row/node.
COLUMNS	Give the name of each variable/arc. ARCS sections also specify cost coefficients and variable bounds.
ARCS
RHS	<![if !supportEmptyParas]> <![endif]> Give right-hand side values for the constraints
SUPPLY
DEMAND
RANGES	(optional)
BOUNDS	(optional)
ENDATA	End of problem data

<![if !supportEmptyParas]> <![endif]>

The remaining challenge is to specify constraint coefficients to the various constraints. In mixed LP and networks problems, one has to be prepared to deal with four distinct situations:

<![if !supportEmptyParas]> <![endif]>

LP columns and constraint coefficients in LP rows	This is easily handled with an MPS-style data record
LP columns that bring flow to a network node.	The only difficulty here is that nodes are not named in a separate ROWS section
Network arcs in node constraints	This is easily handled in a NETGEN-style data record.
Network arcs in LP constraints	This is the most difficult situation and requires careful attention.

<![if !supportEmptyParas]> <![endif]>

The challenge with network arcs appearing in LP constraints is that arcs are not named explicitly, so that three name fields are needed (two for the two nodes incident to the arc and a third for the constraint row), whereas the original NETGEN standard allows only two.

<![if !supportEmptyParas]> <![endif]>

The SMPS format extends the NETGEN data record by allowing a third name field to be placed in columns 63–70. If not empty, the third name field refers to an LP row name, and the first numeric field is taken as the coefficient value. There should be no further numerical data on such records. If the third name field is empty, the record is a regular NETGEN data record.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

Time file:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

TIME Mixed LP and network example

PERIODS

COL1 ROW1 PERIOD1

COL6 ROW3 PERIOD2

'NETWRK' NODE1 PERIOD3

'NETWRK' NODE3 PERIOD4

COL18 ROW5 PERIOD5

ENDATA

<![if !supportEmptyParas]> <![endif]>

Core file

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

NAME Mixed LP and network example

ROWS

...

E ROW3

E ROW4

L NODE1

G NODE2

E ROW5

E ROW6

...

COLUMNS

...

COL16 ROW3 value NODE1 value

COL17 ROW4 value NODE2 value

ARCS

NODE1 NODE2 cost upper lower multiplier

NODE1 NODE7 cost upper lower multiplier

...

NODE8 ROW5 cost upper lower multiplier

NODE8 ROW6 cost upper lower multiplier

COLUMNS

COL18 ROW5 value ROW7 value

COL19 ROW6 value ROW8 value

...

RHS

...

SUPPLY

...

ENDATA

<![if !supportEmptyParas]> <![endif]>

The first COLUMNS section lists the deterministic coefficients of the constraint matrices belonging to periods 1 and 2. Two entries of this last matrix are illustrated in the last two data records in this section. These entries will take values from the second to the third stage. The amount will be determined by the values of COL16 and COL17 and the corresponding entries in this COLUMNS section.

<![if !supportEmptyParas]> <![endif]>

The last two entries in the ARCS section will bring “flow” from NODE8 to the right hand side of ROW5 and ROW6 by entering a number in those rows. The number will be the “multiplier” from the input, and the value ending up on the right hand side will be the product of this multiplier and the flow running out of NODE8 to these rows (which are nodes when viewed from the network).

<![if !supportEmptyParas]> <![endif]>

Integer variables

<![if !supportEmptyParas]> <![endif]>

Integer variables can be handled in the same way as in MPS: Special data records called indicator records are inserted before the start of a group of integer variables and again at the end. These data records define the type of integer variables used through special markers in the name fields.

<![if !supportEmptyParas]> <![endif]>

For general integer variables, the code field of the starting indicator record should be empty, the second name field should contain the marker ‘MARKER’, and the third name field should contain the marker ‘INTORG’. The first name field may contain any value that differs from the name of the previous column. The ending indicator record is identical to the opening indicator, except that the third name field contains the marker ‘INTEND’.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789 123456789

INT ‘MARKER’ ‘INTORG’

Col1 Row1 1.0 Row2 -1.0

Col2 Row1 -1.0 Row3 1.0

INT ‘MARKER’ ‘INTEND’

<![if !supportEmptyParas]> <![endif]>

This example sets up two integer columns, Col1 and Col2.

<![if !supportEmptyParas]> <![endif]>

Special ordered sets can be used to further restrict the possible values of a set of integer variables. At most one of the variables in a special ordered set of type 1 may take a nonzero value. In a special ordered set of type 2 at most two variables may take nonzero values, and they must be adjacent within the set. Special ordered sets of type 3 are used to model decisions, as they force all of the integer variables in the set to be 0-1 variables.

<![if !supportEmptyParas]> <![endif]>

Special ordered sets of type 1 are denoted by the following indicator records: The starting indicator record contains a code value of S1, an arbitrary name in the first name field, the keyword ‘MARKER’ in the second name field and the keyword ‘SOSORG’ in the third name field. The ending indicator record is similar, but it contains the keyword ‘SOSEND’ in the third name field.

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789 123456789

S1 INT1 ‘MARKER’ ‘SOSORG’

Col1 Row1 1.0 Row2 -1.0

Col2 Row1 -1.0 Row3 1.0

S1 INT1 ‘MARKER’ ‘SOSEND’

<![if !supportEmptyParas]> <![endif]>

In this example the two integer columns Col1 and Col2 form a special ordered set of type 1.

<![if !supportEmptyParas]> <![endif]>

Special ordered sets of type 3

<![if !supportEmptyParas]> <![endif]>

Special ordered sets of type 3 are useful in the following situation:

<![if !supportEmptyParas]> <![endif]>

<![if !supportLists]>1. <![endif]>There exists an equality constraint whose right-hand side is 1.

<![if !supportLists]>2. <![endif]>The coefficients of all variables in this row are either 0 or 1.

<![if !supportLists]>3. <![endif]>The variables whose coefficients are non-zero are integer variables.

<![if !supportLists]>4. <![endif]>At most one of these integer variables can be non-zero.

<![if !supportEmptyParas]> <![endif]>

In this case it can be deduced that exactly one of the integer variables takes a value of 1, and that all of them are 0-1 variables. These variables form a special ordered set of type 3. Special ordered sets of type 3 are declared in SMPS by a construct similar to other special ordered sets. The starting indicator record has an empty code field and the name of a valid equality row in the first name field. The second name field contains the keyword ‘MARKER”, and the third name field contains the keyword ‘SOSORG’. In the ending indicator record, the keyword ‘SOSEND’ replaces the keyword ‘SOSORG’.

<![if !supportEmptyParas]> <![endif]>

Example:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

Row3 ‘MARKER’ ‘SOSORG’

Col1 Row1 1.0 Row3 1.0

Col2 Row1 1.0 Row3 1.0

Row3 ‘MARKER’ ‘SOSEND’

<![if !supportEmptyParas]> <![endif]>

Quadratic objectives

<![if !supportEmptyParas]> <![endif]>

A quadratic objective can be set up following the linear part of the core file. It uses the following sections:

<![if !supportEmptyParas]> <![endif]>

Section	Purpose
NAME	Gives a name to the problem in name field 2
QSECTION	Gives the nonzero coefficients in the quadratic objective
ENDATA	End of problem data

<![if !supportEmptyParas]> <![endif]>

The NAME section gives a name in the second name field. This name must match the name given in the linear portion of the core file. The second name field in the QSECTION header record contains no information. The first two name fields on a data record contain the column names of a quadratic term, the first name field contains the coefficient. A common factor of ½ is assumed throughout.

<![if !supportEmptyParas]> <![endif]>

The QSECTION can be read from a separate file if necessary.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789

NAME Example

QSECTION

Col1 Col1 1.0

Col1 Col2 3.0

Col2 Col2 2.0

ENDATA

<![if !supportEmptyParas]> <![endif]>

sets up the objective 0.5*(Col1)² + 1.5*Col1*Col2 + (Col2)².

<![if !supportEmptyParas]> <![endif]>

Probabilistic objectives

<![if !supportEmptyParas]> <![endif]>

Probabilistic objectives take the form

<![if !supportEmptyParas]> <![endif]>

_{<![if !vml]><![endif]>}

<![if !supportEmptyParas]> <![endif]>

where the optimization could be either minimization or maximization and the relation ~ could be ³, £ or =.

<![if !supportEmptyParas]> <![endif]>

This is very similar to a single chance constraint, and thus it can be represented in SMPS format in the same way. If ROW1 is the objective row specified in the core file, then the following example defines a probabilistic objective:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789

CHANCE INDIV

N CC1 ROW1

<![if !supportEmptyParas]> <![endif]>

The numeric fields are not used.

<![if !supportEmptyParas]> <![endif]>

Quantile objectives

<![if !supportEmptyParas]> <![endif]>

Quantile objectives take the form

<![if !supportEmptyParas]> <![endif]>

_{<![if !vml]><![endif]>}.

<![if !supportEmptyParas]> <![endif]>

This is the same as optimizing c subject to the simple chance constraint _{<![if !vml]><![endif]>} along with the other constraints of the problem.

<![if !supportEmptyParas]> <![endif]>

The time file

<![if !supportEmptyParas]> <![endif]>

Purpose of the time file is to allow breaking down the core file scenario into nodes corresponding to the individual stages.

<![if !supportEmptyParas]> <![endif]>

Sections in the time file

<![if !supportEmptyParas]> <![endif]>

Section	Purpose
TIME	Gives a name to the problem in name field 2
PERIODS	Gives the name of each time period (in order)
ROWS	(optional) Specifies for each row the period to which it belongs
COLUMNS	(optional) Specifies for each column the period to which it belongs
ENDATA	End of problem data

<![if !supportEmptyParas]> <![endif]>

The small print

<![if !supportEmptyParas]> <![endif]>

Implicitly named columns

Stages

<![if !supportEmptyParas]> <![endif]>

TIME section

<![if !supportEmptyParas]> <![endif]>

The second name field on the TIME header record contains the name of the problem. This name is verified against the name in the core and stoch files.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789

TIME Example

<![if !supportEmptyParas]> <![endif]>

PERIODS section

<![if !supportEmptyParas]> <![endif]>

The header record contains the value PERIODS in the first name field. If the core file is in time order, then the second name field can be left blank or given the value IMPLICIT. The ROWS and COLUMNS sections are not needed in this case.

<![if !supportEmptyParas]> <![endif]>

If the core file is not given in temporal order (for instance if it was generated by an algebraic modelling language), then the keyword EXPLICIT must be placed in the second name field of the header record and the ROWS and COLUMNS sections must be present.

<![if !supportEmptyParas]> <![endif]>

Each data record contains the name of a period in the third name field. If the time file is in implicit format, then the first name field contains the name of the first column in this period, the second name field contains the name of the first row. If the time file is in explicit format, the first two name fields are not used. The objective row must always belong to the first period.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

PERIODS IMPLICIT

COL1 ROW1 PER1

COL5 ROW3 PER2

<![if !supportEmptyParas]> <![endif]>

In this example all columns in the core file that appear between COL1 (inclusive) and COL5 (exclusive) make up the first period, named PER1, while COL5 and all the remaining columns belong to period PER2. Similarly, ROW1 and ROW2 (along with the objective) are the rows belonging to the first period; all the others are second-period rows.

<![if !supportEmptyParas]> <![endif]>

ROWS section

<![if !supportEmptyParas]> <![endif]>

The data records in this section contain the name of a row mentioned in the core file in the first name field; the second name field contains the name of a time period set up in the preceding PERIODS section. The ROWS section is optional if the core file is given in temporal order.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789

ROWS

ROW1 PER1

ROW3 PER2

ROW2 PER1

...

<![if !supportEmptyParas]> <![endif]>

COLUMNS section

<![if !supportEmptyParas]> <![endif]>

The data records in this section contain the name of a column mentioned in the core file in the first name field; the second name field contains the name of a time period set up in the preceding PERIODS section. The COLUMNS section is optional if the core file is given in temporal order.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789

COLS

COL1 PER1

COL5 PER2

COL2 PER1

...

<![if !supportEmptyParas]> <![endif]>

Implicitly named columns

<![if !supportEmptyParas]> <![endif]>

If the core file is given in temporal order and the time file only provides markers for the first row and column of each period, then there exists a problem with columns that do not have explicit names given in the core file. This situation can arise in two circumstances: if the core file has network components, or if there are penalties (linear, quadratic or mixed) for violating a constraint. In the first instance, the first name field of a data record in the PERIODS section should contain the marker ‘NETWRK’, in the second instance it should contain the marker ‘PENLTY’. For an example see the section on mixing LP and network formats.

<![if !supportEmptyParas]> <![endif]>

Stages

<![if !supportEmptyParas]> <![endif]>

Stages help many stochastic programming solvers to decompose the problem into smaller pieces. They denote the times when new information becomes available. The stages form a subset of the time structure and are characterized by an alternating sequence of decision points and random events. It is assumed that at the time of the first decision all explicit constraints are known, so that the sequence always starts with decision - event - decision - event .... The end of the sequence for recourse problems is ...decision - event - decision, while most problems with chance constraints contain only the sequence decision - event. (Multistage problems with probabilistic constraints have been investigated by Prékopa.)

<![if !supportEmptyParas]> <![endif]>

The usual convention for problems with probabilistic constraints is to consider a stage as (decision – event), while for recourse problems it is more common to use the opposite view. However, to allow mixing of recourse and chance constraints, consistency is essential. This format uses the convention that a stage is made up of an event and a decision (in that order), with the very last event possibly irrelevant.

<![if !supportEmptyParas]> <![endif]>

This has the advantage that the events and the induced decisions lie in the same stage, simplifying the indexing notation for finite distributions and making it easier to set up problems with incomplete information (where some of the first stage coefficients are unknown). The only drawback of this method is that ordinary chance-constrained problems must be thought of as two-stage problems with an unusual second stage that contains no decisions.

<![if !supportEmptyParas]> <![endif]>

Assignment of problem elements to the various stages must then be consistent with the following rules:

<![if !supportEmptyParas]> <![endif]>

1. A column belongs to the stage in which the decision is made.

2. A row belongs to the stage of the latest decision incident with the row.

3. A random variable belongs to the earliest stage that has a stochastic element depending on this random variable.

4. For finite distributions all columns (and with them the rows) must be replicated according to the random variables of the same stage. In particular, this means that for chance-constrained problems (where the final stage contains no decisions) replication is not needed in the final stage.

<![if !supportEmptyParas]> <![endif]>

Stoch file

<![if !supportEmptyParas]> <![endif]>

The purpose of the stoch file is to allow the solver to build a deterministic equivalent, which requires information about the random variables. If all the random variables are finitely distributed, it amounts to the construction of an event tree. The event tree can be described in three different ways: scenario by scenario, node by node, or implicitly using marginal distributions. Implicit descriptions are also available if the random variables are continuously distributed, where explicit descriptions would obviously fail.

<![if !supportEmptyParas]> <![endif]>

The stoch file may contain the following sections:

<![if !supportEmptyParas]> <![endif]>

Section	Purpose
STOCH	Gives a name to the problem in name field 2
SIMPLE	For problems with simple recourse (optional)
ROBUST	For quadratic penalties (optional)
PLINQUAD	For piecewise linear-quadratic penalties (optional)
CHANCE	For chance constraints (optional)
ICC<![if !supportNestedAnchors]><![endif]>	For integrated chance constraints (optional)
SCENARIOS	Gives the values of stochastic elements one scenario at a time
NODES	Gives the values of stochastic elements one node at a time
INDEP	Marginal distribution of independent random variables
BLOCKS	Marginal distribution of a random vector
DISTRIB	Distribution of auxiliary random variables
ENDATA	End of problem data

<![if !supportEmptyParas]> <![endif]>

The three ways of describing the event tree are mutually exclusive. That is, a stoch file cannot contain SCENARIO, NODE and INDEP/BLOCK/DISTRIB sections simultaneously. INDEP, BLOCKS and DISTRIB sections may be mixed freely, although the order must be such that enough information is available to construct the event tree during a single pass through the file.

<![if !supportEmptyParas]> <![endif]>

The small print

<![if !supportEmptyParas]> <![endif]>

Linking (global) constraints

<![if !supportEmptyParas]> <![endif]>

STOCH section

<![if !supportEmptyParas]> <![endif]>

The second name field on the STOCH header record contains the name of the problem. This name is verified against the name in the core and time files.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789

STOCH Example

<![if !supportEmptyParas]> <![endif]>

SIMPLE section for simple recourse

<![if !supportEmptyParas]> <![endif]>

Simple recourse problems use very special recourse matrices, which should not have to be set up by the user explicitly. In simple recourse problems a subset of the rows is of the form _{<![if !vml]><![endif]>}, where the auxiliary variables _{<![if !vml]><![endif]>} and _{<![if !vml]><![endif]>} are nonnegative and are used to balance any shortage (_{<![if !vml]><![endif]>}) or surplus (_{<![if !vml]><![endif]>}) allocation of the decision variables after the random variable b_i has been observed. Any shortage incurs a penalty of _{<![if !vml]><![endif]>}, surplus is penalized by _{<![if !vml]><![endif]>}.

<![if !supportEmptyParas]> <![endif]>

We set up a separate section named SIMPLE as part of the stoch file. Each data record in this section contains the name of one row in the second name field (the first name field contains an identifier and can be used to set up multiple sets of simple recourse coefficients), and the cost coefficients are placed in the two numeric fields; _{<![if !vml]><![endif]>} is first, followed by _{<![if !vml]><![endif]>}. The penalty costs _{<![if !vml]><![endif]>} and _{<![if !vml]><![endif]>} must satisfy the condition _{<![if !vml]><![endif]>} in order for the problem to be bounded; this constraint is enforced by the system.

<![if !supportEmptyParas]> <![endif]>

Each occurrence of a row name in this section triggers the generation of additional decision variables, identified by appending the suffix .minus and .plus after the name of the row. If the row represents an equality constraint, both variables are generated, along with their coefficients in the constraint matrix. If the row is of type L, only the shortage variable <rowname>.minus is created; if the row is of type G, only the surplus variable <rowname>.plus is added. The penalty terms in a simple recourse row will most likely be deterministic, but in a pinch the user can specify stochastic coefficients by using these system-generated variable names.

<![if !supportEmptyParas]> <![endif]>

The recourse variables may be integer-valued. This fact is signalled by placing integer markers into the stoch file.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

SIMPLE

SIMPLE1 ROW1 10.0 5.0

SIMPLE1 ROW2 50.0

<![if !supportEmptyParas]> <![endif]>

Assume that ROW1 is an E-type row and ROW2 has type G. Then each unit of shortage in ROW1 is penalized by 10.0 units in the objective; each unit of surplus has a penalty of 5. Surplus in ROW2 is penalized by 50 units.

<![if !supportEmptyParas]> <![endif]>

In order to allow stochastic recourse costs, the SIMPLE section precedes the NODES, SCENARIOS, INDEP, BLOCKS and DISTRIB sections.

<![if !supportEmptyParas]> <![endif]>

ROBUST section for robust optimization (quadratic penalties)

<![if !supportEmptyParas]> <![endif]>

Quadratic penalties for surplus and shortage have a similar function as the piecewise linear penalties in the section on simple recourse. The most common application of this feature is in robust programming (see, e.g., Mulvey et al.).

<![if !supportEmptyParas]> <![endif]>

We provide a section named ROBUST with syntax identical to the SIMPLE section to provide quadratic penalty coefficients on _{<![if !vml]><![endif]>} and _{<![if !vml]><![endif]>}. The ROBUST section follows the SIMPLE section and, like it, precedes the distribution sections. In keeping with the conventions for the quadratic objective, the penalty term includes an implicit factor of 2, that is, if the entry is of the form

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

ROBUST1 ROW1 0.5 1.5

<![if !supportEmptyParas]> <![endif]>

then negative deviations from the target x₀ are penalized by 0.25*(x–x₀)², positive deviations by 0.75*(x–x₀)².

<![if !supportEmptyParas]> <![endif]>

In many applications the quadratic penalty term is uniform, i.e., it is equal to some value r/2 for all constraints. For simplicity this coefficient can be specified directly in the first numeric field of the header record.

<![if !supportEmptyParas]> <![endif]>

PLINQUAD section for piecewise linear-quadratic penalties

<![if !supportEmptyParas]> <![endif]>

Another type of penalties has received attention in the literature, the piecewise linear-quadratic penalties described by King. These are penalties of the form

_{<![if !vml]><![endif]>}.

Because of continuity and differentiability requirements at 0 and b/a, two parameters suffice to describe these one-sided penalties, the curvature a of the quadratic part and the slope b of the linear part. We propose to express these parameters in a PLINQUAD section, to follow the SIMPLE and ROBUST sections. Each data record in the PLINQUAD section lists an identifying name in the first name field, a valid row name in the second, the quadratic parameter in the first numeric field, and the linear parameter in the second. (If the linear parameter is nonpositive, the penalty is assumed to be a pure quadratic.)

<![if !supportEmptyParas]> <![endif]>

If the mentioned row is of type L, the penalty is applied to positive deviations, if the row is of type G, the penalty applies to negative deviations. In the case of equality constraints, the range on which to apply the penalty is ambiguous but can be clarified in the code field. If the code field is empty, the penalty is applied to both positive and negative deviations; the code PL denotes positive deviations, the code MI is used to specify negative deviations.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

PLINQUAD

PLQ1 ROW3 1.0 10.0

<![if !supportEmptyParas]> <![endif]>

Assume that ROW3 is of type L. Then the first 10 units of shortage are penalized at the progressive rate of 0.5*(short)², all subsequent units are penalized at a rate of 10.

<![if !supportEmptyParas]> <![endif]>

CHANCE section for chance-constrained problems

<![if !supportEmptyParas]> <![endif]>

This section describes the modelling of chance-constrained problems. There are individual (one-dimensional) and joint (multidimensional) chance constraints, with slightly differing syntax.

<![if !supportEmptyParas]> <![endif]>

For the purpose of this exposition we distinguish four different forms of chance constraints:

<![if !supportEmptyParas]> <![endif]>

_{<![if !vml]><![endif]>}

<![if !supportEmptyParas]> <![endif]>

The first two of these are one-dimensional chance constraints, the last two are multidimensional; the symbol ~ indicates an arbitrary constraint type (as set up in the core file), A_k is a matrix, b_k a conformal subset of the right-hand side vector b.

<![if !supportEmptyParas]> <![endif]>

The CHANCE section deals only with supplying the reliability levels a and fault tolerances e, the constraints themselves are defined in the core file, along with their deterministic components; the distributions of the stochastic elements are described in later sections of the stoch file.

<![if !supportEmptyParas]> <![endif]>

Data records for individual chance constraints list the name of the row in the second name field and the reliability level in the first numeric field. The code field can be used to indicate whether we are dealing with a reliability level (Pr{…} ³ a_k — using G as the code value) or a fault tolerance (Pr{…} £ e_k — using code value L). Other valid codes are N and E. The first of these can be used to set up a probabilistic objective, the latter is here mostly for completeness. For N-type records, the numeric fields are ignored.

<![if !supportEmptyParas]> <![endif]>

The first name field is used as a label for this group of constraints. This permits selecting different chance-constraints or perhaps different probability levels, similar to the device of specifying multiple objective rows and/or right-hand side sections in an MPS file.

<![if !supportEmptyParas]> <![endif]>

Example:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789

CHANCE

G CC1 ROW1 0.95

L CC1 ROW2 0.10

<![if !supportEmptyParas]> <![endif]>

This sets up two probabilistic constraints that should be interpreted as

_{<![if !vml]><![endif]>}

assuming that ROW1 and ROW2 were both defined as G-type rows in the core file.

<![if !supportEmptyParas]> <![endif]>

For joint chance constraints we use two types of data records. The first, denoted with a code in the code field, marks the start of the next block, the direction of the probabilistic inequality (JG for reliability levels, JL for fault tolerances), the label for this group of chance constraints in name field 1, a distinguishing name in name field 2 (for the somewhat esoteric situation of a multidimensional chance constraint with a probability level that itself depends on a particular realization of a random variable in the past), and the value of a_k in the first numeric field. The following data records list the names of the rows participating in this constraint, as in the following example:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789

CHANCE

JG CC1 CON1 0.98

ROW3

ROW4

JL CC1 CON2 0.001

ROW5

ROW6

ROW7

<![if !supportEmptyParas]> <![endif]>

This example shows a mixed chance-constrained problem with two multidimensional probabilistic constraints. The first one requires a reliability level of at least 0.98 on ROW3 and ROW4, i.e.,

_{<![if !vml]><![endif]>}

the second prescribes a fault tolerance of no more than 0.001 on ROW5, ROW6 and ROW7, i.e.,

_{<![if !vml]><![endif]>}

assuming that all rows were originally defined as G-type rows in the core file.

<![if !supportEmptyParas]> <![endif]>

ICC section for integrated chance constraints

<![if !supportEmptyParas]> <![endif]>

This type of constraint was introduced by Klein Haneveld in 1986. Assume that a deterministic version of the problem features the constraint

<![if !supportEmptyParas]> <![endif]>

_{<![if !vml]><![endif]>}

<![if !supportEmptyParas]> <![endif]>

Then an integrated chance constraint is of the form

<![if !supportEmptyParas]> <![endif]>

_{<![if !vml]><![endif]>}

where ~ is an arbitrary relation (³, £ or =).

<![if !supportEmptyParas]> <![endif]>

The SMPS format defines an ICC section to set up such integrated chance constraints.

<![if !supportEmptyParas]> <![endif]>

The header record contains the value ICC in the first name field. Each data record contains a code of L or G, an identifying name in the first name field, the name of a row in the second name field, and a numeric value for d in the first numeric field.

<![if !supportEmptyParas]> <![endif]>

Example:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789

ICC

L ICC1 ROW8 10.

<![if !supportEmptyParas]> <![endif]>

Assuming that ROW8 was set up as an L-type row in the core file with right-hand side 100, this stoch file snippet specifies the integrated chance constraint

<![if !supportEmptyParas]> <![endif]>

_{<![if !vml]><![endif]>}

SCENARIOS section

<![if !supportEmptyParas]> <![endif]>

This section describes an explicit event tree scenario by scenario. There is a unique node in the event tree that belongs to the first period. This node is sometimes called the root node. Scenarios are identified with the leaf nodes of the tree. One could think of the scenarios as paths all the way from the root node to the leaves, but it is easier to deal with them in this simplified manner: One scenario (the root scenario) represents a path from the root node to one of the leaves. All other scenarios branch from a parent scenario at some time prior to the final period. Information up to the branch period is shared between a scenario and its parent scenario, only after the branch occurred will there be duplicate information. This point of view is advantageous because it allows for a reduction of redundancy in the tree, which compresses the size of the stoch file.

<![if !supportEmptyParas]> <![endif]>

To code the event tree information into the SCENARIOS section, we use two types of data records. The first, denoted by SC in the code field, signals the start of a new scenario. It gives the name of the scenario in the first name field and its path probability in the first numeric field. The name of the scenario from which it branches is written in the second name field, and the name of the period in which the branch occurred—i.e., the first period in which the two scenarios differ—in the third name field. The root scenario originates in stage one and has no parent scenario. This should be indicated by using the keyword 'ROOT' (including the quotes) in the second name field.

<![if !supportEmptyParas]> <![endif]>

The next data records give the column/row values assumed by the scenario in the same format used in the corresponding section of the core file.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789

SCENARIOS

SC SCEN_A 'ROOT' 0.3 PERIOD1

COL2 ROW3 1.0

COL3 ROW4 1.0

UP BOUND1 COL5 1.0

SC SCEN_B SCEN_A 0.2 PERIOD3

COL3 ROW4 2.0

UP BOUND1 COL5 2.0

SC SCEN_C SCEN_A 0.1 PERIOD2

COL2 ROW3 2.0

COL3 ROW4 2.0

UP BOUND1 COL5 2.0

SC SCEN_D SCEN_C 0.1 PERIOD3

COL3 ROW4 1.0

UP BOUND1 COL5 1.0

SC SCEN_E SCEN_D 0.1 PERIOD4

UP BOUND1 COL5 2.0

SC SCEN_F SCEN_A 0.1 PERIOD2

COL2 ROW3 3.0

COL3 ROW4 3.0

UP BOUND1 COL5 3.0

SC SCEN_G SCEN_F 0.1 PERIOD3

COL4 ROW5 2.0

<![if !supportEmptyParas]> <![endif]>

This is a description of the distribution of three entries: matrix entries in positions COL2/ROW3 and COL3/ROW4, and the upper bound on variable COL5, which we assume to occur in stages 2, 3 and 4, respectively. (The event tree is the tree of figure 1.)

<![if !supportEmptyParas]> <![endif]>

<![if !vml]><![endif]>

Figure 1. An event tree with seven scenarios

<![if !supportEmptyParas]> <![endif]>

A minor modification of the preceding format is needed for network parameters. Since arcs are defined by pairs of nodes, to say that the cost of the arc from node NODE1 to node NODE2 is random requires three parameters. The same goes for bounds and multipliers. In addition to the two name fields, we use the code field as in the following example. (The data record format used in the stoch file for the networks case is the same as that for the LP case.)

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789

SC SCEN_1 'ROOT' 0.3 PERIOD_1

C1 NODE1 NODE3 6.0

U2 NODE6 NODE8 7.0

SU NODE6 6.0

<![if !supportEmptyParas]> <![endif]>

We use C1 for “cost of first arc from node NODE1 to node NODE2” and use higher numbers, such as C2, for the second parallel arc, etc. (The second character in the code field corresponds to the marker placed in the ARCS section in the core file.) Similarly, M = multiplier, U = upper bound, L = lower bound, X = upper and lower bound simultaneously.

<![if !supportEmptyParas]> <![endif]>

Random supply and demand are accommodated by use of SU and DE, respectively, in the code fields as illustrated. The code SI can be used to provide values for a stochastic coefficient in a side constraint.

<![if !supportEmptyParas]> <![endif]>

Any data items not specifically mentioned in the stoch file are inherited by each scenario from its parent scenario, which in turn may inherit them from its parent scenario, and so on. The base scenario inherits its data from the core file. Two things about this scheme of multiple inheritance are noteworthy. First, it is essential that all problems at a stage have the same problem dimensions and nonzero patterns. Second, the values entered for a particular scenario replace any values inherited from the ancestors.

<![if !supportEmptyParas]> <![endif]>

To see why additive or multiplicative perturbations are impractical, consider scenario E in the decision tree of figure 1. Scenario E inherits its values from scenario D, which inherits its third-stage data from scenario C, which in turn inherits them from scenario A, and possibly from the core file. There could therefore be as many as five data items involved before the value of a particular coefficient in scenario E is settled, and the danger of forgetting or misspecifying an addition or multiplication is considerable.

<![if !supportEmptyParas]> <![endif]>

NODES section

<![if !supportEmptyParas]> <![endif]>

This section describes the construction of an event tree one node at a time, which is very convenient when the depth of the tree is not uniform (containing so-called trap states) or when the number of rows or columns associated with a particular period depends on the history of the data process. It is possible to treat such stochastic problem dimensions in a scenario-wise description by introducing a number of empty rows and columns, but these phantom elements (phantom rows, phantom columns, and phantom nodes) introduce irrelevant overhead into the problem formulation. The NODES section provides an alternate way to describe the event tree, without the use of phantom elements.

<![if !supportEmptyParas]> <![endif]>

There are two types of data records. The start of each node is marked by a special code in the code field (see below). The first name field on this record supplies a name to the node and the second name field gives the name of the parent node (in the previous period). The first name field contains the conditional probability of reaching this node, given the parent node. The remaining data records for each node follow the core file layout.

<![if !supportEmptyParas]> <![endif]>

The code field in the node identifier indicates how the information for the node is to be obtained and influences the appearance of the remaining rows. There are two possibilities: one could copy the information from one node to another, allowing for modification of data, although the nonzero structure must remain the same. This is signaled by the value CP in the code field. The alternative is to make up the information on the spot by reading an MPS file. The code MK is used for this purpose.

<![if !supportEmptyParas]> <![endif]>

Under normal circumstance, the MK option is easier to handle, since it makes no assumptions about variable names of different nodes in the same time stage. Individual MPS files can thus be prepared for each node and strung together into one large file fairly easily. When the information is to be created on the spot, we insert an ordinary MPS file after the node identifier record. (We substitute an ENDNODE record to mark the end of the data for this particular node, and the NAME section is optional.) The user should be careful to note that the objective must have the same name in every node. Quadratic objectives are consistent with the MK option; however, the QSECTION must be incorporated into the stoch file.

<![if !supportEmptyParas]> <![endif]>

On the other hand, if there are two or more nodes that do share problem dimensions and variable names, then it is possible to decrease the redundancy and shorten the file length by using the CP option. If information is to be copied, then the third name field on the node identifier record gives the reference node where the information is to be found. The third name field may contain the keyword 'CORFIL'. In this case the information is retrieved from the core file.

<![if !supportEmptyParas]> <![endif]>

Following the node identifier record one lists the modifications to the constraint matrix, right-hand side, bounds, etc., in standard MPS format. There should not be any header records in this section. Any data element not explicitly mentioned is assumed to be identical to the corresponding data element in the reference node.

<![if !supportEmptyParas]> <![endif]>

In this node-by-node description it is much harder to convey the dynamic structure of the problem. The user must therefore exercise discipline when placing the off-diagonal matrix coefficients. Such entries must appear in the block that defines the row, so that the columns will belong to nodes that have been processed before and can therefore be identified. This forces two further restrictions: Special ordered sets of Type 3 cannot have subdiagonal entries (unless they are specified explicitly as binary variables with explicit matrix coefficients), and network records are not allowed. This is because the originating and terminal nodes may belong to different time periods, creating ambiguities as to where to place the data record. (Of course the user is free to supply the network information on MPS style records.)

<![if !supportEmptyParas]> <![endif]>

Every node in the event tree, even the deterministic ones, must be represented by at least the NODE header. The node corresponding to the first period has no predecessor; in this case the second name field should contain the keyword 'ROOT'.

<![if !supportEmptyParas]> <![endif]>

Since the length of a scenario path and the problem dimensions are variable, the contents of the time and core files have to be adjusted as well.

<![if !supportEmptyParas]> <![endif]>

The time file must be present, but it does not necessarily describe the full temporal structure. It must contain enough information to separate those nodes of the core file that are referenced explicitly. The core file must also be present. It lists the deterministic parts of the problem, which would normally include the first stage.

<![if !supportEmptyParas]> <![endif]>

Here is an example to illustrate the above rules.

<![if !supportEmptyParas]> <![endif]>

Time file:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789

TIME ProdDemo

PERIODS

Prod0 Cost Period_0

Prod1 Demd1 Period_1

Prod2 Demd2 Period_2

ENDATA

<![if !supportEmptyParas]> <![endif]>

Core file:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789

NAME ProdDemo

ROWS

N Cost

E Demd0

E Demd1

E Demd2

L Stor0

L Stor1

L Stor2

COLUMNS

Prod0 Demd0 1.

Hold0 Demd0 -1. Demd1 1.

Hold0 Cost 1. Stor0 1.

Prod1 Demd1 1.

Hold1 Demd1 -1. Demd2 1.

Hold1 Cost 1. Stor1 1.

Prod2 Demd2 1.

Hold2 Demd2 -1.

Hold2 Cost 1. Stor2 1.

RHS

RHS Demd0 1.

RHS Demd1 4.

RHS Demd2 4.

RHS Stor0 4.

RHS Stor1 4.

RHS Stor2 4.

BOUNDS

UP BOUND Prod0 4.

UP BOUND Prod1 4.

UP BOUND Prod2 4.

ENDATA

<![if !supportEmptyParas]> <![endif]>

Stoch file:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789

STOCH ProdDemo

NODES

CP NODE0 'ROOT' 1.0 'CORFIL'

CP NODE1 NODE0 0.3 'CORFIL'

RHS Demd1 2.0

CP NODE2 NODE0 0.5 'CORFIL'

CP NODE3 NODE0 0.2 'CORFIL'

RHS DEMD1 6.0

CP NODE4 NODE2 0.3 'CORFIL'

RHS Demd2 4.0

CP NODE5 NODE2 0.4 'CORFIL'

RHS Demd2 5.0

CP NODE6 NODE2 0.3 'CORFIL'

RHS Demd2 6.0

*-----------------------

MK NODE7 NODE3 0.25

ROWS

E Demd2W

E Demd2S

L Stor2

COLUMNS

Hold1 Demd2W 1.0

Prod2W Demd2W 1.0

Prod2S Demd2S 1.0

Hold2W Demd2W -1.0

Hold2W Cost 1.0 Stor2 1.0

Hold2S Demd2S -1.0

Hold2S Cost 1.0 Stor2 1.0

RHS

RHS Demd2W 6.0

RHS Demd2S 4.0

RHS Stor2 4.0

BOUNDS

UP BOUND Prod2W 8.0

UP BOUND Prod2S 8.0

ENDNODE

*-----------------------

CP NODE8 NODE3 0.06 NODE7

RHS Demd2W 6.0

RHS Demd2S 6.0

....

ENDATA

<![if !supportEmptyParas]> <![endif]>

This example describes a three-stage production problem. At the start only a single item is produced. If the demand in period 1 is low, production ceases entirely (the company goes out of business); if the demand in period 1 is medium, production continues; if demand in period 1 is high, a second item is introduced. The event tree with trap state is given in figure 2.

<![if !supportEmptyParas]> <![endif]>

<![if !vml]><![endif]>

Figure 2. An event tree with a trap state

<![if !supportEmptyParas]> <![endif]>

INDEP section

<![if !supportEmptyParas]> <![endif]>

This section describes the modelling of independent random variables. The SMPS format allows for three different forms of the distribution: discretely distributed, possessing a special distribution with no more than two parameters, or by accessing a user-defined subroutine. The header record distinguishes between these forms by placing appropriate keywords into the second name field (see table below). The third keyword may contain the value ADD, MULTIPLY or REPLACE to indicate how the value of the random variable is to modify the information found in the core file. The default is REPLACE.

<![if !supportEmptyParas]> <![endif]>

The data records have the following structure:

<![if !supportEmptyParas]> <![endif]>

first name field	column name of the random element
second name field	row name of the element
first numeric field	value
second numeric field	value
third name field	name of the period in which a particular realization is observed.

<![if !supportEmptyParas]> <![endif]>

If the period can be inferred from the row/column name of the random element, the third name field may be left empty.

<![if !supportEmptyParas]> <![endif]>

The interpretation of the values in the two numeric fields depends on the type of the distribution, as follows:

<![if !supportEmptyParas]> <![endif]>

Keyword in second name field of the header record	Distribution	First numeric field	Second numeric field
DISCRETE	Discrete distribution	Value	Probability^*
UNIFORM	Continuous uniform on [a,b]	a	b
NORMAL	Normal distribution	mean m	variance s²
GAMMA	Gamma distribution (on [0,¥)) _{<![if !vml]><![endif]>}	scale b	shape c
BETA	Beta distribution (on [0,1]) _{<![if !vml]><![endif]>}	n	m
LOGNORM	Lognormal distribution	m = E(ln L)	s² = Var(ln L)
(any other)	User-defined subroutine	(not used)	(not used)

<![if !supportEmptyParas]> <![endif]>

^*Possible values for each random element must be listed in sequence, and the probabilities must sum to 1.

<![if !supportEmptyParas]> <![endif]>

The SMPS format provides for a mechanism by which the user can generate the realizations by accessing a user-defined subroutine. Any modifier on the header record different from the keywords for univariate or multivariate distributions, that is, other than DISCRETE, UNIFORM, NORMAL, GAMMA, BETA, LOGNORM, MVNORMAL, LINTRAN, is taken to be the name of a subroutine, which must be provided by the user. The subroutine can be given calling parameters, and it must return one realization of the random variable it represents. Each parameter value is listed on a separate record following an indicator record containing only the code PR. Two types of values can be passed in this way, integers and reals, assumed to take up, respectively, four and eight bytes. The parameter type is inferred from the appearance of the number, but the user can override this convention by placing one of the two tags 'INTEGR' and 'DOUBLE' into the third name field; their meaning should be self-evident.

<![if !supportEmptyParas]> <![endif]>

Parameters can also be passed by location, making it possible to access any problem coefficient or even current values of the decision variables in order to model any dependence structure required. Locations are identified by placing the column and row names into the first two name fields. Current decision variables are identified by placing the tag 'PRIMAL' into the first name field, current dual variables use the tag 'DUAL'.

<![if !supportEmptyParas]> <![endif]>

Example 1

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

INDEP DISCRETE

COL1 ROW8 6.0 PERIOD2 0.5

COL1 ROW8 8.0 PERIOD2 0.5

RHS ROW8 1.0 PERIOD2 0.1

RHS ROW8 2.0 PERIOD2 0.5

RHS ROW8 3.0 PERIOD2 0.4

<![if !supportEmptyParas]> <![endif]>

In this example the entry COL1/ROW8 takes value 6.0 with probability 0.5 and 8.0 with probability 0.5; and the right-hand side of ROW8 takes values {1.0, 2.0, 3.0} with probabilities {0.1,0.5,0.4} respectively. The example shows random matrix coefficients only, other data items (including network data) can be rendered in the manner described in the SCENARIOS section.

<![if !supportEmptyParas]> <![endif]>

Example 2

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

INDEP DISCRETE ADD

COL1 ROW8 -1.0 PERIOD2 0.5

COL1 ROW8 1.0 PERIOD2 0.5

<![if !supportEmptyParas]> <![endif]>

Assuming that the core file contains a value of 7.0 for the coefficient COL1/ROW8, the entry COL1/ROW8 will again take value 6.0 with probability 0.5 and 8.0 with probability 0.5.

<![if !supportEmptyParas]> <![endif]>

Example 3

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

INDEP UNIFORM

COL1 ROW8 8.0 PERIOD2 9.0

INDEP NORMAL

RHS ROW9 10.0 PERIOD2 4.0

<![if !supportEmptyParas]> <![endif]>

In this example the random entry COL1/ROW8 is uniformly distributed over the interval [8.0,9.0], and the right-hand side in ROW9 is normally distributed with mean 10.0 and variance 4.0.

<![if !supportEmptyParas]> <![endif]>

Example 4

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

INDEP TRIANG

COL5 ROW8 PERIOD2

10.0

20.0

COL1 ROW1

<![if !supportEmptyParas]> <![endif]>

This example shows how to set up a non-symmetric triangular distribution defined over an interval. This requires the specification of the mode along with the two endpoints of the interval. The mode is the third parameter, which is assumed equal to the (possibly random) realization of the coefficient in location COL1, ROW1. (It is left to the user to check that its value does indeed fall between the two endpoints 10 and 20.) When this example is distributed, the user should make sure to include the subroutine TRIANG(min,max,mode).

<![if !supportEmptyParas]> <![endif]>

BLOCKS section

<![if !supportEmptyParas]> <![endif]>

This section shows how to set up multidimensional random vectors that may have correlated components but are independent of other random elements in the problem.

<![if !supportEmptyParas]> <![endif]>

The header record is similar to the INDEP header: The second name field specifies the type of the block (DISCRETE, MVNORMAL, LINTRAN or user defined subroutine), the third name field describes the way the random information interacts with the core file data (ADD, MULTIPLY or REPLACE—the default is REPLACE).

<![if !supportEmptyParas]> <![endif]>

DISCRETE blocks use two types of data records. The first record of each realization is distinguished by the code BL; the first name field gives a name to the block, and the second name field pinpoints the period in which the realizations become known; finally, the first numeric field contains the probability with which this particular set of values is attained. Following this marker, the values are listed on separate data records. The first name field gives the column name, the second name field gives the row name, and the first numeric field gives the value itself. The other fields are not used.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789

BLOCKS DISCRETE

BL BLOCK1 PERIOD2 0.5

COL1 ROW6 83.0

COL2 ROW8 1.2

BL BLOCK1 PERIOD2 0.2

COL2 ROW8 1.3

BL BLOCK1 PERIOD2 0.2

COL1 ROW6 84.0

BL BLOCK1 PERIOD2 0.1

COL1 ROW6 84.0

COL2 ROW8 0.0

<![if !supportEmptyParas]> <![endif]>

To save space, only values that change must be recorded. The SMPS format adopts the convention that the first statement of the block is the basis from which all changes are computed. (This implies that zero values in subsequent realizations must be stated explicitly, as shown in the last data record of the example above.)

<![if !supportEmptyParas]> <![endif]>

In this example the block, called BLOCK1, is the 2-vector made up of the entries COL1/ROW6 and COL2/ROW8. It takes values (83.0,1.2) with probability 0.5, (83.0,1.3) with probability 0.2, (84.0,1.2) with probability 0.2, and (84.0,0.0) with probability 0.1.

<![if !supportEmptyParas]> <![endif]>

It is possible to model additive or multiplicative perturbations, but the user must be careful since each block modifies the core file values and at the same time replaces values in the first occurrence of the block. If the core file records values of 83.0 and 1.2 for the locations COL1/ROW6 and COL2/ROW8, respectively, then the following specification is equivalent to the previous example:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789

BLOCKS DISCRETE ADD

BL BLOCK1 PERIOD2 0.5

COL1 ROW6 0.0

COL2 ROW8 0.0

BL BLOCK1 PERIOD2 0.2

COL2 ROW8 0.1

BL BLOCK1 PERIOD2 0.2

COL1 ROW6 1.0

BL BLOCK1 PERIOD2 0.1

COL1 ROW6 1.0

COL2 ROW8 -1.2

<![if !supportEmptyParas]> <![endif]>

Multivariate normal distributions can be set up using the MVNORMAL keyword on the header record. The first data record contains a BL in the code field and has the same appearance as the first data record for DISCRETE blocks. Following this is a list of locations that make up this block. Each location is identified by two names in the first two name fields, which leaves two numeric fields and a third name field free. We place the mean value of each marginal distribution in the first numeric field and the variance in the second. An alias is placed in the third name field so that future occurrences of this random variable can be uniquely deduced from a single name field.

<![if !supportEmptyParas]> <![endif]>

It remains to specify the correlations between pairs of random variables. This is effected in a separate subsection whose start is marked with the code CR in the code field. On each data record, the first two name fields list the aliases of two locations and the first numeric field contains the correlation between the two random variables.

<![if !supportEmptyParas]> <![endif]>

Alternatively the user may want to specify the covariances between the components of the random vector. This is easily set up using the code CV.

<![if !supportEmptyParas]> <![endif]>

Example:

<![if !supportEmptyParas]> <![endif]>

BLOCKS MVNORMAL

BL BLOCK1 PERIOD2

COL1 ROW6 5.0 ALIAS1 1.0

COL2 ROW8 8.0 ALIAS2 2.0

COL3 ROW9 11.0 ALIAS3 3.0

ALIAS1 ALIAS2 0.6

ALIAS1 ALIAS3 0.6

ALIAS2 ALIAS3 0.6

<![if !supportEmptyParas]> <![endif]>

This example sets up a trivariate normal distribution of the three locations COL1/ROW6, COL2/ROW8, COL3/ROW9, with mean vector (5,8,11), and variances 1, 2, and 3, respectively. The three components are equicorrelated with correlation coefficient 0.6.

<![if !supportEmptyParas]> <![endif]>

Random vectors can also be generated by a user-defined subroutine. This is indicated by a modifier value that is not part of the existing standard, that is, not equal to DISCRETE, UNIFORM, NORMAL, GAMMA, BETA, LOGNORM, MVNORMAL, LINTRAN, similar to the INDEP section.

<![if !supportEmptyParas]> <![endif]>

The BL record once again marks the beginning of the block, giving a name and fixing the stage for the block. On subsequent data records the locations making up the random vector are listed in the first two name fields. Parameters that must be passed to the subroutine can be specified following a record containing the code PR, with all the conventions and possibilities discussed in the INDEP section.

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

BLOCKS USER1

BL BLOCK1 PERIOD2

COL1 ROW6

COL2 ROW8

COL3 ROW9

12.0

3.0

RHS ROW1

'PRIMAL' COL5

<![if !supportEmptyParas]> <![endif]>

The user-defined subroutine USER1 returns values for the locations COL1/ROW6, COL2/ROW8, COL3/ROW9. This routine takes four parameters, whose values are given on the records following the marker PR. The third parameter is the value of the right-hand side of ROW1, the fourth parameter is the current value of the decision variable COL5.

<![if !supportEmptyParas]> <![endif]>

Sometimes the user may want to specify stochastic coefficients determined by underlying random phenomena (factors) of lower dimension. A simple form of this relationship is an affine transformation, which can be written mathematically as v = H u + c, where H and c are deterministic and u is a random vector. Even though this device may blur the boundary between modelling and recording of an instance in ways not intended by the original MPS format, it is nonetheless useful because in many cases the dimension of the vector u is much smaller than that of the vector v. Certain approximation algorithms may be able to take advantage of working in the original space, so that there is considerable merit in associating the original random factors u with the problem instance.

<![if !supportEmptyParas]> <![endif]>

The use of this format is signalled by the keyword LINTR on the BLOCKS header record. Once more the start of each block is marked with a record containing the code BL in the code field, followed by a name for the block in the first name field. The second name field identifies the period in which the information becomes known. Following this header record, the locations of the elements of the random vector v are identified on separate data records using the first two name fields; the additive constant (component of the vector c) can be entered in the first numeric field.

<![if !supportEmptyParas]> <![endif]>

Then the coefficients of the transformation matrix H are given column by column. Each column is tied to one component of the vector u, and there are two mechanisms for supplying its distribution. Any components of u that is independent of the other components can be specified directly on a record with the code RV. The identifier of the distribution (DISCRETE, UNIFORM, etc.) is placed in the second name field, the distribution parameters are placed in the two numeric fields. The first name field is not used. Alternatively, the name of a random variable defined in a preceding DISTRIB section may be placed into the first name field.

<![if !supportEmptyParas]> <![endif]>

Which of these two mechanisms is used depends on the appearance of the RV data record. If the second name field is empty, the random variable named in the first name field must have been defined in a preceding DISTRIB section; if the second name field is not empty, its value must describe a valid two-parameter distribution family, which is then taken to describe the distribution of the current random variable. In this case the first name field is ignored (but must be present for correct parsing of free-format input).

<![if !supportEmptyParas]> <![endif]>

We will illustrate these rules with the following example:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

DISTRIB MVNORMAL

BL BL1

U1 0.0 1.0

U2 0.0 1.0

U1 U2 0.5

BLOCKS LINTR

BL BLOCK1 PERIOD1

COL1 ROW1 5.0

COL2 ROW2 10.0

COL3 ROW3 0.0

COL4 ROW4 0.0

RV U1

COL1 ROW1 -1.0

COL2 ROW2 2.0

COL3 ROW3 1.0

RV U2

COL1 ROW1 1.0

COL2 ROW2 2.0

COL3 ROW3 3.0

COL4 ROW4 4.0

RV U3 NORMAL 10.0 3.0

COL1 ROW1 1.0

<![if !supportEmptyParas]> <![endif]>

This example defines a joint probability distribution for the four random elements COL1/ROW1, COL2/ROW2, COL3/ROW3, COL4/ROW4 making up the random vector v, which depends on a three-dimensional random vector u as follows: The first two components of u are defined in a DISTRIB section as bivariate normal with mean (0,0)' and covariance matrix _{<![if !vml]><![endif]>}. The third component is defined directly in the block itself and is normal with mean 10 and variance 3. It is independent of the other components, so that u will have a trivariate normal distribution with mean (0,0,10)^T and covariance matrix _{<![if !vml]><![endif]>}. The affine transformation is given by _{<![if !vml]><![endif]>}

<![if !supportEmptyParas]> <![endif]>

By the rules governing linear transformations of normal random variables, v=Hu+c is therefore also normally distributed with mean vector m_v = H m_u + c = (15, 10, 0, 0)^T and covariance matrix _{<![if !vml]><![endif]>}.

<![if !supportEmptyParas]> <![endif]>

DISTRIB section

<![if !supportEmptyParas]> <![endif]>

This section describes the use of random variables (univariate and multivariate) that do not correspond directly to stochastic elements within the current problem. This device is needed to adequately model certain multivariate distribution, since the MPS data record does not allow sufficient fields to specify correlations between random elements. The main purpose of a DISTRIB section is to provide an alias (a single name) by which the random variable can be referenced in a later BLOCKS section.

<![if !supportEmptyParas]> <![endif]>

There may be many DISTRIB sections; it is assumed that each of them defines random variables independently of the others. Conversely, each new group of random variables must be introduced by a new DISTRIB header.

<![if !supportEmptyParas]> <![endif]>

The rules for the DISTRIB sections are similar to those for other distributions (INDEP, BLOCKS) except that only one name field (the first) is used to provide the name for the random variable. Discrete random variables can be defined, as can two-parameter families and the multivariate normal distribution. In the latter case, distinct names must be used for the distribution and for each of its components. The user can even specify univariate or multivariate random variables by accessing a custom-made subroutine. The only situation explicitly ruled out is that of a random vector with a discrete multivariate (i.e., dependent) distribution. Such distributions should be specified directly (using the BLOCKS DISCRETE format).

<![if !supportEmptyParas]> <![endif]>

Example

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789 123456789

DISTRIB UNIFORM

U1 0.0 1.0

DISTRIB MVNORMAL

BL BL1

U2 0.0 1.0

U3 0.0 1.0

U2 U3 0.5

<![if !supportEmptyParas]> <![endif]>

This example defines the auxiliary random variable U1, which is uniformly distributed on [0,1], and a bivariate normal random vector whose components have mean 0, variance 1 and covariance 0.5. The vector can be referred to as BL1, its first component as U2 and its second component as U3.

<![if !supportEmptyParas]> <![endif]>

Linking constraints

<![if !supportEmptyParas]> <![endif]>

Most constraints in stochastic programming are of the “replicating” kind. This means that each constraint contains variables from at most one node in each period. The constraint is thought to belong to the latest period in which it has variables and is replicated for each realization of the random elements.

<![if !supportEmptyParas]> <![endif]>

In some special instances (for example, to model risk constraints in financial applications) it may be useful to link together variables belonging to different nodes in the same period. The easiest way to include such linking or global constraints in a stochastic program is to assign the constraint to the first period. (This is best done using the explicit form of the time file.) While the more common decomposition solvers will not be able to deal with linking constraints, specially developed software (see e.g., Steinbach 2003) is available.

<![if !supportEmptyParas]> <![endif]>

The following is an example of a linking constraint:

<![if !supportEmptyParas]> <![endif]>

Core file entry:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789

ROWS

G GLOBCON

...

COLS

...

FWEALTH GLOBCON 1.20

...

RHS

RHS1 GLOBCON 100.

<![if !supportEmptyParas]> <![endif]>

Time file entry:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789

PERIODS EXPLICIT

Period_1

Period_2

…

ROWS

...

GLOBCON Period_1

COLS

...

FWEALTH Period_2

<![if !supportEmptyParas]> <![endif]>

Stoch file entry:

<![if !supportEmptyParas]> <![endif]>

*23456789 123456789 123456789 123456789 123456789

SCENARIOS

SC Scen_1 ‘ROOT’ 0.4 Period_1

SC Scen_2 Scen_1 0.6 Period_2

FWEALTH GLOBCON 1.30

...

<![if !supportEmptyParas]> <![endif]>

This construction sets up the global constraint

<![if !supportEmptyParas]> <![endif]>

1.20*FWEALTH(Scen_1) + 1.30*FWEALTH(Scen_2) ³100.

<![if !supportEmptyParas]> <![endif]>

Order of processing

<![if !supportEmptyParas]> <![endif]>

To make sure that the many variations can all be parsed correctly it is important to read the three files in the correct order, as follows:

<![if !supportEmptyParas]> <![endif]>

Time file: PERIODS section only

Core file

Time file: Remaining sections (if any)

Stoch file

<![if !supportEmptyParas]> <![endif]>

Solver capabilities and error recovery

<![if !supportEmptyParas]> <![endif]>

The SMPS format is extremely flexible and can define a wide variety of problems, far exceeding the capability of any existing stochastic programming solver. It should not be assumed, therefore, that a given problem can be solved with a particular solver nor that in fact there is any solver capable of solving the problem. However, any SMPS parser should recover gracefully when it encounters a section or construct its solver is not prepared to deal with.

<![if !supportEmptyParas]> <![endif]>

References:

<![if !supportEmptyParas]> <![endif]>

[1]. J.R. Birge, M.A.H. Dempster, H.I. Gassmann, E.A. Gunn, A.J. King and S.W. Wallace, “A standard input format for multiperiod stochastic linear programs”, COAL Newsletter #17 (1987) pp. 1–19.

<![if !supportEmptyParas]> <![endif]>

[2]. J.R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer Series in Operations Research, Springer Verlag, New York, 1997.

<![if !supportEmptyParas]> <![endif]>

[3]. A. Charnes and W.W. Cooper, “Chance-constrained programming”, Management Science 5 (1959) 73–79.

<![if !supportEmptyParas]> <![endif]>

[4]. J. Edwards, J. Birge, A. King and L. Nazareth, “A standard input format for computer codes which solve stochastic programs with recourse and a library of utilities to simplify its use”, Working Paper WP-85-03, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1985.

<![if !supportEmptyParas]> <![endif]>

[5]. H.I. Gassmann and E. Schweitzer, “A comprehensive input format for stochastic linear programs”, Annals of Operations Research 104 (2001) 89-125.

<![if !supportEmptyParas]> <![endif]>

[6]. International Business Machines, Inc., "Passing your model to OSL using Mathematical Programming System (MPS) format", world-wide web document, http://www6.software.ibm.com/sos/features/featur11.htm.

<![if !supportEmptyParas]> <![endif]>

[7]. P. Kall and S.W. Wallace, Stochastic Programming, John Wiley and Sons, New York, 1994.

<![if !supportEmptyParas]> <![endif]>

[8]. A.J. King, “An implementation of the Lagrangian finite-generation method”, in: Yu. Ermoliev and R.J-B Wets (eds.), Numerical Techniques for Stochastic Optimization, Springer Series in Computational Mathematics, Vol. 10, Springer Verlag, Berlin, 1988.

<![if !supportEmptyParas]> <![endif]>

[9]. W.K. Klein Haneveld, Duality in Stochastic Linear and Dynamic Programming, Lecture Notes in Economics and Mathematical Systems, Vol. 274, Springer-Verlag, Berlin, 1986.

<![if !supportEmptyParas]> <![endif]>

[10]. D. Klingman, A. Napier and J. Stutz, “NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems”, Management Science 20 (1974) 814–821.

<![if !supportEmptyParas]> <![endif]>

[11]. J.M. Mulvey, R.J. Vanderbei and S.A. Zenios, “Robust optimization of large-scale systems”, Operations Research 43 (1993) 264–281.

<![if !supportEmptyParas]> <![endif]>

[12]. A. Prékopa, Stochastic Programming, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995.

<![if !supportEmptyParas]> <![endif]>

[13]. M.C. Steinbach, "Tree-sparse convex programs", Mathematical Methods of Operations Research 56 (2003) 347-376.

<![if !supportEmptyParas]> <![endif]>

Last modified 08 April 2003.

<![if !supportEmptyParas]> <![endif]>

Please send comments and errata to the author.

<![if !supportEmptyParas]> <![endif]>

Distribution