Problem-based optimal scenario generation and reduction in stochastic programming

Scenarios are indispensable ingredients for the numerical solution of stochastic programs. Earlier approaches to optimal scenario generation and reduction are based on stability arguments involving distances of probability measures. In this paper we review those ideas and suggest to make use of stability estimates based only on problem specific data. For linear two-stage stochastic programs we show that the problem-based approach to optimal scenario generation can be reformulated as best approximation problem for the expected recourse function which in turn can be rewritten as a generalized semi-infinite program. We show that the latter is convex if either right-hand sides or costs are random and can be transformed into a semi-infinite program in a number of cases. We also consider problem-based optimal scenario reduction for two-stage models and optimal scenario generation for chance constrained programs. Finally, we discuss problem-based scenario generation for the classical newsvendor problem.

     

Scenario generation and stochastic programming models for asset liability management

In this paper, we develop and test scenario generation methods for asset liability management models. We propose a multi-stage stochastic programming model for a Dutch pension fund. Both randomly sampled event trees and event trees fitting the mean and the covariance of the return distribution are used for generating the coefficients of the stochastic program. In order to investigate the performance of the model and the scenario generation procedures we conduct rolling horizon simulations. The average cost and the risk of the stochastic programming policy are compared to the results of a simple fixed mix model. We compare the average switching behavior of the optimal investment policies. Our results show that the performance of the multi-stage stochastic program could be improved drastically by choosing an appropriate scenario generation method.     

Stochastic network optimization models for investment planning

We describe and compare stochastic network optimization models for investment planning under uncertainty. Emphasis is placed on multiperiod a sset allocation and active portfolio management problems. Myopic as well as multiple period models are considered. In the case of multiperiod models, the uncertainty in asset returns filters into the constraint coefficient matrix, yielding a multi-scenario program formulation. Different scenario generation procedures are examined. The use of utility functions to reflect risk bearing attitudes results in nonlinear stochastic network models. We adopt a newly proposed decomposition procedure for solving these multiperiod stochastic programs. The performance of the models in simulations based on historical data is discussed.Research partially supported by National Science Foundation Grant No. DCR-861-4057 and IBM Grant No. 5785. Also, support from Pacific Financial Companies is gratefully acknowledged.     

Parameter estimation in stochastic scenario generation systems

Scenario analysis offers an effective tool for addressing the stochastic elements in multi-period financial planning models. Critical to any scenario generation process is the estimation of the input parameters of the underlying stochastic model for economic factors. In this paper, we propose a new approach for estimation, known as the integrated parameter estimation (IPE). This approach combines the significant features of other well-known estimation techniques within a non-convex multiple objective optimization framework, with the objective weights controlling the relative importance of the features. We solve the non-convex optimization problem using adaptive memory programming – a variation of tabu search. Based on a short interest rate model using UK treasury rates from 1980 to 1995, the integrated approach compares favorably with maximum likelihood and the generalized method of moments. We also evaluate performance with Towers Perrin's CAP:Link scenario generation system.     

Stability Properties of a Bond Portfolio Management Problem

The bond portfolio management problem is formulated as a multiperiod two-stage or multistage stochastic program based on interest rate scenarios. These scenarios depend on the available market data, on the applied estimation and sampling techniques, etc., and are used to evaluate coefficients of the resulting large scale mathematical program. The aim of the contribution is to analyze stability and sensitivity of this program on small changes of the coefficients – the (scenario dependent) values of future interest rates and prices. We shall prove that under sensible assumptions, the scenario subproblems are stable linear programs and that also the optimal first-stage decisions and the optimal value of the considered stochastic program possess acceptable continuity properties.     

Solution sensitivity-based scenario reduction for stochastic unit commitment

A two-stage stochastic program is formulated for day-ahead commitment of thermal generating units to minimize total expected cost considering uncertainties in the day-ahead load and the availability of variable generation resources. Commitments of thermal units in the stochastic reliability unit commitment are viewed as first-stage decisions, and dispatch is relegated to the second stage. It is challenging to solve such a stochastic program if many scenarios are incorporated. A heuristic scenario reduction method termed forward selection in recourse clusters (FSRC), which selects scenarios based on their cost and reliability impacts, is presented to alleviate the computational burden. In instances down-sampled from data for an Independent System Operator in the US, FSRC results in more reliable commitment schedules having similar costs, compared to those from a scenario reduction method based on probability metrics. Moreover, in a rolling horizon study, FSRC preserves solution quality even if the reduction is substantial.     

Problem-driven scenario generation: an analytical approach for stochastic programs with tail risk measure

Mathematical Programming - Scenario generation is the construction of a discrete random vector to represent parameters of uncertain values in a stochastic program. Most approaches to scenario...     

