Uncertainty is one of the main issues that should be addressed by modern systems fundaanalysis. Missing or inaccurate data, unknown external disturbances and the mental uncertainty of the future need investigation. Incorporating uncertainty into models makes them more realistic, provides additional insight into their properties, and may suggest new types of solutions that do not appear in deterministic models.The objective of the Optimization Under Uncertainty Project is three-fold. First, to develop practical modeling techniques that will facilitate extension of existing deterministic models into models explicitly incorporating uncertainty. Second, to develop efficient solution techniques for such models that would not only allow solving problems with uncertainty, but also provide an additional insight into them. Finally, to 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.
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. The presence of uncertainty makes the traditional approaches especially insufficient. Uncertainty may result from many sources: i.e., 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 that has already found successful applications and is the main approach used in the 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, e.g., 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 techniques for their solutions can also have a solid theoretical background.
To make such methodological modeling techniques useful however, the gap between theory and applications has to be closed. Only a narrow class of 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.
There are three fundamental objectives of the project. First, motivated by applied problems, to develop practical modeling techniques for incorporating uncertainty into longterm investment planning problems in environmental protection. In particular, modeling techniques should be developed that build on existing deterministic models. Second, progress should be made in developing flexible and practical solution techniques for solving realistic models with uncertainty. Third, specialized versions of 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 motivate future research.
The fundamental approach used in the project 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 was true. Obviously, this cannot be confined to one scenario - many are needed to reflect uncertainty. Still, problems with many finite 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 earlier stages of research. Second, 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 can provide estimates of the acceptable costs of reducing uncertainty. Finally, scenario decomposition approaches are better suited for real world applications because they can exploit, to a 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.
The activities of the project can be broken down into two main areas: (1) theoretical research, and (2) modeling and applications.
There are two major theoretical problems that should be addressed in the near future. The first is to perform an analysis of the concept of critical scenarios, i.e., collections of data that sufficiently describe uncertainty in the optimization problem. Together with that, advances in computational methods should be made to quickly process large numbers of scenarios by identifying the critical ones.
The second theoretical problem to be addressed is an analysis of the convergence properties of decomposition methods with sparse linking structures and their application to scenario decomposition techniques in stochastic optimization and other large scale models. A long term objective here would be to formulate advances in primal-dual decomposition methods.
The main activity planned here is the development of a flexible computer program that would include scenario (subproblem) models in a modeling language (GAMS) and a coordinating procedure based on regularized duality relations for stochastic programs. Extensions to the Parallel Virtual Machine (PVM) framework will be the next step. Discussions are underway with IIASA's Environmentally Compatible Energy Strategies Project, to test this approach on a stochastic version of a dynamic macroeconomic model.
The results and future directions of research will be discussed at the 7th International Conference on Stochastic Optimization to be held in 1995.
Theoretical results will be presented in the form of working papers and (later) papers in refereed journals and conference proceedings on properties of critical scenarios; and convergence properties of decomposition methods for sparsely linked structures. Computational and modeling work will be presented as a C program for coordinating GAMS submodels for scenarios, and working papers reporting the experience from applying the methodology to specific models.
Team members involved are likely to be Project Leader Andrzej Ruszczynski working with Markku Kallio (part-time), Vladimir Norkin (part time), Georg Pflug (part-time), Charles Rosa (part-time). If the diverse applied activities planned in the project are to be carried out, the project should be increased to the equivalent of three full-time staff members. In addition to working with the ECS Project, collaboration is foreseen with the Water Resources Project, on water quality management under uncertainty; with the Transboundary Air Pollution Project on investment planning in emission control; and with the Risk, Policy and Complexity Project on allocating indivisible resources under uncertainty. External collaboration will continue with Jitka Dupacova, Charles University, Prague (on economic applications); R. Tyrell Rockafellar, University of Washington, Seattle (on sparse linking structures); with Werner Roemisch, Humbolt University, Berlin (on approximations to stochastic optimization problems); and with Roger J.B. Wets, University of California, Davis (on finite scenario approximations);