Barycentric scenario trees in convex multistage stochastic programming

This work deals with the approximation of convex stochastic multistage programs allowing prices and demand to be stochastic with compact support. Based on earlier results, sequences of barycentric scenario trees with associated probability trees are derived for minorizing and majorizing the given problem. Error bounds for the optimal policies of the approximate problem and duality analysis with respect to the stochastic data determine the scenarios which improve the approximation. Convergence of the approximate solutions is proven under the stated assumptions. Preliminary computational results are outlined. This work has been supported by Schweizerischen Nationalfonds Grant Nr. 21-39 575.93.     

Aggregation and discretization in multistage stochastic programming

Multistage stochastic programs have applications in many areas and support policy makers in finding rational decisions that hedge against unforeseen negative events. In order to ensure computational tractability, continuous-state stochastic programs are usually discretized; and frequently, the curse of dimensionality dictates that decision stages must be aggregated. In this article we construct two discrete, stage-aggregated stochastic programs which provide upper and lower bounds on the optimal value of the original problem. The approximate problems involve finitely many decisions and constraints, thus principally allowing for numerical solution.      

Multistage stochastic convex programs: Duality and its implications

In this paper, we study alternative primal and dual formulations of multistage stochastic convex programs (SP). The alternative dual problems which can be traced to the alternative primal representations, lead to stochastic analogs of standard deterministic constructs such as conjugate functions and Lagrangians. One of the by-products of this approach is that the development does not depend on dynamic programming (DP) type recursive arguments, and is therefore applicable to problems in which the objective function is non-separable (in the DP sense). Moreover, the treatment allows us to handle both continuous and discrete random variables with equal ease. We also investigate properties of the expected value of perfect information (EVPI) within the context of SP, and the connection between EVPI and nonanticipativity of optimal multipliers. Our study reveals that there exist optimal multipliers that are nonanticipative if, and only if, the EVPI is zero. Finally, we provide interpretations of the retroactive nature of the dual multipliers. This work was supported by NSF grant DMII-9414680.     

A stochastic programming model for asset liability management of a Finnish pension company

This paper describes a stochastic programming model that was developed for asset liability management of a Finnish pension insurance company. In many respects the model resembles those presented in the literature, but it has some unique features stemming from the statutory restrictions for Finnish pension insurance companies. Particular attention is paid to modeling the stochastic factors, numerical solution of the resulting optimization problem and evaluation of the solution. Out-of-sample tests clearly favor the strategies suggested by our model over static fixed-mix and dynamic portfolio insurance strategies. Financial support from the Foundation for the Helsinki School of Economics under grants number 9981114 and 9981117 for P. Hilli and M. Koivu is gratefully acknowledged. The work of T. Pennanen was supported by Finnish Academy under contract no. 3385     

Star-shaped approximation approach for stochastic programming problems with probability function

Star-shaped probability function approximation is suggested. Conditions of log-concavity and differentiability of approximation function are obtained. The method for constructing stochastic estimates of approximation function gradient and stochastic quasi-gradient algorithm for probability function maximization are described in the paper     

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     

The Expected loss in the discretization of multistage stochastic programming problems—estimation and convergence rate

In the present paper, the approximate computation of a multistage stochastic programming problem (MSSPP) is studied. First, the MSSPP and its discretization are defined. Second, the expected loss caused by the usage of the “approximate” solution instead of the “exact” one is studied. Third, new results concerning approximate computation of expectations are presented. Finally, the main results of the paper—an upper bound of the expected loss and an estimate of the convergence rate of the expected loss—are stated.     

Analysis of stochastic dual dynamic programming method

In this paper we discuss statistical properties and convergence of the Stochastic Dual Dynamic Programming (SDDP) method applied to multistage linear stochastic programming problems. We assume that the underline data process is stagewise independent and consider the framework where at first a random sample from the original (true) distribution is generated and consequently the SDDP algorithm is applied to the constructed Sample Average Approximation (SAA) problem. Then we proceed to analysis of the SDDP solutions of the SAA problem and their relations to solutions of the “true” problem. Finally we discuss an extension of the SDDP method to a risk averse formulation of multistage stochastic programs. We argue that the computational complexity of the corresponding SDDP algorithm is almost the same as in the risk neutral case.     

Integrating stochastic programming and decision tree techniques in land conversion problems

This paper is concerned with gradual land conversion problems, placing the main focus on the interaction between time and uncertainty. This aspect is extremely relevant since most decisions made in the field of natural resources and sustainable development are irreversible decisions. In particular, we discuss and develop a scenario-based multi-stage stochastic programming model in order to determine the optimal land portfolio in time, given uncertainty affecting the market. The approach is then integrated in a decision tree framework in order to account for domain specific (environmental) uncertainty that, diversely from market uncertainty, may depend on the decision taken. Although, the designed methodology has many general applications, in the present work we focus on a particular case study, concerning a semi-degraded natural park located in northern Italy.     

A stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

On the role of bounds in stochastic linear programming

