Convergence analysis of sample average approximation for a class of stochastic nonlinear complementarity problems: from two-stage to multistage

In this paper, we consider the sample average approximation (SAA) approach for a class of stochastic nonlinear complementarity problems (SNCPs) and study the corresponding convergence properties. We first investigate the convergence of the SAA counterparts of two-stage SNCPs when the first-stage problem is continuously differentiable and the second-stage problem is locally Lipschitz continuous. After that, we extend the convergence results to a class of multistage SNCPs whose decision variable of each stage is influenced only by the decision variables of adjacent stages. Finally, some preliminary numerical tests are presented to illustrate the convergence results.

     

Fenchel decomposition for stochastic mixed-integer programming

This paper introduces a new cutting plane method for two-stage stochastic mixed-integer programming (SMIP) called Fenchel decomposition (FD). FD uses a class of valid inequalities termed, FD cuts, which are derived based on Fenchel cutting planes from integer programming. First, we derive FD cuts based on both the first and second-stage variables, and devise an FD algorithm for SMIP and establish finite convergence for binary first-stage. Second, we derive FD cuts based on the second-stage variables only and use an idea from disjunctive programming to lift the cuts to the higher dimension space including the first-stage variables. We then devise an alternative algorithm (FD-L algorithm) based on the lifted FD cuts. Finally, we report on computational results based on several test instances from the literature involving the special structure of knapsack problems with nonnegative left-hand side coefficients. The results are promising and show that both algorithms can outperform a standard direct solver and a disjunctive decomposition algorithm on large-scale instances. Furthermore, the FD-L algorithm provides better performance than the FD algorithm in general. Since Fenchel cuts can be computationally expensive in general and are best suited for problems with special structure, both algorithms exploit the special structure of the test instances by reducing the size of the cut generation problems based on the number of nonzero components in the non-integer solution that needs to be cut off.     

Two-stage stochastic hierarchical multiple risk problems: models and algorithms

In this paper, we consider a class of two-stage stochastic risk management problems, which may be stated as follows. A decision-maker determines a set of binary first-stage decisions, after which a random event from a finite set of possible outcomes is realized. Depending on the realization of this outcome, a set of continuous second-stage decisions must then be made that attempt to minimize some risk function. We consider a hierarchy of multiple risk levels along with associated penalties for each possible scenario. The overall objective function thus depends on the cost of the first-stage decisions, plus the expected second-stage risk penalties. We develop a mixed-integer 0–1 programming model and adopt an automatic convexification procedure using the reformulation–linearization technique to recast the problem into a form that is amenable to applying Benders’ partitioning approach. As a principal computational expedient, we show how the reformulated higher-dimensional Benders’ subproblems can be efficiently solved via certain reduced-sized linear programs in the original variable space. In addition, we explore several key ingredients in our proposed procedure to enhance the tightness of the prescribed Benders’ cuts and the efficiency with which they are generated. Finally, we demonstrate the computational efficacy of our approaches on a set of realistic test problems. Dr. H. D. Sherali acknowledges the support of the National Science Foundation under Grant No. DMI-0552676. Dr. J. C. Smith acknowledges the support of the Air Force Office of Scientific Research under Grant No. AFOSR/MURI F49620-03-1-0477.     

On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables

In this paper, we propose a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders' decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution space. This partial convex hull is sequentially generated using a convexification scheme such as the Reformulation-Linearization Technique (RLT) or lift-and-project process, which yields valid inequalities that are reusable in the subsequent subproblems by updating the values of the first-stage variables. A branch-and-bound algorithm is designed based on a hyperrectangular partitioning process, using the established property that any resulting lower bounding Benders' master problem defined over a hyperrectangle yields the same objective value as the original stochastic program over that region if the first-stage variable solution is an extreme point of the defining hyperrectangle or the second-stage solution satisfies the binary restrictions. We prove that this algorithm converges to a global optimal solution. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach.     

Two-stage stochastic programming under multivariate risk constraints with an application to humanitarian relief network design

In this study, we consider two classes of multicriteria two-stage stochastic programs in finite probability spaces with multivariate risk constraints. The first-stage problem features multivariate stochastic benchmarking constraints based on a vector-valued random variable representing multiple and possibly conflicting stochastic performance measures associated with the second-stage decisions. In particular, the aim is to ensure that the decision-based random outcome vector of interest is preferable to a specified benchmark with respect to the multivariate polyhedral conditional value-at-risk or a multivariate stochastic order relation. In this case, the classical decomposition methods cannot be used directly due to the complicating multivariate stochastic benchmarking constraints. We propose an exact unified decomposition framework for solving these two classes of optimization problems and show its finite convergence. We apply the proposed approach to a stochastic network design problem in the context of pre-disaster humanitarian logistics and conduct a computational study concerning the threat of hurricanes in the Southeastern part of the United States. The numerical results provide practical insights about our modeling approach and show that the proposed algorithm is computationally scalable.

     

Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs

