Scenario tree reduction for multistage stochastic programs

A framework for the reduction of scenario trees as inputs of (linear) multistage stochastic programs is provided such that optimal values and approximate solution sets remain close to each other. The argument is based on upper bounds of the L _r -distance and the filtration distance, and on quantitative stability results for multistage stochastic programs. The important difference from scenario reduction in two-stage models consists in incorporating the filtration distance. An algorithm is presented for selecting and removing nodes of a scenario tree such that a prescribed error tolerance is met. Some numerical experience is reported.     

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.     

Quantitative stability of fully random mixed-integer two-stage stochastic programs

Mixed-integer two-stage stochastic programs with fixed recourse matrix, random recourse costs, technology matrix, and right-hand sides are considered. Quantitative continuity properties of its optimal value and solution set are derived when the underlying probability distribution is perturbed with respect to an appropriate probability metric.     

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.     

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.     

Challenges in stochastic programming

Remarkable progress has been made in the development of algorithmic procedures and the availability of software for stochastic programming problems. However, some fundamental questions have remained unexplored. This paper identifies the more challenging open questions in the field of stochastic programming. Some are purely technical in nature, but many also go to the foundations of designing models for decision making under uncertainty. Research supported by grants of the National Science Foundation and the US-Israel Binational Science Foundation.     

An algorithm for stochastic programs with first-order dominance constraints induced by linear recourse

We derive a cutting plane decomposition method for stochastic programs with first-order dominance constraints induced by linear recourse models with continuous variables in the second stage.     

IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation

We present a new method for solving stochastic programs with joint chance constraints with random technology matrices and discretely distributed random data. The problem can be reformulated as a large-scale mixed 0–1 integer program. We derive a new class of optimality cuts called IIS cuts and apply them to our problem. The cuts are based on irreducibly infeasible subsystems (IIS) of an LP defined by requiring that all scenarios be satisfied. We propose a method for improving the upper bound of the problem when no cut can be found. We derive and implement a branch-and-cut algorithm based on IIS cuts, and refer to this algorithm as the IIS branch-and-cut algorithm. We report on computational results with several test instances from optimal vaccine allocation. The computational results are promising as the IIS branch-and-cut algorithm gives better results than a state-of-the-art commercial solver on one class of problems.     

Stochastically weighted stochastic dominance concepts with an application in capital budgeting

The problem of comparing random vectors arises in many applications. We propose three new concepts of stochastically weighted dominance for comparing random vectors X and Y. The main idea is to use a random vector V to scalarize X and Y   as V^TX$V^{T}X$ and V^TY$V^{T}Y$, and subsequently use available concepts from stochastic dominance and stochastic optimization for comparison. For the case where the distributions of X, Y and V have finite support, we give (mixed-integer) linear inequalities that can be used for random vector comparison as well as for modeling of optimization problems where one of the random vectors depends on decisions to be optimized. Some advantages of the proposed new concepts are illustrated with the help of a capital budgeting example.     

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.     

A simulation-based approach to two-stage stochastic programming with recourse

In this paper we consider stochastic programming problems where the objective function is given as an expected value function. We discuss Monte Carlo simulation based approaches to a numerical solution of such problems. In particular, we discuss in detail and present numerical results for two-stage stochastic programming with recourse where the random data have a continuous (multivariate normal) distribution. We think that the novelty of the numerical approach developed in this paper is twofold. First, various variance reduction techniques are applied in order to enhance the rate of convergence. Successful application of those techniques is what makes the whole approach numerically feasible. Second, a statistical inference is developed and applied to estimation of the error, validation of optimality of a calculated solution and statistically based stopping criteria for an iterative alogrithm. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by CNPq (Conselho Nacional de Desenvolvimento Científico e Tecnológico), Brasília, Brazil, through a Doctoral Fellowship under grant 200595/93-8.     

A stochastic programming approach for multi-period portfolio optimization