Stochastic linear programming (SLP) models involve multivariate integrals. Although in the discretely distributed case these integrals become sums they typically contain a large amount of terms. The purpose of this paper is twofold:On the one hand we discuss the usage of bounds concerning integrals for constructing SLP algorithms and secondly we point out the role of bounds-based algorithms for solving SLP problems. The conceptual considerations are demonstrated in the last section by computational results. The tests have been carried out by utilizing SLP-IOR, our model management system for SLP     

Asymptotic analysis for a stochastic semidefinite programming

Stochastic semidefinite programming (SSDP) is a new class of optimization problems with a wide variety of applications. In this article, asymptotic analysis results of sample average approximation estimator for SSDP are established. Asymptotic analysis result already existing for stochastic nonlinear programming is extended to SSDP, that is, the conditions ensuring the convergence in distribution of sample average approximation estimator for SSDP to a multivariate normal are obtained and the corresponding covariance matrix is described in a closed form.     

Finite-stage stochastic decision processes with recursive reward structure I: optimality equations and deterministic strategies

In this paper we examine an N-stage stochastic decision model with a recursive reward structure whose state and action spaces are standard Borel ones. The central results relate to the validity of the optimality equations and to the sufficiency of deterministic strategies. The results expand statements known for classical dynamic programming problems with additive total rewards to a wide class of recursive reward functions under certain monotonicity and continuity assumptions. The existence of an expected utility representation of the total rewards is generally not presupposed     

An aggregate stochastic programming model for air traffic flow management

In this paper, we present an aggregate mathematical model for air traffic flow management (ATFM), a problem of great concern both in Europe and in the United States. The model extends previous approaches by simultaneously taking into account three important issues: (i) the model explicitly incorporates uncertainty in the airport capacities; (ii) it also considers the trade-off between airport arrivals and departures, which is a crucial issue in any hub airport; and (iii) it takes into account the interactions between different hubs.The level of aggregation proposed for the mathematical model allows us to solve realistic size instances with a commercial solver on a PC. Moreover it allows us to compute solutions which are perfectly consistent with the Collaborative Decision-Making (CDM) procedure in ATFM, widely adopted in the USA and which is currently receiving a lot of attention in Europe. In fact, the proposed model suggests the number of flights that should be delayed, a decision that belongs to the ATFM Authority, rather than assigning delays to individual aircraft.     

Error bounds for the aggregated convex programming problem

Applied mathematical programming problems are often approximations of larger, more detailed problems. One criterion to evaluate an approximating program is the magnitude of the difference between the optimal objective values of the original and the approximating program. The approximation we consider is variable aggregation in a convex program. Bounds are derived on the difference between the two optimal objective values. Previous results of Geoffrion and Zipkin are obtained by specializing our results to linear programming. Also, we apply our bounds to a convex transportation problem. Thanks are due to Ron Dembo, Paul Zipkin and the referees for valuable comments. This research was supported by NSF Grant ENG-76-15599.     

Solution approaches for the multiobjective stochastic programming

We survey in this paper various solution approaches for multiobjective stochastic problems where random variables can be in both objectives and constraints parameters. Once a problem requires a stochastic formulation, a first step consists in transforming the problem into its deterministic formulation. We propose to classify and evaluate such transformations with regards to the many proposed concepts of efficiency. The paper addresses also some applications of the multiobjective stochastic programming models.     

Weak approximation of the stochastic wave equation

We investigate the accuracy of approximation of E[φ(u(t))], where {u(t):t∈[0,∞)} is the solution of the stochastic wave equation driven by the space-time white noise and φ is an R-valued function defined on the Hilbert space L²(R). The approximation is done by the leap-frog scheme. We show that, under certain conditions on φ, the approximation by the leap-frog scheme is of order two.     

On statistical sensitivity analysis in stochastic programming

Different approaches to statistical sensitivity analysis for optimal solutions of stochastic programs are discussed and compared. Possibilities of drawing conclusions about asymptotic behavior of estimated optimal solutions by means of stability properties of auxiliary randomly perturbed convex quadratic programs are indicated and illustrated on a numerical example.     

Stability results for stochastic programming problems

The paper deals with a statistical approach to stability analysis in nonlinear stochastic programming. Firstly the distribution function of the underlying random variable is estimated by the empirical distribution function, and secondly the problem of estimated parameters is considered. In both the cases the probability that the solution set of the approximate problem, is not contained in an l-neighbourhood of the solution set to the original problem is estimated, and under differentiability properties an asymptotic expansion for the density of the (unique) solution to the approximate problem is derived.     

Mslip: A computer code for the multistage stochastic linear programming problem

This paper describes an efficient implementation of a nested decomposition algorithm for the multistage stochastic linear programming problem. Many of the computational tricks developed for deterministic staircase problems are adapted to the stochastic setting and their effect on computation times is investigated. The computer code supports an arbitrary number of time periods and various types of random structures for the input data. Numerical results compare the performance of the algorithm to MINOS 5.0.