We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the $L$ -shaped or Benders’ methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology is flexible in that it allows several modes of implementation, all of which lead to finitely convergent algorithms. We illustrate our algorithms using examples from the literature. We report computational results using the stochastic server location problem instances which suggest that our decomposition-based approach scales better with increases in the number of scenarios than a state-of-the art solver which was used to solve the deterministic equivalent formulation.     

Stochastic binary problems with simple penalties for capacity constraints violations

This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly ${\mathcal{N}\mathcal{P}}$ -hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and strictly positively distributed random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.     

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.     

Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables

This paper proposes an accelerated solution method to solve two-stage stochastic programming problems with binary variables in the first stage and continuous variables in the second stage. To develop the solution method, an accelerated sample average approximation approach is combined with an accelerated Benders’ decomposition algorithm. The accelerated sample average approximation approach improves the main structure of the original technique through the reduction in the number of mixed integer programming problems that need to be solved. Furthermore, the recently accelerated Benders’ decomposition approach is utilized to expedite the solution time of the mixed integer programming problems. In order to examine the performance of the proposed solution method, the computational experiments are performed on developed stochastic supply chain network design problems. The computational results show that the accelerated solution method solves these problems efficiently. The synergy of the two accelerated approaches improves the computational procedure by an average factor of over 42%, and over 12% in comparison with the original and the recently modified methods, respectively. Moreover, the betterment of the computational process increases substantially with the size of the problem.     

Two-Stage Stochastic Variational Inequality Arising from Stochastic Programming

We consider a two-stage stochastic variational inequality arising from a general convex two-stage stochastic programming problem, where the random variables have continuous distributions. The equivalence between the two problems is shown under some moderate conditions, and the monotonicity of the two-stage stochastic variational inequality is discussed under additional conditions. We provide a discretization scheme with convergence results and employ the progressive hedging method with double parameterization to solve the discretized stochastic variational inequality. As an application, we show how the water resources management problem under uncertainty can be transformed from a two-stage stochastic programming problem to a two-stage stochastic variational inequality, and how to solve it, using the discretization scheme and the progressive hedging method with double parameterization.

     

Geometric partitioning and robust ad-hoc network design

We consider bounds for the price of a European-style call option under regime switching. Stochastic semidefinite programming models are developed that incorporate a lattice generated by a finite-state Markov chain regime-switching model as a representation of scenarios (uncertainty) to compute bounds. The optimal first-stage bound value is equivalent to a Value at Risk quantity, and the optimal solution can be obtained via simple sorting. The upper (lower) bounds from the stochastic model are bounded below (above) by the corresponding deterministic bounds and are always less conservative than their robust optimization (min-max) counterparts. In addition, penalty parameters in the model allow controllability in the degree to which the regime switching dynamics are incorporated into the bounds. We demonstrate the value of the stochastic solution (bound) and computational experiments using the S&P 500 index are performed that illustrate the advantages of the stochastic programming approach over the deterministic strategy.     

An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems

This paper considers a class of bilevel linear programming problems in which the coefficients of both objective functions are fuzzy random variables. The main idea of this paper is to introduce the Pareto optimal solution in a multi-objective bilevel programming problem as a solution for a fuzzy random bilevel programming problem. To this end, a stochastic interval bilevel linear programming problem is first introduced in terms of α-cuts of fuzzy random variables. On the basis of an order relation of interval numbers and the expectation optimization model, the stochastic interval bilevel linear programming problem can be transformed into a multi-objective bilevel programming problem which is solved by means of weighted linear combination technique. In order to compare different optimal solutions depending on different cuts, two criterions are given to provide the preferable optimal solutions for the upper and lower level decision makers respectively. Finally, a production planning problem is given to demonstrate the feasibility of the proposed approach.     

Some insights into the solution algorithms for SLP problems

We consider classes of stochastic linear programming problems which can be efficiently solved by deterministic algorithms. For two–stage recourse problems we identify two such classes. The first one consists of problems where the number of stochastically independent random variables is relatively low; the second class is the class of simple recourse problems. The proposed deterministic algorithm is successive discrete approximation. We also illustrate the impact of required accuracy on the efficiency of this algorithm. For jointly chance constrained problems with a random right–hand–side and multivariate normal distribution we demonstrate the increase in efficiency when lower accuracy is required, for a central cutting plane method. We support our argumentation and findings with computational results.     

Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra

 We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example. Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002 Key words. stochastic programming – integer programming – valid inequalities     

