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.     

Using scenario trees and progressive hedging for stochastic inventory routing problems

The Stochastic Inventory Routing Problem is a challenging problem, combining inventory management and vehicle routing, as well as including stochastic customer demands. The problem can be described by a discounted, infinite horizon Markov Decision Problem, but it has been showed that this can be effectively approximated by solving a finite scenario tree based problem at each epoch. In this paper the use of the Progressive Hedging Algorithm for solving these scenario tree based problems is examined. The Progressive Hedging Algorithm can be suitable for large-scale problems, by giving an effective decomposition, but is not trivially implemented for non-convex problems. Attempting to improve the solution process, the standard algorithm is extended with locking mechanisms, dynamic multiple penalty parameters, and heuristic intermediate solutions. Extensive computational results are reported, giving further insights into the use of scenario trees as approximations of Markov Decision Problem formulations of the Stochastic Inventory Routing Problem.     

A so-called Cluster Benders Decomposition approach for solving two-stage stochastic linear problems

The optimization of stochastic linear problems, via scenario analysis, based on Benders decomposition requires appending feasibility and/or optimality cuts to the master problem until the iterative procedure reaches the optimal solution. The cuts are identified by solving the auxiliary submodels attached to the scenarios. In this work, we propose the algorithm named scenario Cluster Benders Decomposition (CBD) for dealing with the feasibility cut identification in the Benders method for solving large-scale two-stage stochastic linear problems. The scenario tree is decomposed into a set of scenario clusters and tighter feasibility cuts are obtained by solving the auxiliary submodel for each cluster instead of each individual scenario. Then, the scenario cluster based scheme allows to identify tighter feasibility cuts that yield feasible second stage decisions in reasonable computing time. Some computational experience is reported by using CPLEX as the solver of choice for the auxiliary LP submodels at each iteration of the algorithm CBD. The results that are reported show the favorable performance of the new approach over the traditional single scenario based Benders decomposition; it also outperforms the plain use of CPLEX for medium-large and large size instances.     

A scenario decomposition approach for stochastic production planning in sawmills

This study considers a real world stochastic multi-period, multi-product production planning problem. Motivated by the challenges encountered in sawmill production planning, the proposed model takes into account two important aspects: (i) randomness in yield and in demand; and (ii) set-up constraints. Rather than considering a single source of randomness, or ignoring set-up constraints as is typically the case in the literature, we retain all these characteristics while addressing real life-size instances of the problem. Uncertainties are modelled by a scenario tree in a multi-stage environment. In the case study, the resulting large-scale multi-stage stochastic mixed-integer model cannot be solved by using the mixed-integer solver of a commercial optimization package, such as CPLEX. Moreover, as the production planning model under discussion is a mixed-integer programming model lacking any special structure, the development of decomposition and cutting plane algorithms to obtain good solutions in a reasonable time-frame is not straightforward. We develop a scenario decomposition approach based on the progressive hedging algorithm, which iteratively solves the scenarios separately. CPLEX is then used for solving the sub-problems generated for each scenario. The proposed approach attempts to gradually steer the solutions of the sub-problems towards an implementable solution by adding some penalty terms in the objective function used when solving each scenario. Computational experiments for a real-world large-scale sawmill production planning model show the effectiveness of the proposed solution approach in finding good approximate solutions.     

On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management

A new scheme for dealing with uncertainty in scenario trees is presented for dynamic mixed 0–1 optimization problems with strategic and operational stochastic parameters. Let us generically name this type of problems as capacity expansion planning (CEP) in a given system, e.g., supply chain, production, rapid transit network, energy generation and transmission network, etc. The strategic scenario tree is usually a multistage one, and the replicas of the strategic nodes root structures in the form of either a special scenario graph or a two-stage scenario tree, depending on the type of operational activity in the system. Those operational scenario structures impact in the constraints of the model and, thus, in the decomposition methodology for solving usually large-scale problems. This work presents the modeling framework for some of the risk neutral and risk averse measures to consider for CEP problem solving. Two types of risk averse measures are considered. The first one is a time-inconsistent mixture of the chance-constrained and second-order stochastic dominance (SSD) functionals of the value of a given set of functions up to the strategic nodes in selected stages along the time horizon, The second type is a strategic node-based time-consistent SSD functional for the set of operational scenarios in the strategic nodes at selected stages. A specialization of the nested stochastic decomposition methodology for that problem solving is outlined. Its advantages and drawbacks as well as the framework for some schemes to, at least, partially avoid those drawbacks are also presented.     

On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming

We present a framework for solving large-scale multistage mixed 0–1 optimization problems under uncertainty in the coefficients of the objective function, the right-hand side vector, and the constraint matrix. A scenario tree-based scheme is used to represent the Deterministic Equivalent Model of the stochastic mixed 0–1 program with complete recourse. The constraints are modeled by a splitting variable representation via scenarios. So, a mixed 0–1 model for each scenario cluster is considered, plus the nonanticipativity constraints that equate the 0–1 and continuous so-called common variables from the same group of scenarios in each stage. Given the high dimensions of the stochastic instances in the real world, it is not realistic to obtain the optimal solution for the problem. Instead we use the so-called Fix-and-Relax Coordination (FRC) algorithm to exploit the characteristics of the nonanticipativity constraints of the stochastic model. A mixture of the FRC approach and the Lagrangian Substitution and Decomposition schemes is proposed for satisfying, both, the integrality constraints for the 0–1 variables and the nonanticipativity constraints. This invited paper is discussed in the comments available at: doi:, doi:, doi:, doi:.     

