- SCFXM1 is real-world production scheduling problem of unknown origin. The
problem is two stage, but can be extended to a multistage problem.
The problem originated in Ho and Loute , and has been extended by
Birge, Gassman, and Birge, et. al.
- CEP1 is a two-stage machine capacity planning problem provided by
Survajeet Sen (see, e.g. Higle and Sen).
- STORM is a two period freight scheduling problem described in
Mulvey and Ruszczynski. (The problem was provided to
the University of Michigan courtesy of Adam Berger). In this model,
routes are scheduled to satisfy a set of demands at stage 1, demands
occur, and unmet demands are delivered at higher costs in stage
2 to account for shortcomings.
Expansion and Planning Problems
- SCAGR is a multiperiod dairy farm expansion model. The problem first
appeared in deterministic form in a chapter by Swart, Smith, and Holderby.
The model was subsequently collected in electronic form by Ho and Loute and modified by Birge and Gassman.
- SSN is a telephone switching network expansion planning problem,
discussed in Sen, Doverspike, and Cosares The model seeks to
add capacity (lines) to a network of existing point-to-point connections
so as to minimize the number of unfilled requests for service. Demand is
defined as the number of requests for connections at a given instance
of time, and is stochastic.
- SC205 is a dynamic multisector planning problem adapted by Ho and
Loute from Manne's ETA model. The history of the model is unclear, but
SC205 appears to be model whose goal is to determine a free market's
ability to supply energy to an economy. Since the model appears to be a
feasibility problem, it probably was formulated to find equilibrium
points where shadow prices of energy sources are equal to their marginal
costs of supply.
- SCRS8, collected by Ho and first modified to include
stochasticity by Birge, is a technological assessment model
for the transition from nonrenewable to renewable energy sources. The
model is a linearized version of the ETA model (Manne)
which seeks to find the minimal cost strategy to meet future energy
- PLTEXP (Sims) is a stochastic capacity expansion model inspired
by manufacturing flexibility research in Graves and Jordan.
The model is similar to SSN in that it tries to allocate new production
capacity across a set of plants so as to maximize profit subject to uncertain
demand. However, instead
of enumerating a set of possible expansions, PLTEXP explicitly models the
expansion options with binary variables. The test version is the linearized
- PGP2 is an electrical capacity expansion problem developed by Louveaux
and Smeers. (The problem was donated in digital format
by Survajeet Sen, University of Arizona, and by H. I. Gassman)
The two-stage stochastic program finds the minimal cost strategy for investing
in various types of power plants.
- STOCHFOR is a multistage model developed by Gassman to
determine logging levels to maximize output. The problem considers the
risk of fire and of other environmental hazards. (The electronic
form was donated by H. Gassman).
- Network Models of Mulvey and Vladimirou
- Mulvey and Vladimirou have
created several two-stage network programs for finding the
optimal investment strategy to meet cash flow needs in the face of uncertain
investment returns. Although the formulations are two-stage in the
formal sense, the second stage groups together multiple time periods.
The goal of the model is to allocate funds to asset categories in each
of four periods. Flows of funds between assets in a period have fixed marginal
costs. Asset returns from one period to the next are modeled using stochastic
multipliers on ``arcs'' from between periods. A scenario in this case is a
realization of all future asset returns.
- OPTN - An option selection model
- OPT is a multistage stochastic programming model for selecting a minimal
(expected) cost option portfolio. The portfolio must guarantee that an
acceptable level of dollar revenue will be obtained given
that a known quantity of a foreign currency must be exchanged in the
future. The model was first developed by Klaassen, et. al.
and was digitized and slightly modified by Derek Holmes.
- ALM: Asset Liability Management
- Kusy and Ziemba developed a multistage stochastic formulation
called ALM to try to balance a bank's income stream from a set of assets
against a set of liabilities. The assets are loans and investments with
uncertain returns and varying levels of risk, and the liabilities are depositor's
withdrawals from demand accounts.
- SCTAP1: Traffic Assignment
- SCTAP1 is a stochastic version of a two stage traffic assignment problem
given in Ho. The objective of the problem is to find a
set of traffic flows over a network with multiple sources and one sink
that minimizes some cost function. The cost function is a utility function
associated with traffic congestion. The flow of traffic is governed by an
``exit function'' for each arc which relates the amount of traffic entering
and leaving an arc in a given period. This function is (in general) a
nondecreasing, continuous concave function, which is linearized to
form a problem in standard LP form.
- SCSD: Design of a multistage truss
- SCSD is a multistage model due to Ho which seeks to find the
lowest weight truss design given a set of admissible joints in the plane
and a load which the truss must bear.
The structure is formed by placing bars between pairs of joints, and must
satisfy constraints on maximum stress in each bar.
This page was last modified on . Send
- J. R. Birge, 1985. ``Decomposition and partitioning methods
for multistage stochastic linear programs,'' Operations Research,
33, pp. 989-1007.
- J. R. Birge, M.A.H. Dempster, H. I. Gassman, E. A.
Gunn, A. J. King, and S. W. Wallace, 1987. ``A Standard forinput format for
multiperiod stochastic linear programs,'' COAL newsletter, 17, pp. 1-20.
- J. R. Birge, H. I. Gassman, and D. Holmes, 1991. STOPGEN
stochastic linear program deterministic equivalent problem generator.
- J. R. Birge and F. Louveaux, 1994.
Introduction to Stochastic Programming, manuscript.
- J. Birge, C. Donohue, D. Holmes, and O. Svintsitski, 1993.
``A Parallel Implementation of the Nested Decomposition Algorithm
for Multistage Stochastic Linear Programs,'' to appear in
- G. Dantzig, 1963. Linear Programming and Extensions,
Princeton University Press, Princeton, NJ.
- Fourer, R., D. M. Gay, and B. W. Kernighan, 1992.
AMPL: A Modeling Language for Mathematical Programming, Scientific
Press, San Francisco, CA.
- H. I. Gassman, 1989. ``Optimal harvest of a forest in
the presence of uncertainty,'' Canadian Journal of Forest Research,
Vol 19, pp. 1267-1274.
- H. I. Gassman, 1990. ``MSLiP: A computer code for the
multistage stochastic linear programming problem.''
Mathematical Programming, 47, pp. 407-423.
- S. C. Graves and W. C. Jordan, 1991. ``Principles
of the Benefits of Manufacturing Process Flexibility,'' General Motors
Laboratories Research Publication.
- J. L. Higle, and S. Sen, 1990. ``Finite Master Programs in
Regularized Stochastic Decomposition,''
Dept. of Systems and Industrial Engineering,
University of Arizona, Tucson, AZ, 85721.
- J. K. Ho, 1975. ``Optimal Design of Multistage Structures:
A Nested Decomposition Approach,'' Computers and Structures, Vol. 5,
- J. K. Ho, 1977. ``Nested Decomposition of a Dynamic Energy
Model,'' Management Science Vol. 23, No 9. pp. 1022-1026.
- J. K. Ho, 1980. ``A successive Linear Optimization Approach to
the Dynamic Traffic Assignment Problem,'' Transportation Science, 14(4),
- J.K. Ho and E. Loute, 1981. ``A Set of Linear Programming Test
Problems,'' Mathematical Programming 20 245-250.
- International Business Machines Corp., 1991. ``Optimization
Subroutine Library Guide and Reference, Release 2,'' document SC23-0519-02,
International Business Machines Corp.
- P. Klaassen, J. F. Shapiro, and D. E. Spitz, 1990.
``Sequential Decision Models for Selecting Currency Options,'' IFSRC Report
No. 133-90, International Financial Services Research Center, Massachussets
Institute of Technology, Cambridge, MA.
- M. I. Kusy and W. T. Ziemba, 1986. ``A Bank Asset
and Liability Management Model,'' Operations Research, 34(3), pp. 356-376.
- F. Louveaux and Y. Smeers, 1988. ``Optimal investments for electricity
generation: a stochastic model and a test-problem,'' in Numerical Techniques
for Stochastic Optimization, Springer-Verlag, Berlin, pp. 33-64.
- I. Lustig, J. Mulvey, and T. Carpenter, 1991. ``Formulating
stochastic programs for interior point methods,'' Operations Research
39:5, pp. 757-770.
- A. S. Manne, 1975.``U.S. Options for the transition
from oil and gas to synthetic fuels,'' Discussion Paper No. 26F, Public
Policy Program, John F. Kennedy School of Government, Harvard University
- J. M. Mulvey, and H. Vladimirou, 1989. ``Stochastic
network optimization model for investment planning,''
Annals of Operations Research. Vol. 20, p. 187.
- J. M. Mulvey, and H. Vladimirou, 1991. ``Applying
the Progressive Hedging Algorithm to Stochastic Generalized Networks.''
Annals of Operations Research. Vol. 31, pp. 399-424.
- J. M. Mulvey, and A. Ruszczynski, 1992. ``A New
Scenario Decomposition Method for Large Scale Stochastic Optimization,''
Technical Report SOR-91-19, Dept. of Civil Engineering and Operations
Research, Princeton Univ. Princeton, N.J. 08544
- S. Sen, J. Mai, and J. L. Higle, 1993. `` Solution of
Large Scale Stochastic Programs with Stochastic Decomposition Algorithms,''
Technical Report, SIE Dept., University of Arizona, Tucson, AZ, 85721.
- S. Sen, R. D. Doverspike, and S. Cosares, 1992. ``Network
Planning with Random Demand,''
Dept. of Systems and Industrial Engineering,
University of Arizona, Tucson, AZ, 85721.
- M. J. Sims, 1992. ``Use of a stochastic capacity planning
model to find the optimal level of flexibility for a manufacturing system,''
Senior Design Project, Department of Industrial and Operations Engineering,
University of Michigan, Ann Arbor, MI 48109.
- W. Swart, C. Smith, and T. Holderby, 1975.
``Expansion Planning for a Large Dairy Farm,'' Chapter 8 in Studies
in Linear Programming, H. Salkin and J. Saha, eds. North Holland,