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.     

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.     

A note on scenario reduction for two-stage stochastic programs

We extend earlier work on scenario reduction by relying directly on Fortet-Mourier metrics instead of using upper bounds given in terms of mass transportation problems. The importance of Fortet-Mourier metrics for quantitative stability of two-stage models is reviewed and some numerical results are also provided.     

Scenario reduction in stochastic programming with respect to discrepancy distances

Discrete approximations to chance constrained and mixed-integer two-stage stochastic programs require moderately sized scenario sets. The relevant distances of (multivariate) probability distributions for deriving quantitative stability results for such stochastic programs are ℬ-discrepancies, where the class ℬ of Borel sets depends on their structural properties. Hence, the optimal scenario reduction problem for such models is stated with respect to ℬ-discrepancies. In this paper, upper and lower bounds, and some explicit solutions for optimal scenario reduction problems are derived. In addition, we develop heuristic algorithms for determining nearly optimally reduced probability measures, discuss the case of the cell discrepancy (or Kolmogorov metric) in some detail and provide some numerical experience.     

Airline network revenue management by multistage stochastic programming

A multistage stochastic programming approach to airline network revenue management is presented. The objective is to determine seat protection levels for all itineraries, fare classes, points of sale of the airline network and all dcps of the booking horizon such that the expected revenue is maximized. While the passenger demand and cancelation rate processes are the stochastic inputs of the model, the stochastic protection level process represents its output and allows to control the booking process. The stochastic passenger demand and cancelation rate processes are approximated by a finite number of tree structured scenarios. The scenario tree is generated from historical data using a stability-based recursive scenario reduction scheme. Numerical results for a small hub-and-spoke network are reported. This research is supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

Partially observable multistage stochastic programming

We propose a class of partially observable multistage stochastic programs and describe an algorithm for solving this class of problems. We provide a Bayesian update of a belief-state vector, extend the stochastic programming formulation to incorporate the belief state, and characterize saddle-function properties of the corresponding cost-to-go function. Our algorithm is a derivative of the stochastic dual dynamic programming method.     

The value of the stochastic solution in multistage problems

We generalize the definition of the bounds for the optimal value of the objective function for various deterministic equivalent models in multistage stochastic programs. The parameters EVPI and VSS were introduced for two-stage models. The parameter EVPI, the expected value of perfect information, measures how much it is reasonable to pay to obtain perfect information about the future. The parameter VSS, the value of the stochastic solution, allows us to obtain the goodness of the expected solution value when the expected values are replaced by the random values for the input variables. We extend the definition of these parameters to the multistage stochastic model and prove a similar chain of inequalities with the lower and upper bounds depending substantially on the structure of the problem. This research has been partially supported by the grants, 1/BBVA 00038.16421/2004 from Fundación BBVA, SEJ2005-05549/ECON from Ministerio de Educación y Ciencia and the grant GRUPOS79/04 from the Generalitat Valenciana, Spain.     

Solving stochastic complementarity problems in energy market modeling using scenario reduction

In this paper, we analyze market equilibrium models with random aspects that lead to stochastic complementarity problems. While the models presented depict energy markets, the results are believed to be applicable to more general stochastic complementarity problems. The contribution is the development of new heuristic, scenario reduction approaches that iteratively work towards solving the full, extensive form, stochastic market model. The methods are tested on three representative models and supporting numerical results are provided as well as derived mathematical bounds.     

Quantitative stability of multistage stochastic programs via calm modifications

In this paper, we revisit the quantitative stability of multistage stochastic programs. Different from the single calm modification used in Küchler (2008), we introduce two types of calm modifications which leads to a much simpler proof and tighter upper bound for the difference of optimal values of multistage stochastic programs under different stochastic processes than those of Küchler (2008). In addition, we avoid those restrictive assumptions in Küchler (2008) and the filtration distance in Heitsch et al. (2006). Finally, we illustrate our results with two numerical examples.     

A general framework for multistage mean-variance post-tax optimization

An investor’s decisions affect the way taxes are paid in a general portfolio investment, modifying the net redemption value and the yearly optimal portfolio distribution. We investigate the role of these decisions on multistage mean-variance portfolio allocation model. A number of risky assets grouped in wrappers with special taxation rules is integrated in a multistage financial portfolio optimization problem. The uncertainty on the returns of assets is specified as a scenario tree generated by simulation/clustering based approach. We show the impact of decisions in the yearly reallocation of the investments for three typical cases with an annual fixed withdrawal in a fixed horizon that utilizes completely the option of taper relief offered by banks in UK. Our computational framework can be used as a tool for testing decisions in this context.     

