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.     

Quantitative stability of mixed-integer two-stage quadratic stochastic programs

For our introduced mixed-integer quadratic stochastic program with fixed recourse matrices, random recourse costs, technology matrix and right-hand sides, we study quantitative stability properties of its optimal value function and optimal solution set when the underlying probability distribution is perturbed with respect to an appropriate probability metric. To this end, we first establish various Lipschitz continuity results about the value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of linear constraints. The obtained results extend earlier results about quantitative stability properties of stochastic integer programming and stability results for mixed-integer parametric quadratic programs.     

Distributionally robust simple integer recourse

The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two-stage stochastic linear programming. Structural properties and approximations of SIR functions have been extensively studied in the seminal works of van der Vlerk and coauthors. We study a distributionally robust SIR function (DR-SIR) that considers the worst-case expectation over a given family of distributions. Under the assumption that the distribution family is specified by its mean and support, we derive a closed form analytical expression for the DR-SIR function. We also show that this nonconvex DR-SIR function can be represented using a mixed-integer second-order conic program.     

Postoptimality for mean-risk stochastic mixed-integer programs and its application

The mean-risk stochastic mixed-integer programs can better model complex decision problems under uncertainty than usual stochastic (integer) programming models. In order to derive theoretical results in a numerically tractable way, the contamination technique is adopted in this paper for the postoptimality analysis of the mean-risk models with respect to changes in the scenario set, here the risk is measured by the lower partial moment. We first study the continuity of the objective function and the differentiability, with respect to the parameter contained in the contaminated distribution, of the optimal value function of the mean-risk model when the recourse cost vector, the technology matrix and the right-hand side vector in the second stage problem are all random. The postoptimality conclusions of the model are then established. The obtained results are applied to two-stage stochastic mixed-integer programs with risk objectives where the objective function is nonlinear with respect to the probability distribution. The current postoptimality results for stochastic programs are improved.     

Designing a majorization scheme for the recourse function in two-stage stochastic linear programming

We discuss issues pertaining to the domination from above of the second-stage recourse function of a stochastic linear program and we present a scheme to majorize this function using a simpler sublinear function. This majorization is constructed using special geometrical attributes of the recourse function. The result is a proper, simplicial function with a simple characterization which is well-suited for calculations of its expectation as required in the computation of stochastic programs. Experiments indicate that the majorizing function is well-behaved and stable.     

Some Aspects of Stability in Stochastic Programming

Some developments in structure and stability of stochastic programs during the last decade together with interrelations to optimization theory and stochastics are reviewed. With weak convergence of probability measures as a backbone we discuss qualitative and quantitative stability of recourse models that possibly involve integer variables. We sketch stability in chance constrained stochastic programming and provide some applications in statistical estimation. Finally, an outlook is devoted to issues that were not discussed in detail and to some open problems.     

A note on second-order stochastic dominance constraints induced by mixed-integer linear recourse

We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured, mixed- integer linear programming equivalents to the dominance constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instances from power optimization.     

Quantitative stability of full random two-stage stochastic programs with recourse

In this paper, we consider quantitative stability analysis for two-stage stochastic linear programs when recourse costs, the technology matrix, the recourse matrix and the right-hand side vector are all random. For this purpose, we first investigate continuity properties of parametric linear programs. After deriving an explicit expression for the upper bound of its feasible solutions, we establish locally Lipschitz continuity of the feasible solution sets of parametric linear programs. These results are then applied to prove continuity of the generalized objective function derived from the full random second-stage recourse problem, from which we derive new forms of quantitative stability results of the optimal value function and the optimal solution set with respect to the Fortet–Mourier probability metric. The obtained results are finally applied to establish asymptotic behavior of an empirical approximation algorithm for full random two-stage stochastic programs.     

A finite branch-and-bound algorithm for two-stage stochastic integer programs

