On the information-based complexity of stochastic programming

Existing complexity results in stochastic linear programming using the Turing model depend only on problem dimensionality. We apply techniques from the information-based complexity literature to show that the smoothness of the recourse function is just as important. We derive approximation error bounds for the recourse function of two-stage stochastic linear programs and show that their worst case is exponential and depends on the solution tolerance, the dimensionality of the uncertain parameters and the smoothness of the recourse function.     

A tighter variant of Jensen’s lower bound for stochastic programs and separable approximations to recourse functions

In this paper, we propose a new method to compute lower bounds on the optimal objective value of a stochastic program and show how this method can be used to construct separable approximations to the recourse functions. We show that our method yields tighter lower bounds than Jensen’s lower bound and it requires a reasonable amount of computational effort even for large problems. The fundamental idea behind our method is to relax certain constraints by associating dual multipliers with them. This yields a smaller stochastic program that is easier to solve. We particularly focus on the special case where we relax all but one of the constraints. In this case, the recourse functions of the smaller stochastic program are one dimensional functions. We use these one dimensional recourse functions to construct separable approximations to the original recourse functions. Computational experiments indicate that our lower bounds can significantly improve Jensen’s lower bound and our recourse function approximations can provide good solutions.     

Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis

In this paper we present a framework for solving stochastic programs with complete integer recourse and discretely distributed right-hand side vector, using Gröbner basis methods from computational algebra to solve the numerous second-stage integer programs. Using structural properties of the expected integer recourse function, we prove that under mild conditions an optimal solution is contained in a finite set. Furthermore, we present a basic scheme to enumerate this set and suggest improvements to reduce the number of function evaluations needed.     

Convergent Cutting-Plane and Partial-Sampling Algorithm for Multistage Stochastic Linear Programs with Recourse

We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.     

Stochastic utility-efficient programming of organic dairy farms

Opportunities to make sequential decisions and adjust activities as a season progresses and more information becomes available characterise the farm management process. In this paper, we present a discrete stochastic two-stage utility-efficient programming model of organic dairy farms, which includes risk aversion in the decision maker’s objective function as well as both embedded risk (stochastic programming with recourse) and non-embedded risk (stochastic programming without recourse). Historical farm accountancy data and subjective judgements were combined to assess the nature of the uncertainty that affects the possible consequences of the decisions. The programming model was used within a stochastic dominance framework to examine optimal strategies in organic dairy systems in Norway.     

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.     

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.     

Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming

We introduce and study two-stage stochastic symmetric programs with recourse to handle uncertainty in data defining (deterministic) symmetric programs in which a linear function is minimized over the intersection of an affine set and a symmetric cone. We present a Benders’ decomposition-based interior point algorithm for solving these problems and prove its polynomial complexity. Our convergence analysis proved by showing that the log barrier associated with the recourse function of stochastic symmetric programs behaves a strongly self-concordant barrier and forms a self-concordant family on the first stage solutions. Since our analysis applies to all symmetric cones, this algorithm extends Zhao’s results [G. Zhao, A log barrier method with Benders’ decomposition for solving two-stage stochastic linear programs, Math. Program. Ser. A 90 (2001) 507–536] for two-stage stochastic linear programs, and Mehrotra and Özevin’s results [S. Mehrotra, M.G. Özevin, Decomposition-based interior point methods for two-stage stochastic semidefinite programming, SIAM J. Optim. 18 (1) (2007) 206–222] for two-stage stochastic semidefinite programs.     

Continuity of parametric mixed-integer quadratic programs and its application to stability analysis of two-stage quadratic stochastic programs with mixed-integer recourse

For mixed-integer quadratic program where all coefficients in the objective function and the right-hand sides of constraints vary simultaneously, we show locally Lipschitz continuity of its optimal value function, and derive the corresponding global estimation; furthermore, we also obtain quantitative estimation about the change of its optimal solutions. Applying these results to two-stage quadratic stochastic program with mixed-integer recourse, we establish quantitative stability of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. The obtained results generalize available results on continuity properties of mixed-integer quadratic programs and extend current results on quantitative stability of two-stage quadratic stochastic programs with mixed-integer recourse.     

A piecewise linear upper bound on the network recourse function

