Models and model value in stochastic programming

Finding optimal decisions often involves the consideration of certain random or unknown parameters. A standard approach is to replace the random parameters by the expectations and to solve a deterministic mathematical program. A second approach is to consider possible future scenarios and the decision that would be best under each of these scenarios. The question then becomes how to choose among these alternatives. Both approaches may produce solutions that are far from optimal in the stochastic programming model that explicitly includes the random parameters. In this paper, we illustrate this advantage of a stochastic program model through two examples that are representative of the range of problems considered in stochastic programming. The paper focuses on the relative value of the stochastic program solution over a deterministic problem solution.The author's work was supported in part by the National Science Foundation under Grant DDM-9215921.     

Warm-Start Heuristic for Stochastic Portfolio Optimization with Fixed and Proportional Transaction Costs

We consider a probabilistic portfolio optimization model including fixed and proportional transaction costs. We derive a deterministic equivalent of the probabilistic model for fat-tailed portfolio returns. We develop a method which finds provably near-optimal solutions in minimal amount of time for industry-sized (up to 2000 assets) problems. To solve the mixed-integer nonlinear programming (MINLP) deterministic formulation equivalent to the stochastic problem, we design a mathematical programming-based warm-start heuristic. The tests show the computational efficiency of the heuristic which is more than an order of magnitude faster than Cplex in finding high-quality solutions.     

Flow-based formulations for operational fixed interval scheduling problems with random delays

We deal with operational fixed interval scheduling problem with random delays in job processing times. We formulate two stochastic programming problems. In the first problem with a probabilistic objective, all jobs are processed on available machines and the goal is to obtain a schedule with the highest attainable reliability. The second problem is to select a subset of jobs with the highest reward under a chance constraint ensuring feasibility of the schedule with a prescribed probability. We assume that the multivariate distribution of delays follows an Archimedean copula, whereas there are no restrictions on marginal distributions. We introduce new deterministic integer linear reformulations based on flow problems. We compare the formulations with the extended robust coloring problem, which was shown to be a deterministic equivalent to the stochastic programming problem with probabilistic objective by Branda et al. (Comput Ind Eng 93:45–54, 2016). In the numerical study, we report average computational times necessary to solve a large number of simulated instances. It turns out that the new flow-based formulation helps to solve the FIS problems considerably faster than the other one.     

A generalized stochastic goal programming model

In this paper we show how one can get stochastic solutions of Stochastic Multi-objective Problem (SMOP) using goal programming models. In literature it is well known that one can reduce a SMOP to deterministic equivalent problems and reduce the analysis of a stochastic problem to a collection of deterministic problems. The first sections of this paper will be devoted to the introduction of deterministic equivalent problems when the feasible set is a random set and we show how to solve them using goal programming technique. In the second part we try to go more in depth on notion of SMOP solution and we suppose that it has to be a random variable. We will present stochastic goal programming model for finding stochastic solutions of SMOP. Our approach requires more computational time than the one based on deterministic equivalent problems due to the fact that several optimization programs (which depend on the number of experiments to be run) needed to be solved. On the other hand, since in our approach we suppose that a SMOP solution is a random variable, according to the Central Limit Theorem the larger will be the sample size and the more precise will be the estimation of the statistical moments of a SMOP solution. The developed model will be illustrated through numerical examples.     

PROMISE: A DSS for multiple objective stochastic linear programming problems

Most of the multiple objective linear programming (MOLP) methods which have been proposed in the last fifteen years suppose deterministic contexts, but because many real problems imply uncertainty, some methods have been recently developed to deal with MOLP problems in stochastic contexts. In order to help the decision maker (DM) who is placed before such stochastic MOLP problems, we have built a Decision Support System called PROMISE. On the one hand, our DSS enables the DM to identify many current stochastic contexts: risky situations and also situations of partial uncertainty. On the other hand, according to the nature of the uncertainty, our DSS enables the DM to choose the most appropriate interactive stochastic MOLP method among the available methods, if such a method exists, and to solve his problem via the chosen method.     

An application of Lagrangian relaxation to a capacity planning problem under uncertainty

A supply chain network-planning problem is presented as a two-stage resource allocation model with 0-1 discrete variables. In contrast to the deterministic mathematical programming approach, we use scenarios, to represent the uncertainties in demand. This formulation leads to a very large scale mixed integer-programming problem which is intractable. We apply Lagrangian relaxation and its corresponding decomposition of the initial problem in a novel way, whereby the Lagrangian relaxation is reinterpreted as a column generator and the integer feasible solutions are used to approximate the given problem. This approach addresses two closely related problems of scenario analysis and two-stage stochastic programs. Computational solutions for large data instances of these problems are carried out successfully and their solutions analysed and reported. The model and the solution system have been applied to study supply chain capacity investment and planning.     