Risk optimization with p-order conic constraints: A linear programming approach

The paper considers solving of linear programming problems with p-order conic constraints that are related to a certain class of stochastic optimization models with risk objective or constraints. The proposed approach is based on construction of polyhedral approximations for p-order cones, and then invoking a Benders decomposition scheme that allows for efficient solving of the approximating problems. The conducted case study of portfolio optimization with p-order conic constraints demonstrates that the developed computational techniques compare favorably against a number of benchmark methods, including second-order conic programming methods.     

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 comparative study of decomposition algorithms for stochastic combinatorial optimization

This paper presents comparative computational results using three decomposition algorithms on a battery of instances drawn from two different applications. In order to preserve the commonalities among the algorithms in our experiments, we have designed a testbed which is used to study instances arising in server location under uncertainty and strategic supply chain planning under uncertainty. Insights related to alternative implementation issues leading to more efficient implementations, benchmarks for serial processing, and scalability of the methods are also presented. The computational experience demonstrates the promising potential of the disjunctive decomposition (D ²) approach towards solving several large-scale problem instances from the two application areas. Furthermore, the study shows that convergence of the D ² methods for stochastic combinatorial optimization (SCO) is in fact attainable since the methods scale well with the number of scenarios.     

A scenario decomposition algorithm for 0–1 stochastic programs

We propose a scenario decomposition algorithm for stochastic 0–1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and nonlinear stochastic integer programming test problems are presented.     

Sequential Importance Sampling Algorithms for Dynamic Stochastic Programming

This paper gives a comprehensive treatment of EVPI-based sequential importance sampling algorithms for dynamic (multistage) stochastic programming problems. Both theory and computational algorithms are discussed. Under general assumptions it is shown that both an expected value of perfect information (EVPI) process and the corresponding marginal EVPI process (the supremum norm of the conditional expectation of its generalized derivative) are nonanticipative nonnegative supermartingales. These processes are used as importance criteria in the class of sampling algorithms treated in the paper. When their values are negligible at a node of the current sample problem scenario tree, scenarios descending from the node are replaced by a single scenario at the next iteration. On the other hand, high values lead to increasing the number of scenarios descending from the node. Both the small sample and asymptotic properties of the sample problem estimates arising from the algorithms are established, and the former are evaluated numerically in the context of a financial planning problem. Finally, current and future research is described. Bibliography: 49 titles. __________ Published in Zapiski Nauchnykh Seminarov POMI, Vol. 312, 2004, pp. 94–129.     

Decomposition of test sets in stochastic integer programming

 We study Graver test sets for linear two-stage stochastic integer programs and show that test sets can be decomposed into finitely many building blocks whose number is independent on the number of scenarios of the stochastic program. We present a finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors. Once computed, building blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of test set vectors. Finally, we report preliminary computational experience. Received: March 14, 2002 / Accepted: March 27, 2002 Published online: September 27, 2002 Key words. test sets – stochastic integer programming – decomposition methods Mathematics Subject Classification (2000): 90C15, 90C10, 13P10     

Multicut Benders decomposition algorithm for process supply chain planning under uncertainty

In this paper, we present a multicut version of the Benders decomposition method for solving two-stage stochastic linear programming problems, including stochastic mixed-integer programs with only continuous recourse (two-stage) variables. The main idea is to add one cut per realization of uncertainty to the master problem in each iteration, that is, as many Benders cuts as the number of scenarios added to the master problem in each iteration. Two examples are presented to illustrate the application of the proposed algorithm. One involves production-transportation planning under demand uncertainty, and the other one involves multiperiod planning of global, multiproduct chemical supply chains under demand and freight rate uncertainty. Computational studies show that while both the standard and the multicut versions of the Benders decomposition method can solve large-scale stochastic programming problems with reasonable computational effort, significant savings in CPU time can be achieved by using the proposed multicut algorithm.     

Primal—Dual Constraint Aggregation with Application to Stochastic Programming

The special constraint structure and large dimension are characteristic for multistage stochastic optimization. This results from modeling future uncertainty via branching process or scenario tree. Most efficient algorithms for solving this type of problems use certain decomposition schemes, and often only a part of the whole set of scenarios is taken into account in order to make the problem tractable.We propose a primal–dual method based on constraint aggregation, which constructs a sequence of iterates converging to a solution of the initial problem. At each iteration, however, only a reduced sub-problem with smaller number of aggregate constraints has to be solved. Number of aggregates and their composition are determined by the user, and the procedure for calculating aggregates can be parallelized. The method provides a posteriori estimates of the quality of the current solution approximation in terms of the objective function value and the residual.Results of numerical tests for a portfolio allocation problem with quadratic utility function are presented.     

