We propose the policy graph as a way of formulating multistage stochastic optimization problems. We also propose an extension to the stochastic dual dynamic programming algorithm to solve a class of problems formulated as a policy graph. This class includes discrete-time, infinite horizon, multistage stochastic optimization problems with continuous state and control variables. Article Download … Read more
We propose a decomposition algorithm for multistage stochastic programming that resembles the progressive hedging method of Rockafellar and Wets, but is provably capable of several forms of asynchronous operation. We derive the method from a class of projective operator splitting methods fairly recently proposed by Combettes and Eckstein, significantly expanding the known applications of those … Read more
In this paper, we derive deterministic inner approximations for single and joint probabilistic constraints based on classical inequalities from probability theory such as the one-sided Chebyshev inequality, Bernstein inequality, Chernoff inequality and Hoeffding inequality (see Pinter 1989). New assumptions under which the bounds based approximations are convex allowing to solve the problem efficiently are derived. … Read more
We propose a novel way of applying cutting plane techniques to two-stage mixed-integer stochastic programs. Instead of using cutting planes that are always valid, our idea is to apply inexact cutting planes to the second-stage feasible regions that may cut away feasible integer second-stage solutions for some scenarios and may be overly conservative for others. … Read more
Stochastic decomposition (SD) has been a computationally effective approach to solve large-scale stochastic programming (SP) problems arising in practical applications. By using incremental sampling, this approach is designed to discover an appropriate sample size for a given SP instance, thus precluding the need for either scenario reduction or arbitrary sample sizes to create sample average … Read more
In this paper, we present a new stochastic mixed-integer linear programming model for the Stochastic Outpatient Procedure Scheduling Problem (SOPSP). In this problem, we schedule a day’s worth of procedures for a single provider, where each procedure has a known type and associated probability distribution of random duration. Our objective is to minimize the expectation … Read more
We introduce an extension of Stochastic Dual Dynamic Programming (SDDP) to solve stochastic convex dynamic programming equations. This extension applies when some or all primal and dual subproblems to be solved along the forward and backward passes of the method are solved with bounded errors (inexactly). This inexact variant of SDDP is described both for … Read more
In this paper, we discuss input modeling and solution techniques for several classes of chance constrained programs (CCPs). We propose to use Gaussian mixture models (GMM), a semi-parametric approach, to fit the data available and to model the randomness. We demonstrate the merits of using GMM. We consider several scenarios that arise from practical applications … Read more
Bellman formulated a vague principle for optimization over time, which characterizes optimal policies by stating that a decision maker should not regret previous decisions retrospectively. This paper addresses time consistency in stochastic optimization. The problem is stated in generality first. The paper discusses time consistent decision-making by addressing risk measures which are recursive, nested, dynamically … Read more
This paper presents stochastic decomposition (SD) algorithms for two classes of stochastic programming problems: 1) two-stage stochastic quadratic-linear programming (SQLP) in which a quadratic program defines the objective function in the first stage and a linear program defines the value function in the second stage; 2) two-stage stochastic quadratic-quadratic programming (SQQP) which has quadratic programming … Read more