A NEW DETERMINISTIC FORMULATION FOR DYNAMIC STOCHASTIC PROGRAMMING PROBLEMS AND ITS NUMERICAL COMPARISON WITH OTHERS

A new deterministic formulation, called the conditional expectation formulation, is proposed for dynamic stochastic programming problems in order to overcome some disadvantages of existing deterministic formulations. We then check the impact of the new deterministic formulation and other two deterministic formulations on the corresponding problem size, nonzero elements and solution time by solving some typi     

Capital rationing problems under uncertainty and risk

Capital rationing is a major problem in managerial decision making. The classical mathematical formulation of the problem relies on a multi-dimensional knapsack model with known input parameters. Since capital rationing is carried out in conditions where uncertainty is the rule rather than the exception, the hypothesis of deterministic data limits the applicability of deterministic formulations in real settings. This paper proposes a stochastic version of the capital rationing problem which explicitly accounts for uncertainty. In particular, a mathematical formulation is provided in the framework of stochastic programming with joint probabilistic constraints and a novel solution approach is proposed. The basic model is also extended to include specific risk measures. Preliminary computational results are presented and discussed.     

Solution approaches for the multiobjective stochastic programming

We survey in this paper various solution approaches for multiobjective stochastic problems where random variables can be in both objectives and constraints parameters. Once a problem requires a stochastic formulation, a first step consists in transforming the problem into its deterministic formulation. We propose to classify and evaluate such transformations with regards to the many proposed concepts of efficiency. The paper addresses also some applications of the multiobjective stochastic programming models.     

Stochastic MOLP with Incomplete Information: An Interactive Approach with Recourse

Numerous multiobjective linear programming (MOLP) methods have been proposed in the last two decades, but almost all for contexts where the parameters of problems are deterministic. However, in many real situations, parameters of a stochastic nature arise. In this paper, we suppose that the decision-maker is confronted with a situation of partial uncertainty where he possesses incomplete information about the stochastic parameters of the problem, this information allowing him to specify only the limits of variation of these parameters and eventually their central values. For such situations, we propose a multiobjective stochastic linear programming methodology; it implies the transformation of the stochastic objective functions and constraints in order to obtain an equivalent deterministic MOLP problem and the solving of this last problem by an interactive approach derived from the STEM method. Our methodology is illustrated by a didactical example.     

Solving non-linear portfolio optimization problems with the primal-dual interior point method

Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear or quadratic models due to the inability of currently available solvers to solve NLP problems of typical sizes. However stochastic programming problems are highly structured. The key to the efficient solution of such problems is therefore the ability to exploit their structure. Interior point methods are well-suited to the solution of very large non-linear optimization problems. In this paper we exploit this feature and show how portfolio optimization problems with sizes measured in millions of constraints and decision variables, featuring constraints on semi-variance, skewness or non-linear utility functions in the objective, can be solved with the state-of-the-art solver.     

A Simultaneous Enumeration Approach to the Traveling Salesman Problem

The solution procedure proposed in this paper uses certain principles of analog computers. The idea of using analog rather than digital computers to solve mathematical programming problems is not new—various methods have been proposed to solve linear programming, network flows, as well as shortest path problems (Dennis, 1959; Stern, 1965). These problems can be more efficiently solved with digital computers. To find a solution to the traveling salesman problem as well as other integer programming problems is difficult with existing hardware, especially if the number of variables is large. The question thus arises whether different hardware configurations make it possible to solve integer problems more efficiently. One such configuration is proposed below for the traveling salesman problem.     

Solving generalized equations via homotopies

Global Newton methods for computing solutions of nonlinear systems of equations have recently received a great deal of attention. By using the theory of generalized equations, a homotopy method is proposed to solve problems arising in complementarity and mathematical programming, as well as in variational inequalities. We introduce the concepts of generalized homotopies and regular values, characterize the solution sets of such generalized homotopies and prove, under boundary conditions similar to Smale’s [10], the existence of a homotopy path which contains an odd number of solutions to the problem. We related our homotopy path to the Newton method for generalized equations developed by Josephy [3]. An interpretation of our results for the nonlinear programming problem will be given.     

Nonnormal deterministic equivalents and a transformation in stochastic mathematical programming