Stochastic linear programs with restricted recourse

Stochastic programs with recourse provide an effective modeling paradigm for sequential decision problems with uncertain or noisy data, when uncertainty can be modeled by a discrete set of scenarios. In two-stage problems the decision variables are partitioned into two groups: a set of structural, first-stage decisions, and a set of second-stage, recourse decisions. The structural decisions are scenario-invariant, but the recourse decisions are scenario-dependent and can vary substantially across scenarios. In several applications it is important to restrict the variability of recourse decisions across scenarios, or to investigate the tradeoffs between the stability of recourse decisions and expected cost of a solution.We present formulations of stochastic programs with restricted recourse that trade off recourse stability with expected cost. The models generate a sequence of solutions to which recourse robustness is progressively enforced via parameterized, satisficing constraints. We investigate the behavior of the models on several test cases, and examine the performance of solution procedures based on the primal-dual interior point method.     

A model of distributionally robust two-stage stochastic convex programming with linear recourse

We consider distributionally robust two-stage stochastic convex programming problems, in which the recourse problem is linear. Other than analyzing these new models case by case for different ambiguity sets, we adopt a unified form of ambiguity sets proposed by Wiesemann, Kuhn and Sim, and extend their analysis from a single stochastic constraint to the two-stage stochastic programming setting. It is shown that under a standard set of regularity conditions, this class of problems can be converted to a conic optimization problem. Numerical results are presented to show the efficiency of the distributionally robust approach.     

Tight bounds on indefinite separable singly-constrained quadratic programs in linear-time

This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first-stage approximation is solved by a branch-and-bound algorithm with its nodes inheriting Benders’ cuts that are valid for their ancestor nodes. In addition, we develop two closely related convexification schemes which use multi-term disjunctive cuts to obtain approximations of the second-stage mixed-integer programs. We prove that the proposed methods are finitely convergent. One of the main advantages of our decomposition scheme is that we use a Benders-based branch-and-cut approach in which linear programming approximations are strengthened sequentially. Moreover as in many decomposition schemes, these subproblems can be solved in parallel. We also illustrate these algorithms using several variants of an SMIP example from the literature, as well as a new set of test problems, which we refer to as Stochastic Server Location and Sizing. Finally, we present our computational experience with previously known examples as well as the new collection of SMIP instances. Our experiments reveal that our algorithm is able to produce provably optimal solutions (within an hour of CPU time) even in instances for which a highly reliable commercial MIP solver is unable to provide an optimal solution within an hour of CPU time.     

A novel differential evolution algorithm for binary optimization

Differential evolution (DE) is one of the most powerful stochastic search methods which was introduced originally for continuous optimization. In this sense, it is of low efficiency in dealing with discrete problems. In this paper we try to cover this deficiency through introducing a new version of DE algorithm, particularly designed for binary optimization. It is well-known that in its original form, DE maintains a differential mutation, a crossover and a selection operator for optimizing non-linear continuous functions. Therefore, developing the new binary version of DE algorithm, calls for introducing operators having the major characteristics of the original ones and being respondent to the structure of binary optimization problems. Using a measure of dissimilarity between binary vectors, we propose a differential mutation operator that works in continuous space while its consequence is used in the construction of the complete solution in binary space. This approach essentially enables us to utilize the structural knowledge of the problem through heuristic procedures, during the construction of the new solution. To verify effectiveness of our approach, we choose the uncapacitated facility location problem (UFLP)—one of the most frequently encountered binary optimization problems—and solve benchmark suites collected from OR-Library. Extensive computational experiments are carried out to find out the behavior of our algorithm under various setting of the control parameters and also to measure how well it competes with other state of the art binary optimization algorithms. Beside UFLP, we also investigate the suitably of our approach for optimizing numerical functions. We select a number of well-known functions on which we compare the performance of our approach with different binary optimization algorithms. Results testify that our approach is very efficient and can be regarded as a promising method for solving wide class of binary optimization problems.     

Continuity and Stability of a Quadratic Mixed-Integer Stochastic Program

For the two-stage quadratic stochastic program where the second-stage problem is a general mixed-integer quadratic program with a random linear term in the objective function and random right-hand sides in constraints, we study continuity properties of the second-stage optimal value as a function of both the first-stage policy and the random parameter vector. We also present sufficient conditions for lower or upper semicontinuity, continuity, and Lipschitz continuity of the second-stage problem's optimal value function and the upper semicontinuity of the optimal solution set mapping with respect to the first-stage variables and/or the random parameter vector. These results then enable us to establish conclusions on the stability of optimal value and optimal solutions when the underlying probability distribution is perturbed with respect to the weak convergence of probability measures.