This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination. Computational experiments on standard test problems indicate superior performance of the proposed algorithm in comparison to those in the existing literature.The authors wish to acknowledge partial financial support from the IBM Research Division, ExxonMobil Upstream Research Company, and the National Science Foundation under awards DMI 95-02722, DMI 00-99726, and DMI 01-15166     

Convex approximations for a class of mixed-integer recourse models

We consider mixed-integer recourse (MIR) models with a single recourse constraint. We relate the second-stage value function of such problems to the expected simple integer recourse (SIR) shortage function. This allows to construct convex approximations for MIR problems by the same approach used for SIR models.     

Implementing bounds-based approximations in convex-concave two-stage stochastic programming

This paper is concerned with implementational issues and computational testing of bounds-based approximations for solving two-stage stochastic programs with fixed recourse. The implemented bounds are those derived by the authors previously, using first and cross moment information of the random parameters and a convex-concave saddle property of the recourse function. The paper first examines these bounds with regard to their tightness, monotonic behavior, convergence properties, and computationally exploitable decomposition structures. Subsequently, the bounds are implemented under various partitioning/refining strategies for the successive approximation. The detailed numerical experiments demonstrate the effectiveness in solving large scenario-based two-stage stochastic optimization problems throughsuccessive scenario clusters induced by refining the approximations.     

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.     

Solving multistage stochastic network programs on massively parallel computers

Multi-stage stochastic programs are typically extremely large, and can be prohibitively expensive to solve on the computer. In this paper we develop an algorithm for multistage programs that integrates the primal-dual row-action framework with proximal minimization. The algorithm exploits the structure of stochastic programs with network recourse, using a suitable problem formulation based on split variables, to decompose the solution into a large number of simple operations. It is therefore possible to use massively parallel computers to solve large instances of these problems. The algorithm is implemented on a Connection Machine CM-2 with up to 32K processors. We solve stochastic programs from an application from the insurance industry, as well as random problems, with up to 9 stages, and with up to 16392 scenarios, where the deterministic equivalent programs have a half million constraints and 1.3 million variables. Research partially supported by NSF grants CCR-9104042 and SES-91-00216, and AFOSR grant 91-0168. Computing resources were made available by AHPCRC at the University of Minnesota, and by NPAC at Syracuse University, New York.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method

The nested L-shaped method is used to solve two- and multi-stage linear stochastic programs with recourse, which can have integer variables on the first stage. In this paper we present and evaluate a cut consolidation technique and a dynamic sequencing protocol to accelerate the solution process. Furthermore, we present a parallelized implementation of the algorithm, which is developed within the COIN-OR framework. We show on a test set of 51 two-stage and 42 multi-stage problems, that both of the developed techniques lead to significant speed ups in computation time.     

On the convex hull of the simple integer recourse objective function

We consider the objective function of a simple integer recourse problem with fixed technology matrix.Using properties of the expected value function, we prove a relation between the convex hull of this function and the expected value function of a continuous simple recourse program.We present an algorithm to compute the convex hull of the expected value function in case of discrete right-hand side random variables. Allowing for restrictions on the first stage decision variables, this result is then extended to the convex hull of the objective function.Supported by the National Operations Research Network in the Netherlands (LNMB).     

Applying the minimax criterion in stochastic recourse programs

We consider an optimization problem in which some uncertain parameters are replaced by random variables. The minimax approach to stochastic programming concerns the problem of minimizing the worst expected value of the objective function with respect to the set of probability measures that are consistent with the available information on the random data. Only very few practicable solution procedures have been proposed for this problem and the existing ones rely on simplifying assumptions. In this paper, we establish a number of stability results for the minimax stochastic program, justifying in particular the approach of restricting attention to probability measures with support in some known finite set. Following this approach, we elaborate solution procedures for the minimax problem in the setting of two-stage stochastic recourse models, considering the linear recourse case as well as the integer recourse case. Since the solution procedures are modifications of well-known algorithms, their efficacy is immediate from the computational testing of these procedures and we do not report results of any computational experiments.     

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.