The value of the stochastic solution in stochastic linear programs with fixed recourse

Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem.This paper is an extension of part of the author's dissertation in the Department of Operations Research, Stanford University, Stanford, California. The research was supported at Stanford by the Department of Energy under Contract DE-AC03-76SF00326, PA#DE-AT03-76ER72018, Office of Naval Research under Contract N00014-75-C-0267 and the National Science Foundation under Grants MCS76-81259, MCS-7926009 and ECS-8012974 (formerly ENG77-06761).     

Second order sensitivity analysis and asymptotic theory of parametrized nonlinear programs

In this paper we study second-order differential properties of an optimal-value function(x). It is shown that under certain conditions(x) possesses second-order directional derivatives, which can be calculated by solving corresponding quadratic programs. Also upper and lower bounds on these derivatives are introduced under weaker assumptions. In particular we show that the second-order directional derivative is infinite if the corresponding quadratic program is unbounded. Finally sensitivity results are applied to investigate asymptotics of estimators in parametrized nonlinear programs.     

Statistical approximations for recourse constrained stochastic programs

The two stage stochastic program with recourse is known to have numerous applications in financial planning, energy modeling, telecommunications systems etc. Notwithstanding its applicability, the two stage stochastic program is limited in its ability to incorporate a decision maker's attitudes towards risk. In this paper we present an extension via the inclusion of a recourse constraint. This results in a convex integrated chance constraint (ICC), which inherits the convexity properties of two stage programs. However, it also inherits some of the difficulties associated with the evaluation of recourse functions. This motivates our study of conditions that may be applicable to algorithms using statistical approximations of such ICC. We present a set of sufficient conditions that these approximations may satisfy in order to assure convergence. Our conditions are satisfied by a wide range of statistical approximations, and we demonstrate that these approximations can be generated within standard algorithmic procedures.This work was supported in part by Grant No. NSF-DDM-9114352 from the National Science Foundation.     

Sublinear upper bounds for stochastic programs with recourse

Separable sublinear functions are used to provide upper bounds on the recourse function of a stochastic program. The resulting problem's objective involves the inf-convolution of convex functions. A dual of this problem is formulated to obtain an implementable procedure to calculate the bound. Function evaluations for the resulting convex program only require a small number of single integrations in contrast with previous upper bounds that require a number of function evaluations that grows exponentially in the number of random variables. The sublinear bound can often be used when other suggested upper bounds are intractable. Computational results indicate that the sublinear approximation provides good, efficient bounds on the stochastic program objective value.This research has been partially supported by the National Science Foundation. The first author's work was also supported in part by Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Adaptive multicut aggregation for two-stage stochastic linear programs with recourse

Outer linearization methods for two-stage stochastic linear programs with recourse, such as the L-shaped algorithm, generally apply a single optimality cut on the nonlinear objective at each major iteration, while the multicut version of the algorithm allows for several cuts to be placed at once. In general, the L-shaped algorithm tends to have more major iterations than the multicut algorithm. However, the trade-offs in terms of computational time are problem dependent. This paper investigates the computational trade-offs of adjusting the level of optimality cut aggregation from single cut to pure multicut. Specifically, an adaptive multicut algorithm that dynamically adjusts the aggregation level of the optimality cuts in the master program, is presented and tested on standard large-scale instances from the literature. Computational results reveal that a cut aggregation level that is between the single cut and the multicut can result in substantial computational savings over the single cut method.     

Approximations to stochastic programs with complete fixed recourse

The probability distribution of the data entering a recourse problem is replaced by finite discrete distributions. It is proved that the convergence of the objective functions of the approximating problems to that one of the original problem can be achieved by choosing the discrete distributions in quite a natural way. For bounded feasible sets this implies the convergence of the optimal values. Finally some error bounds are derived.     

Statistical verification of optimality conditions for stochastic programs with recourse

Statistically motivated algorithms for the solution of stochastic programming problems typically suffer from their inability to recognize optimality of a given solution algorithmically. Thus, the quality of solutions provided by such methods is difficult to ascertain. In this paper, we develop methods for verification of optimality conditions within the framework of Stochastic Decomposition (SD) algorithms for two stage linear programs with recourse. Consistent with the stochastic nature of an SD algorithm, we provide termination criteria that are based on statistical verification of traditional (deterministic) optimality conditions. We propose the use of bootstrap methods to confirm the satisfaction of generalized Kuhn-Tucker conditions and conditions based on Lagrange duality. These methods are illustrated in the context of a power generation planning model, and the results are encouraging.This work was supported in part by Grant No. AFOSR-88-0076 from the Air Force Office of Scientific Research and Grant No. DDM-89-10046 from the National Science Foundation.     