Strategic financial risk management and operations research

Risk management has become a vital topic for financial institutions in the 1990s. Strategically, asset/liability management systems are important tools for controlling a firm's financial risks. They manage these risks by dynamically balancing the firm's asset and liabilities to achieve the firm's objectives. We discuss such leading international firms as Towers Perrin, Frank Russell, and Falcon Asset Management, which apply asset/liability management for efficiently managing risk over extended time periods. Three components of asset/liability management are described: 1) a multi-stage stochastic program for coordinating the asset/liability decisions; 2) a scenario generation procedure for modeling the stochastic parameters; and 3) solution algorithms for solving the resulting large-scale optimization problem.     

Adaptive discretization of convex multistage stochastic programs

We propose a new scenario tree reduction algorithm for multistage stochastic programs, which integrates the reduction of a scenario tree into the solution process of the stochastic program. This allows to construct a scenario tree that is highly adapted on the optimization problem. The algorithm starts with a rough approximation of the original tree and locally refines this approximation as long as necessary. Promising numerical results for scenario tree reductions in the settings of portfolio management and power management with uncertain load are presented.     

PySP: modeling and solving stochastic programs in Python

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simultaneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM’s COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves passing an extensive form to a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets’ Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multi-stage stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.     

Multistage stochastic demand-side management for price-making major consumers of electricity in a co-optimized energy and reserve market

In this paper, we take an optimization-driven heuristic approach, motivated by dynamic programming, to solve a class of non-convex multistage stochastic optimization problems. We apply this to the problem of optimizing the timing of energy consumption for a large manufacturer who is a price-making major consumer of electricity. We introduce a mixed-integer program that co-optimizes consumption bids and interruptible load reserve offers, for such a major consumer over a finite time horizon. By utilizing Lagrangian methods, we decompose our model through approximately pricing the constraints that link the stages together. We construct look-up tables in the form of consumption-utility curves, and use these to determine optimal consumption levels. We also present heuristics, in order to tackle the non-convexities within our model, and improve the accuracy of our policies. In the second part of the paper, we present stochastic solution methods for our model in which, we reduce the size of the scenario tree by utilizing a tailor-made scenario clustering method. Furthermore, we report on a case study that implements our models for a major consumer in the (full) New Zealand Electricity Market and present numerical results.     

Second-order scenario approximation and refinement in optimization under uncertainty

When solving scenario-based stochastic programming problems, it is imperative that the employed solution methodology be based on some form of problem decomposition: mathematical, stochastic, or scenario decomposition. In particular, the scenario decomposition resulting from scenario approximations has perhaps the least tendency to be computationally tedious due to increases in the number of scenarios. Scenario approximations discussed in this paper utilize the second-moment information of the given scenarios to iteratively construct a (relatively) small number of representative scenarios that are used to derive bounding approximations on the stochastic program. While the sizes of these approximations grow only linearly in the number of random parameters, their refinement is performed by exploiting the behavior of the value function in the most effective manner. The implementation SMART discussed here demonstrates the aptness of the scheme for solving two-stage stochastic programs described with a large number of scenarios.This paper was presented at the IFIP Workshop onStochastic Programming: Algorithms and Models, Lillehammer, Norway, January 1994.     

A dual strategy for the implementation of the aggregation principle in decision making under uncertainty

A solution method for stochastic programs is proposed based on the aggregation principle, which allows one to find the solution of a stochastic program by aggregating the solutions of individual deterministic scenario problems. The method concentrates on finding good estimates of the dual variables associated with the non-anticipativity constraints.     

Scenario tree modeling for multistage stochastic programs

An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, we develop (stability) theory-based heuristics for generating scenario trees out of an initial set of scenarios. They are based on forward or backward algorithms for tree generation consisting of recursive scenario reduction and bundling steps. Conditions are established implying closeness of optimal values of the original process and its tree approximation, respectively, by relying on a recent stability result in Heitsch, Römisch and Strugarek (SIAM J Optim 17:511–525, 2006) for multistage stochastic programs. Numerical experience is reported for constructing multivariate scenario trees in electricity portfolio management.     

Knowledge‐based scenario tree generation methods and application in multiperiod portfolio selection problem