This paper extends previous work on the use of stochastic linear programming to solve life-cycle investment problems. We combine the feature of asset return predictability with practically relevant constraints arising in a life-cycle investment context. The objective is to maximize the expected utility of consumption over the lifetime and of bequest at the time of death of the investor. Asset returns and state variables follow a first-order vector auto-regression and the associated uncertainty is described by discrete scenario trees. To deal with the long time intervals involved in life-cycle problems we consider a few short-term decisions (to exploit any short-term return predictability), and incorporate a closed-form solution for the long, subsequent steady-state period to account for end effects.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

A geometric way to build strong mixed-integer programming formulations

We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an $r$-dimensional linear space. The resulting MIP formulation is ideal, and uses exactly $r$ integer variables and $2\times \left(\#\text{of spanning hyperplanes}\right)$ general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and structures appearing in robotics and power systems problems.     

A stochastic programming approach to cash management in banking

The treasurer of a bank is responsible for the cash management of several banking activities. In this work, we focus on two of them: cash management in automatic teller machines (ATMs), and in the compensation of credit card transactions. In both cases a decision must be taken according to a future customers demand, which is uncertain. From historical data we can obtain a discrete probability distribution of this demand, which allows the application of stochastic programming techniques. We present stochastic programming models for each problem. Two short-term and one mid-term models are presented for ATMs. The short-term model with fixed costs results in an integer problem which is solved by a fast (i.e. linear running time) algorithm. The short-term model with fixed and staircase costs is solved through its MILP equivalent deterministic formulation. The mid-term model with fixed and staircase costs gives rise to a multi-stage stochastic problem, which is also solved by its MILP deterministic equivalent. The model for compensation of credit card transactions results in a closed form solution. The optimal solutions of those models are the best decisions to be taken by the bank, and provide the basis for a decision support system.     

Decomposition methods in stochastic programming

Stochastic programming problems have very large dimension and characteristic structures which are tractable by decomposition. We review basic ideas of cutting plane methods, augmented Lagrangian and splitting methods, and stochastic decomposition methods for convex polyhedral multi-stage stochastic programming problems.     

Convexity of chance constraints with independent random variables

We investigate the convexity of chance constraints with independent random variables. It will be shown, how concavity properties of the mapping related to the decision vector have to be combined with a suitable property of decrease for the marginal densities in order to arrive at convexity of the feasible set for large enough probability levels. It turns out that the required decrease can be verified for most prominent density functions. The results are applied then, to derive convexity of linear chance constraints with normally distributed stochastic coefficients when assuming independence of the rows of the coefficient matrix.     

Relaxations of linear programming problems with first order stochastic dominance constraints

Linear stochastic programming problems with first order stochastic dominance (FSD) constraints are non-convex. For their mixed 0-1 linear programming formulation we present two convex relaxations based on second order stochastic dominance (SSD). We develop necessary and sufficient conditions for FSD, used to obtain a disjunctive programming formulation and to strengthen one of the SSD-based relaxations.     

Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations

This paper is concerned with the problem of assigning employees to gas stations owned by the Kuwait National Petroleum Corporation (KNPC), which hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. Although similar employee scheduling problems have been addressed in the literature, certain peculiarities of the problem require novel mathematical models and algorithms to deal with the specific nature and size of this problem. The problem is modeled as a mixed-integer program, and a problem size analysis based on real data reveals that the formulation is too complex to solve directly. Hence, a two-stage approach is proposed, where the first stage assigns employees to stations, and the second stage specifies shifts and off-days for each employee. Computational results related to solving the two-stage models directly via CPLEX and by specialized heuristics are reported. The two-stage approach provides daily schedules for employees for a given time horizon in a timely fashion, taking into consideration the employees’ expressed preferences. This proposed modeling approach can be incorporated within a decision support system to replace the current manual scheduling practice that is often chaotic and has led to feelings of bias and job dissatisfaction among employees.     

A numerical method for solving stochastic programming problems with moment constraints on a distribution function

The stochastic programming problem is considered in the case of a distribution function with partially known random parameters. A minimax approach is taken, and a numerical method is proposed for problems when information on the distribution function can be expressed in the form of finitely many moment constraints. Convergence is proved and results of numerical experiments are reported.