We consider the optimal value of a pure minimum cost network flow problem as a function of supply, demand and arc capacities. We present a new piecewise linear upper bound on this function, which is called the network recourse function. The bound is compared to the standard Madansky bound, and is shown computationally to be a little weaker, but much faster to find. The amount of work is linear in the number of stochastic variables, not exponential as is the case for the Madansky bound. Therefore, the reduction in work increases as the number of stochastic variables increases. Computational results are presented.     

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.     

Improving constants of strong convexity in linear stochastic programming

We derive formulas for constants of strong convexity (CSCs) of expectation functions encountered in two-stage stochastic programs with linear recourse. One of them yields a CSC as the optimal value of a certain quadratically constrained quadratic program, another one in terms of the thickness of the feasibility polytope of the dual problem associated to the recourse problem. CSCs appear in Hoelder-type estimates relating the distance of optimal solution sets of stochastic programs to a suitable distance of underlying probability distributions.     

Stochastic programming with simple integer recourse

Stochastic integer programs are notoriously difficult. Very few properties are known and solution algorithms are very scarce. In this paper, we introduce the class of stochastic programs with simple integer recourse, a natural extension of the simple recourse case extensively studied in stochastic continuous programs.Analytical as well as computational properties of the expected recourse function of simple integer recourse problems are studied. This includes sharp bounds on this function and the study of the convex hull. Finally, a finite termination algorithm is obtained that solves two classes of stochastic simple integer recourse problems.Supported by the National Operations Research Network in the Netherlands (LNMB).     

补偿随机规划的一种新数值方法

本文给出解决两阶段求援随机规划的一种新的数值方法.由于引进了新的逼近技术,该方法具有全局收敛性和局部超线性收敛性.     

Natural gas cash-out problem: Bilevel stochastic optimization approach

A stochastic formulation of the natural gas cash-out problem is given in a form of a bilevel multi-stage stochastic programming model with recourse. After reducing the original formulation to a bilevel linear problem, a stochastic scenario tree is defined by its node events, and time series forecasting is used to produce stochastic values for data of natural gas price and demand. Numerical experiments were run to compare the stochastic solution with the perfect information solution and the expected value solutions.     

简单补偿随机规划的一种异步并行算法

本文利用凸规划的近似分解方法，给出了求解具有简单补偿随机规划问题的一种异步并行算法．     

Bounding separable recourse functions with limited distribution information

The recourse function in a stochastic program with recourse can be approximated by separable functions of the original random variables or linear transformations of them. The resulting bound then involves summing simple integrals. These integrals may themselves be difficult to compute or may require more information about the random variables than is available. In this paper, we show that a special class of functions has an easily computable bound that achieves the best upper bound when only first and second moment constraints are available.This research has been partially supported by the National Science Foundation under Grants ECS-8304065 and ECS-8815101, by the 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.     

Quantitative stability of full random two-stage problems with quadratic recourse

ABSTRACT

In this paper, we discuss quantitative stability of two-stage stochastic programs with quadratic recourse where all parameters in the second-stage problem are random. By establishing the Lipschitz continuity of the feasible set mapping of the restricted Wolfe dual of the second-stage quadratic programming in terms of the Hausdorff distance, we prove the local Lipschitz continuity of the integrand of the objective function of the two-stage stochastic programming problem and then establish quantitative stability results of the optimal values and the optimal solution sets when the underlying probability distribution varies under the Fortet–Mourier metric. Finally, the obtained results are applied to study the asymptotic behaviour of the empirical approximation of the model.     

A simple recourse model for power dispatch under uncertain demand

Optimal power dispatch under uncertainty of power demand is tackled via a stochastic programming model with simple recourse. The decision variables correspond to generation policies of a system comprising thermal units, pumped storage plants and energy contracts. The paper is a case study to test the kernel estimation method in the context of stochastic programming. Kernel estimates are used to approximate the unknown probability distribution of power demand. General stability results from stochastic programming yield the asymptotic stability of optimal solutions. Kernel estimates lead to favourable numerical properties of the recourse model (no numerical integration, the optimization problem is smooth convex and of moderate dimension). Test runs based on real-life data are reported. We compute the value of the stochastic solution for different problem instances and compare the stochastic programming solution with deterministic solutions involving adjusted demand portions.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft.