Stochastic Programming

A Cutting Surface Method for Uncertain Linear Programs with Polyhedral Stochastic Dominance Constraints

  • Tito Homem-de-Mello
  • Sanjay Mehrotra
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , ,

    In this paper we study linear optimization problems with multi-dimensional linear positive second-order stochastic dominance constraints. By using the polyhedral properties of the second- order linear dominance condition we present a cutting-surface algorithm, and show its finite convergence. The cut generation problem is a difference of convex functions (DC) optimization problem. We exploit the polyhedral … Read more

    A Multistage Stochastic Programming Approach to Open Pit Mine Production Scheduling with Uncertain Geology

  • Natashia Boland
  • Gary Froyland
  • Irina Dumitrescu
    • Categories Applications - OR and Management Sciences, Integer Programming, Stochastic Programming Tags , , ,

    The Open Pit Mine Production Scheduling Problem (OPMPSP) studied in recent years is usually based on a single geological estimate of material to be excavated and processed over a number of decades. However techniques have now been developed to generate multiple stochastic geological estimates that more accurately describe the uncertain geology. While some attempts have … Read more

    A Framework for Optimization under Ambiguity

  • David Wozabal
    • Categories Global Optimization Applications, Robust Optimization, Stochastic Programming

    In this paper, single stage stochastic programs with ambiguous distributions for the involved random variables are considered. Though the true distribution is unknown, existence of a reference measure P enables the construction of non-parametric ambiguity sets as Kantorovich balls around P. The resulting robustified problems are infinite optimization problems and can therefore not be solved … Read more

    Chance-constrained optimization via randomization: feasibility and optimality

  • Marco C. Campi
  • Simone Garatti
    • Categories Convex Optimization, Semi-infinite Programming, Stochastic Programming Tags , ,

    In this paper we study the link between a semi-infinite chance-constrained optimization problem and its randomized version, i.e. the problem obtained by sampling a finite number of its constraints. Extending previous results on the feasibility of randomized convex programs, we establish here the feasibility of the solution obtained after the elimination of a portion of … Read more

    Progressive Hedging Innovations for a Class of Stochastic Resource Allocation Problems

  • David Strip
  • Jean-Paul Watson
  • David L. Woodruff
    • Categories Production and Logistics, Stochastic Programming Tags , ,

    Progressive hedging (PH) is a scenario-based decomposition technique for solving stochastic programs. While PH has been successfully applied to a number of problems, a variety of issues arise when implementing PH in practice, especially when dealing with very difficult or large-scale mixed-integer problems. In particular, decisions must be made regarding the value of the penalty … Read more

    The Facility Location Problem with Bernoulli Demands

  • Maria Albareda-Sambola
  • Francisco Saldanha-da-Gama
  • Elena Fernandez
    • Categories Stochastic Programming Tags ,

    In this paper we address a discrete capacitated facility location problem in which customers have Bernoulli demands. The problem is formulated as a two-stage stochastic program. The goal is to define an a priori solution for the location of the facilities and for the allocation of customers to the operating facilities that minimize the expected … Read more

    Efficient Methods for Stochastic Composite Optimization

  • Guanghui Lan
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , , , ,

    This paper considers an important class of convex programming problems whose objective function $\Psi$ is given by the summation of a smooth and non-smooth component. Further, it is assumed that the only information available for the numerical scheme to solve these problems is the subgradient of $\Psi$ contaminated by stochastic noise. Our contribution mainly consists … Read more

    Scalable Heuristics for Stochastic Programming with Scenario Selection

  • Jean-Paul Watson
  • Roger J.B. Wets
  • David L. Woodruff
    • Categories Stochastic Programming Tags , , ,

    We describe computational procedures to solve a wide-ranging class of stochastic programs with chance constraints where the random components of the problem are discretely distributed. Our procedures are based on a combination of Lagrangian relaxation and scenario decomposition, which we solve using a novel variant of Rockafellar and Wets’ progressive hedging algorithm. Experiments demonstrate the … Read more

    Validation Analysis of Robust Stochastic Approximation Method

  • Guanghui Lan
  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , , , , , ,

    The main goal of this paper is to develop accuracy estimates for stochastic programming problems by employing robust stochastic approximation (SA) type algorithms. To this end we show that while running a Robust Mirror Descent Stochastic Approximation procedure one can compute, with a small additional effort, lower and upper statistical bounds for the optimal objective … Read more

    Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion

  • Dimitris Bertsimas
  • Xuan Vinh Doan
  • Karthik Natarajan
  • Chung-Piaw Teo
    • Categories Semi-definite Programming, Stochastic Programming

    In this paper, we propose a semidefinite optimization (SDP) based model for the class of minimax two-stage stochastic linear optimization problems with risk aversion. The distribution of the second-stage random variables is assumed to be chosen from a set of multivariate distributions with known mean and second moment matrix. For the minimax stochastic problem with … Read more