The main subjects of modern systems analysis: economics, population and the
environment are characterized by a number of general features that make them
particularly difficult for existing methods. These are: complexity, dynamics and
uncertainty. Especially, the presence of uncertainty makes the traditional
approaches insufficient. Uncertainty may result from many sources: missing or
inaccurate data, the existence of external uncontrollable disturbances and
forecasting errors, among others. For dynamic problems that have to be modeled
over many time periods there are inevitable uncertainties regarding future data.
When a model is used for decisionmaking an active approach to uncertainty
should be developed; model it rather than ignore it. There are many ways to
model uncertainty; one which has already found successful applications and which
is the main approach used in this project is to model uncertain quantities by
random variables. Probabilistic models of uncertainty allow the formulation of
many different decision problems reflecting specific features of a given
application (such as expected value maximization, mean-variance models,
maximization or minimization of probabilities of certain events, event-specific
constraints, etc.). The advantage of probabilistic modeling is that problems
with uncertainty can be analyzed by rigorous mathematical methods and that
techniques for their solution can also have a solid theoretical background.
However, to make such modeling techniques a useful methodology, the gap between
theory and applications has to be closed. This is the main objective of the
project and it includes a number of specific activities to be detailed in the
next sections, related to modeling, solution methods and applications. There are three fundamental objectives of the project. First, motivated by
applied problems, develop practical modeling techniques for incorporating
uncertainty into long-term investment planning problems in environmental
protection. In particular, modeling techniques should be developed that build on
existing deterministic models. Secondly, progress should be made in developing flexible and practical
solution techniques for solving realistic models with uncertainty. Only a
narrow class of such problems can be solved by analytical methods. Real world
problems usually require computational approaches. However, existing
computational methods of optimization cannot solve problems with uncertainty,
even if they are approximated by some deterministic problems. The main
difficulty here is the enormous size of resulting problems, orders of magnitude
above the the capabilities of the existing deterministic methods. What is
needed are special methods that exploit the structure of multistage problems
with uncertainty. Thirdly, specialized versions of the general modeling and solution
techniques have to be developed for some of the applied models analyzed at
IIASA. Such detailed case studies should help to identify the strengths and the
weaknesses of the methods developed and to motivate future research. The fundamental approach is to approximate the underlying distribution of
uncertain data by a discrete one - composed of a finite number of scenarios.
Here, a scenario means an instance of the problem's data that could be used to
solve the problem as a deterministic one, if the data were true. Obviously,
this cannot be confined to one scenario - many of them are needed to reflect
uncertainty. Still, problems with finitely many scenarios are much more
amenable to solution via the decomposition methods discussed below than are
problems with general distributions of uncertain data. There remain, however, a number of fundamental questions regarding the
relationship between the approximate problem and the original one. In
particular, what guarantee is there that when the number of scenarios grows the
approximate problem becomes close (in some sense) to the original one? How
should the scenarios be selected: at random or should an attempt be made to find
some critical scenarios? These fundamental questions have direct implications
for numerical methods and for particular application problems. Scenario-based models provide a convenient framework for developing
computational methods for decision problems with uncertainty. The main approach
followed will be decomposition in the space of uncertain parameters into
scenario subproblems. Such an approach seems to be well suited to real world
applications for many reasons. First, scenario-based models are built of blocks
which are copies of a deterministic model, usually already well-understood. This
facilitates the use of knowledge and the models (computer programs) accumulated
in the earlier stage of the research. Secondly, scenario-based models provide
an important insight into the problem by explicitly dealing with so-called
non-anticipativity constraints: relations representing the necessity of making
decisions before uncertain data is known. The analysis of these constraints and
the associated dual multipliers provides us with estimates of the acceptable
costs of reducing uncertainty. Finally, scenario decomposition approaches are
better suited for real world applications because they can exploit to the full
extent the power of the existing hardware (networks of workstations) by allowing
parallel and distributed computation. Apart from computational advantages, they
also have a modeling value, because they provide an insight into the structure
of the problem. There exist, however, classes of problems, such as, for example, discrete
event systems, where it is very difficult or even impossible to define a
meaningful finite set of scenarios, and the analysis has to be based on
simulation techniques. Therefore, it is crucial to develop in parallel tools
for optimizing such problems as well; these tools are based on a combination of
simulation and optimization within one iterative procedure. The activities of the project can be divided into two main areas: (1)
theoretical research and (2) modeling and applications. There are five major theoretical problems that should be addressed in 1996:
There are two objectives. The state-of-the-art of the field of stochastic optimization will be
discussed at the "Winter School of Stochastic Optimization" to be held
in Austria in January 1996, which will be partially supported by IIASA. Theoretical results will be presented in the form of working papers and
(later) papers in refereed journals and conference proceedings on: The computational and modeling work will be presented as Team members involved are likely to be Andrzej Ruszczynski, Vladimir Norkin
(30% time), Georg Pflug (20% time), Hirokazu Tatano. Collaboration is foreseen with the Risk, Policy and Complexity project on
allocating indivisible resources under uncertainty and constraint aggregation;
and with the Dynamic Systems project on constraint aggregation techniques.
External collaboration will continue with R. Tyrell Rockafellar, University of
Washington, Seattle and Krzysztof Kiwiel, Systems Research Institute of the
Polish Academy of Sciences, Warsaw (on decomposition methods), Roger J.B. Wets,
University of California, Davis, USA (on finite scenario approximations); with
Jitka Dupacova, Charles University, Prague, Czech Republic and John M. Mulvey,
Princeton University, USA (on economic applications), and Stephen M. Robinson,
University of Wisconsin-Madison, USA (on simulation-based models), and with
Werner Römisch, Humboldt University, Berlin, Germany (on sensitivity of
stochastic optimization problems).
Abstract
Uncertainty is one of the main issues that has to be addressed by modern
systems analysis. There are missing or inaccurate data, unknown external
disturbances and the fundamental uncertainty of the future. Incorporating
uncertainty into a model makes it more realistic, provides additional insights
into its properties and may suggest new types of solutions, that do not appear
in deterministic models. The objective of the project is three-fold. First,
develop practical modeling techniques that will facilitate extension of existing
deterministic models into models explicitly incorporating uncertainty. Secondly,
develop efficient solution techniques for such models which would not only allow
for solving problems with uncertainty but also provide an additional insight
into them. Finally, apply the techniques to a number of models analyzed by other
IIASA projects. The main theoretical idea on which these developments will
be built is the decomposition of the stochastic problem into a finite number of
manageable scenario subproblems and coordination of their solutions by specially
designed algorithms.
Introduction
Objectives
Approach and Activities
Theoretical Research
Modeling and Applications
Expected Results and Applications
Personnel and Collaboration