A heuristic procedure for stochastic integer programs with complete recourse

In this paper, we propose a successive approximation heuristic which solves large stochastic mixed-integer programming problem with complete fixed recourse. We refer to this method as the Scenario Updating Method, since it solves the problem by considering only a subset of scenarios which is updated at each iteration. Only those scenarios which imply a significant change in the objective function are added. The algorithm is terminated when no such scenarios are available to enter in the current scenario subtree. Several rules to select scenarios are discussed. Bounds on heuristic solutions are computed by relaxing some of the non-anticipativity constraints. The proposed procedure is tested on a multistage stochastic batch-sizing problem.     

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.     

A parallel inexact newton method for stochastic programs with recourse

A parallel inexact Newton method with a line search is proposed for two-stage quadratic stochastic programs with recourse. A lattice rule is used for the numerical evaluation of multi-dimensional integrals, and a parallel iterative method is used to solve the quadratic programming subproblems. Although the objective only has a locally Lipschitz gradient, global convergence and local superlinear convergence of the method are established. Furthermore, the method provides an error estimate which does not require much extra computation. The performance of the method is illustrated on a CM5 parallel computer.This work was supported by the Australian Research Council and the numerical experiments were done on the Sydney Regional Centre for Parallel Computing CM5.     

Strong convexity in risk-averse stochastic programs with complete recourse

We give sufficient conditions for the expected excess and the mean-upper-semideviation of recourse functions to be strongly convex. This is done in the setting of two-stage stochastic programs with complete linear recourse and random right-hand side. This work extends results on strong convexity of risk-neutral models.     

L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

On structure and stability in stochastic programs with random technology matrix and complete integer recourse

For two-stage stochastic programs with integrality constraints in the second stage, we study continuity properties of the expected recourse as a function both of the first-stage policy and the integrating probability measure.Sufficient conditions for lower semicontinuity, continuity and Lipschitz continuity with respect to the first-stage policy are presented. Furthermore, joint continuity in the policy and the probability measure is established. This leads to conclusions on the stability of optimal values and optimal solutions to the two-stage stochastic program when subjecting the underlying probability measure to perturbations.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.The main part of the paper was written while the author was an assistant at the Department of Mathematics at Humboldt University Berlin.     

Distribution functions in stochastic programs with recourse: A parametric analysis

This paper studies the behavior of the optimum value of a two-stage stochastic program with recourse (random right-hand sides) as the mean and covariance matrices defining the random variables in the program are perturbed. Several results for convex programs are developed and are used to study the effect such perturbations have on the regularity properties of the stochastic programs. Cost associated with incorrectly specifying the mean and covariance matrices are discussed and estimated. A stochastic programming model in which the random variable is dependent on the first-stage decision is presented.     

Worst-case distribution analysis of stochastic programs

We show that for even quasi-concave objective functions the worst-case distribution, with respect to a family of unimodal distributions, of a stochastic programming problem is a uniform distribution. This extends the so-called ``Uniformity Principle' of Barmish and Lagoa (1997) where the objective function is the indicator function of a convex symmetric set.     

An economic interpretation of stochastic programs

The purpose of this note is to interpret a class of stochastic programming problems in economic terms. The primal stochastic program is shown to represent a certain production program of an entrepreneur. The dual program, which is also a stochastic program, represents the problem of a contractor who desires to purchase the entrepreneur's resources and sell product back to him.     

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.     

Approximate Lagrange multiplier algorithm for stochastic programs with complete recourse: Nonlinear deterministic constraints

In this paper we design an approximation method for solving stochastic programs with complete recourse and nonlinear deterministic constraints. This method is obtained by combining approximation method and Lagrange multiplier algorithm of Bertsekas type. Thus this method has the advantages of both the two.This project is supported by the National Natural Science Foundation of China.     

On the Glivenko-Cantelli problem in stochastic programming: Mixed-integer linear recourse

Expected recourse functions in linear two-stage stochastic programs with mixed-integer second stage are approximated by estimating the underlying probability distribution via empirical measures. Under mild conditions, almost sure uniform convergence of the empirical means to the original expected recourse function is established.     

Two-stage stochastic optimization problems with stochastic ordering constraints on the recourse

We consider two-stage risk-averse stochastic optimization problems with a stochastic ordering constraint on the recourse function. Two new characterizations of the increasing convex order relation are provided. They are based on conditional expectations and on integrated quantile functions: a counterpart of the Lorenz function. We propose two decomposition methods to solve the problems and prove their convergence. Our methods exploit the decomposition structure of the risk-neutral two-stage problems and construct successive approximations of the stochastic ordering constraints. Numerical results confirm the efficiency of the methods.