A scenario tree is an efficient way to represent a stochastic data process in decision problems under uncertainty. This paper addresses how to efficiently generate appropriate scenario trees. A knowledge‐based scenario tree generation method is proposed; the new method is further improved by accounting for subjective judgements or expectations about the random future. Compared with existing approaches, complicated mathematical models and time‐consuming estimation, simulation and optimization problem solution are avoided in our knowledge‐based algorithms, and large‐scale scenario trees can be quickly generated. To show the advantages of the new algorithms, a multiperiod portfolio selection problem is considered, and a dynamic risk measure is adopted to control the intermediate risk, which is superior to the single‐period risk measure used in the existing literature. A series of numerical experiments are carried out by using real trading data from the Shanghai stock market. The results show that the scenarios generated by our algorithms can properly represent the underlying distribution; our algorithms have high performance, say, a scenario tree with up to 10,000 scenarios can be generated in less than a half minute. The applications in the multiperiod portfolio management problem demonstrate that our scenario tree generation methods are stable, and the optimal trading strategies obtained with the generated scenario tree are reasonable, efficient and robust. Copyright © 2013 John Wiley & Sons, Ltd.     

A mixed integer programming model for multistage mean–variance post-tax optimization

In this paper, we introduce a mixed integer stochastic programming approach to mean–variance post-tax portfolio management. This approach takes into account of risk in a multistage setting and allows general withdrawals from original capital. The uncertainty on asset returns is specified as a scenario tree. The risk across scenarios is addressed using the probabilistic approach of classical stochastic programming. The tax rules are used with stochastic linear and mixed integer quadratic programming models to compute an overall tax and return-risk efficient multistage portfolio. The incorporation of the risk term in the model provides robustness and leads to diversification over wrappers and assets within each wrapper. General withdrawals and risk aversion have an impact on the distribution of assets among wrappers. Computational results are presented using a study with different scenario trees in order to show the performance of these models.     

On multistage Stochastic Integer Programming for incorporating logical constraints in asset and liability management under uncertainty

We present a model for optimizing a mean-risk function of the terminal wealth for a fixed income asset portfolio restructuring with uncertainty in the interest rate path and the liabilities along a given time horizon. Some logical constraints are considered to be satisfied by the assets portfolio. Uncertainty is represented by a scenario tree and is dealt with by a multistage stochastic mixed 0-1 model with complete recourse. The problem is modelled as a splitting variable representation of the Deterministic Equivalent Model for the stochastic model, where the 0-1 variables and the continuous variables appear at any stage. A Branch-and-Fix Coordination approach for the multistage 0–1 program solving is proposed. Some computational experience is reported.      

Real options valuation of forest plantation investments in Brazil

In this paper, we consider investments in eucalyptus plantations in Brazil. For such projects, we discuss real options valuation in the place conventional methods such as IRR or NPV, possibly with CAPM. Traditionally, real options valuation assumes complete markets and neglects market imperfections. Yet, market frictions, such as transaction costs, interest rate spreads, and restricted short positions, can play an important role. We extend real options valuation to allow incomplete and imperfect markets. The value is obtained as a competitive price, given markets of competing investment opportunities, such as real and financial assets. Under perfect and complete markets, such valuation method is consistent with conventional real options theory. Stochastic programming and standard software is used for valuation of eucalyptus plantations. We estimate the underlying interdependent diffusion processes of stock market, interest rates, exchange rates and pulpwood price, and derive novel expressions of stochastic integrals to be employed in scenario generation for discrete time stochastic programming.     

Solving Sequences of Refined Multistage Stochastic Linear Programs

Multistage stochastic programs with continuous underlying distributions involve the obstacle of high-dimensional integrals where the integrands' values again are given by solutions of stochastic programs. A common solution technique consists of discretizing the support of the original distributions leading to scenario trees and corresponding LPs which are – up to a certain size – easy to solve. In order to improve the accuracy of approximation, successive refinements of the support result in rapidly expanding scenario trees and associated LPs. Hence, the solvability of the multistage stochastic program is limited by the numerical solvability of sequences of such expanding LPs. This work describes an algorithmic technique for solving the large-scale LP of refinement ν based on the solutions at the previous ν?1 refinements. Numerical results are presented for practical problem statements within financial applications demonstrating significant speedup (depending on the size of the LP instances).     

Scenario optimization

Uncertainty in the parameters of a mathematical program may present a modeller with considerable difficulties. Most approaches in the stochastic programming literature place an apparent heavy data and computational burden on the user and as such are often intractable. Moreover, the models themselves are difficult to understand. This probably explains why one seldom sees a fundamentally stochastic model being solved using stochastic programming techniques. Instead, it is common practice to solve a deterministic model with different assumed scenarios for the random coefficients. In this paper we present a simple approach to solving a stochastic model, based on a particular method for combining such scenario solutions into a single, feasible policy. The approach is computationally simple and easy to understand. Because of its generality, it can handle multiple competing objectives, complex stochastic constraints and may be applied in contexts other than optimization. To illustrate our model, we consider two distinct, important applications: the optimal management of a hydro-thermal generating system and an application taken from portfolio optimization.