On augmented Lagrangian decomposition methods for multistage stochastic programs

A general decomposition framework for large convex optimization problems based on augmented Lagrangians is described. The approach is then applied to multistage stochastic programming problems in two different ways: by decomposing the problem into scenarios and by decomposing it into nodes corresponding to stages. Theoretical convergence properties of the two approaches are derived and a computational illustration is presented.     

Clustering algorithms for scenario tree generation: Application to natural hydro inflows

In stochastic optimization problems, uncertainty is normally represented by means of a scenario tree. Finding an accurate representation of this uncertainty when dealing with a set of historical series is an important issue, because of its influence in the results of the above mentioned problems. This article uses a procedure to create the scenario tree divided into two phases: the first one produces a tree that represents accurately the original probability distribution, and in the second phase that tree is reduced to make it tractable. Several clustering methods are analysed and proposed in the paper to obtain the scenario tree. Specifically, these are applied to an academic case and to natural hydro inflows series, and comparisons amongst them are established according to these results.     

On complexity of multistage stochastic programs under heavy tailed distributions

In this paper, the complexity of sample average approximation (SAA) of multistage stochastic programs under heavy tailed distributions is investigated. Specifically, we estimate confidence levels when the accuracy parameter and sample size are given under independently and identically distributed (iid) and non-iid conditional samples, respectively. Different from the existing works, we emphasize the impact of heavy tailed distributions, non-iid conditional sampling and stages dependence of the random process in multistage stochastic programs.     

On complexity of multistage stochastic programs

In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self-contained and is based on a relatively elementary, one-dimensional, Cramér's Large Deviations Theorem.     

Postoptimality for multistage stochastic linear programs

The contamination technique is presented as a flexible and relatively easily tractable tool to postoptimality analysis for scenario based multistage stochastic linear programs. It is promising especially in cases when the influence of additional or out-of-sample scenarios on the already solved problem is to be explored.Research supported in part by the Grant Agency of the Czech Republic under Grant No. 402/93/0631.     

Cut sharing for multistage stochastic linear programs with interstage dependency

Multistage stochastic programs with interstage independent random parameters have recourse functions that do not depend on the state of the system. Decomposition-based algorithms can exploit this structure by sharing cuts (outer-linearizations of the recourse function) among different scenario subproblems at the same stage. The ability to share cuts is necessary in practical implementations of algorithms that incorporate Monte Carlo sampling within the decomposition scheme. In this paper, we provide methodology for sharing cuts in decomposition algorithms for stochastic programs that satisfy certain interstage dependency models. These techniques enable sampling-based algorithms to handle a richer class of multistage problems, and may also be used to accelerate the convergence of exact decomposition algorithms. Research leading to this work was partially supported by the Department of Energy Contract DE-FG03-92ER25116-A002; the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089; and the Electric Power Research Institute Contract RP 8010-09, CSA-4O05335. This author's work was supported in part by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Inference of statistical bounds for multistage stochastic programming problems

We discuss in this paper statistical inference of sample average approximations of multistage stochastic programming problems. We show that any random sampling scheme provides a valid statistical lower bound for the optimal (minimum) value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. We also indicate that fixing a feasible first-stage solution and then solving the sampling approximation of the corresponding (T–1)-stage problem, does not give a valid statistical upper bound for the optimal value of the true problem.Supported, in part, by the National Science Foundation under grant DMS-0073770.     

Nested decomposition of multistage nonlinear programs with recourse

Nested decomposition is extended to the case of arborescent nonlinear programs. Duals of extensive forms of nonlinear multistage stochastic programs constitute a particular class of those problems; the method is tested on a set of problems of that type.     

Test problems in stochastic multistage programming

This paper provides a set of stochastic multistage programs where the evolvement of uncertain factors is given by stochastic processes. We treat a practical problem statement within the field of managing fixed-income securities. Detailed information on the used parameter values in various interest rate models is given. Barycentric approximation is applied to obtain computational results; different measures of the achieved goodness of approximation are indicated     

Scenario tree generation and multi-asset financial optimization problems

We compare two popular scenario tree generation methods in the context of financial optimization: moment matching and scenario reduction. Using a simple problem with a known analytic solution, moment matching–when ensuring absence of arbitrage–replicates this solution precisely. On the other hand, even if the scenario trees generated by scenario reduction are arbitrage-free, the solutions are biased and highly variable. These results hold for correlated and uncorrelated asset returns, as well as for normal and non-normal returns.