This paper considers random variables of the continuous type in a stochastic programming problem and presents (1) a general approach to the development of deterministic equivalents of constraints to be satisfied within certain probability limits, and (2) a deterministic transformation of a stochastic programming problem with random variables in the objective function. Deterministic equivalents are developed for constraints containing uniform random variables, but the approach used can be applied to other types of continuous random variables, as well. When the random variables appear in the objective function, a deterministic transformation of the stochastic programming problem is obtained to yield a closed-form solution without resort to a Monte Carlo computer simulation. Extension of this approach to stochastic problems with discrete random variables and integer decision variables is discussed briefly. A numerical example is presented.     

Applying oracles of on-demand accuracy in two-stage stochastic programming – A computational study

Traditionally, two variants of the L-shaped method based on Benders’ decomposition principle are used to solve two-stage stochastic programming problems: the aggregate and the disaggregate version. In this study we report our experiments with a special convex programming method applied to the aggregate master problem. The convex programming method is of the type that uses an oracle with on-demand accuracy. We use a special form which, when applied to two-stage stochastic programming problems, is shown to integrate the advantages of the traditional variants while avoiding their disadvantages. On a set of 105 test problems, we compare and analyze parallel implementations of regularized and unregularized versions of the algorithms. The results indicate that solution times are significantly shortened by applying the concept of on-demand accuracy.     

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.     

A global MINLP approach to symbolic regression

Symbolic regression methods generate expression trees that simultaneously define the functional form of a regression model and the regression parameter values. As a result, the regression problem can search many nonlinear functional forms using only the specification of simple mathematical operators such as addition, subtraction, multiplication, and division, among others. Currently, state-of-the-art symbolic regression methods leverage genetic algorithms and adaptive programming techniques. Genetic algorithms lack optimality certifications and are typically stochastic in nature. In contrast, we propose an optimization formulation for the rigorous deterministic optimization of the symbolic regression problem. We present a mixed-integer nonlinear programming (MINLP) formulation to solve the symbolic regression problem as well as several alternative models to eliminate redundancies and symmetries. We demonstrate this symbolic regression technique using an array of experiments based upon literature instances. We then use a set of 24 MINLPs from symbolic regression to compare the performance of five local and five global MINLP solvers. Finally, we use larger instances to demonstrate that a portfolio of models provides an effective solution mechanism for problems of the size typically addressed in the symbolic regression literature.     

A gaussian upper bound for gaussian multi-stage stochastic linear programs

This paper deals with two-stage and multi-stage stochastic programs in which the right-hand sides of the constraints are Gaussian random variables. Such problems are of interest since the use of Gaussian estimators of random variables is widespread. We introduce algorithms to find upper bounds on the optimal value of two-stage and multi-stage stochastic (minimization) programs with Gaussian right-hand sides. The upper bounds are obtained by solving deterministic mathematical programming problems with dimensions that do not depend on the sample space size. The algorithm for the two-stage problem involves the solution of a deterministic linear program and a simple semidefinite program. The algorithm for the multi-stage problem invovles the solution of a quadratically constrained convex programming problem.     

PySP: modeling and solving stochastic programs in Python

Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of their deterministic counterparts, which are typically formulated first. A second factor relates to the difficulty of solving stochastic programming models, particularly in the mixed-integer, non-linear, and/or multi-stage cases. Intricate, configurable, and parallel decomposition strategies are frequently required to achieve tractable run-times on large-scale problems. We simultaneously address both of these factors in our PySP software package, which is part of the Coopr open-source Python repository for optimization; the latter is distributed as part of IBM’s COIN-OR repository. To formulate a stochastic program in PySP, the user specifies both the deterministic base model (supporting linear, non-linear, and mixed-integer components) and the scenario tree model (defining the problem stages and the nature of uncertain parameters) in the Pyomo open-source algebraic modeling language. Given these two models, PySP provides two paths for solution of the corresponding stochastic program. The first alternative involves passing an extensive form to a standard deterministic solver. For more complex stochastic programs, we provide an implementation of Rockafellar and Wets’ Progressive Hedging algorithm. Our particular focus is on the use of Progressive Hedging as an effective heuristic for obtaining approximate solutions to multi-stage stochastic programs. By leveraging the combination of a high-level programming language (Python) and the embedding of the base deterministic model in that language (Pyomo), we are able to provide completely generic and highly configurable solver implementations. PySP has been used by a number of research groups, including our own, to rapidly prototype and solve difficult stochastic programming problems.     

Some comments on preference order dynamic programming models

A simple deterministic dynamic programming model is used as a general framework for the analysis of stochastic versions of three classical optimization problems: knapsack, traveling salesperson, and assembly line balancing problems. It is shown that this model can provide an alternative to the preference order models proposed for these problems. Counterexample to the optimality of the preference order models are presented.