A model for strategic planning under uncertainty

Summary In this paper the multi-period strategic planning problem for a consumer sumer product manufacturing chain is considered. Our discussion is focused on investment decisions which, are economically optimal over the whole planning horizonT, while meeting customer demands and conforming to technological requirements. In strategic planning, time and uncertainty play important roles. The uncertainties in the model are due to different levels of forecast demands, cost estimates and equipment behaviour. The main aim of this paper is to develop and analyse a multiperiod stochastic model representing the entire manufacturing chain, from the acquisitions of raw material to the delivering of final products. The resulting optimization problem is computationally intractable because of the enormous, and sometimes unrealistic, number of scenarios that must be considered in order to identify the optimal planning strategy. We propose two different solution approaches; firstly, we apply a scenario risk analysis giving the related results of experiments on a particular real data set. We then describe and investigate an Integer Stochastic Programming formulation of the problem and propose, as a solution technique, a variation of Benders decomposition method, namely theL-shaped method.     

A stochastic programming approach for supply chain network design under uncertainty

This paper proposes a stochastic programming model and solution algorithm for solving supply chain network design problems of a realistic scale. Existing approaches for these problems are either restricted to deterministic environments or can only address a modest number of scenarios for the uncertain problem parameters. Our solution methodology integrates a recently proposed sampling strategy, the sample average approximation (SAA) scheme, with an accelerated Benders decomposition algorithm to quickly compute high quality solutions to large-scale stochastic supply chain design problems with a huge (potentially infinite) number of scenarios. A computational study involving two real supply chain networks are presented to highlight the significance of the stochastic model as well as the efficiency of the proposed solution strategy.     

Network planning under uncertainty with an application to hydropower generation

Summary We present a general modeling framework for therobust optimization of linear network problems with uncertainty in the values of the right-hand side. In contrast to traditional approaches in mathematical programming, we use scenarios to characterize the uncertainty. Solutions are obtained for each scenario and these individual scenarios are aggregated to yield a nonanticipative or implementable policy that minimizes the regret of wrong decisions. A given solution is termed robust if it minimizes the sum over the scenarios of the weighted upper difference between the objective function value for the solution and the objective function value for the optimal solution for each scenario, while satisfying certain nonanticipativity constraints. This approach results in a huge model with a network submodel per scenario plus coupling constraints. Several decomposition approaches are considered, namely Dantzig-Wolfe decomposition, various types of Benders decomposition and different quadratic network approaches for approximating Augmented Lagrangian decomposition. We present computational results for these methods, including two implementation versions of the Lagrangian based method: a sequential implementation and a parallel implementation on a network of three workstations.     

A Log-Barrier method with Benders decomposition for solving two-stage stochastic linear programs

An algorithm incorporating the logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage stochastic programs. Basic properties concerning the existence and uniqueness of the solution and the underlying path are studied. When applied to problems with a finite number of scenarios, the algorithm is shown to converge globally and to run in polynomial-time. Received: August 1998 / Accepted: August 2000?Published online April 12, 2001     

Financial scenario generation for stochastic multi-stage decision processes as facility location problems

The quality of multi-stage stochastic optimization models as they appear in asset liability management, energy planning, transportation, supply chain management, and other applications depends heavily on the quality of the underlying scenario model, describing the uncertain processes influencing the profit/cost function, such as asset prices and liabilities, the energy demand process, demand for transportation, and the like. A common approach to generate scenarios is based on estimating an unknown distribution and matching its moments with moments of a discrete scenario model. This paper demonstrates that the problem of finding valuable scenario approximations can be viewed as the problem of optimally approximating a given distribution with some distance function. We show that for Lipschitz continuous cost/profit functions it is best to employ the Wasserstein distance. The resulting optimization problem can be viewed as a multi-dimensional facility location problem, for which at least good heuristic algorithms exist. For multi-stage problems, a scenario tree is constructed as a nested facility location problem. Numerical convergence results for financial mean-risk portfolio selection conclude the paper.     

An Asset Liability Management Model for Casualty Insurers: Complexity Reduction vs. Parameterized Decision Rules

In this paper we study possibilities for complexity reductions in large scale stochastic programming problems with specific reference to the asset liability management (ALM) problem for casualty insurers. We describe a dynamic, stochastic portfolio selection model, within which the casualty insurer maximizes a concave objective function, indicating that the company perceives itself as risk averse. In this context we examine the sensitivity of the solution to the quality and accuracy with which economic uncertainties are represented in the model. We demonstrate a solution method that combines two solution approaches: A truly stochastic, dynamic solution method that requires scenario aggregation, and a solution method based on ex ante decision rules, that allow for a greater number of scenarios. This dynamic/fix mix decision policy, which facilitates a huge number of outcomes, is then compared to a fully dynamic decision policy, requiring fewer outcomes. We present results from solving the model. Basically we find that the insurance company is likely to prefer accurate representation of uncertainties. In order to accomplish this, it will accept to calculate its current portfolio using parameterized decision rules.