Stochastic Programming

PIPS-SBB: A parallel distributed-memory branch-and-bound algorithm for stochastic mixed-integer programs

  • Lluís-Miquel Munguía
  • Deepak Rajan
  • Geoffrey Oxberry
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    Stochastic mixed-integer programs (SMIPs) deal with optimization under uncertainty at many levels of the decision-making process. When solved as extensive formulation mixed- integer programs, problem instances can exceed available memory on a single workstation. To overcome this limitation, we present PIPS-SBB: a distributed-memory parallel stochastic MIP solver that takes advantage of parallelism at multiple levels … Read more

    Bulk Ship Fleet Renewal and Deployment under Uncertainty: A Multi-Stage Stochastic Programming Approach

  • Ayse Nur Arslan
  • Dimitri J. Papageorgiou
    • Categories Stochastic Programming, Supply Chain Management, Transportation Tags , , , , ,

    We study a maritime fleet renewal and deployment problem under demand and charter cost uncertainty. A decision-maker for an industrial bulk shipping company must determine a suitable fleet size, mix, and deployment strategy to satisfy stochastic demand over a given planning horizon. She may acquire vessels in two ways: time chartering and voyage chartering. Time … Read more

    Data-Driven Inverse Optimization with Imperfect Information

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
  • Soroosh Shafieezadeh-Abadeh
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Stochastic Programming Tags , ,

    In data-driven inverse optimization an observer aims to learn the preferences of an agent who solves a parametric optimization problem depending on an exogenous signal. Thus, the observer seeks the agent’s objective function that best explains a historical sequence of signals and corresponding optimal actions. We focus here on situations where the observer has imperfect … Read more

    Distributionally Robust Stochastic Programming

  • Alexander Shapiro
    • Categories Robust Optimization, Stochastic Programming Tags , , , , ,

    In this paper we study distributionally robust stochastic programming in a setting where there is a specified reference probability measure and the uncertainty set of probability measures consists of measures in some sense close to the reference measure. We discuss law invariance of the associated worst case functional and consider two basic constructions of such … Read more

    Distributionally robust inventory control when demand is a martingale

  • David A. Goldberg
  • Linwei Xin
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , , , , ,

    Demand forecasting plays an important role in many inventory control problems. To mitigate the potential harms of model misspecification in this context, various forms of distributionally robust optimization have been applied. Although many of these methodologies suffer from the problem of time-inconsistency, the work of Klabjan, Simchi-Levi and Song [85] established a general time-consistent framework … Read more

    Branch and Price for Chance Constrained Bin Packing

  • Brian T. Denton
  • Xiaolan Xie
  • Z. Zhang
    • Categories Applications - OR and Management Sciences, Stochastic Programming

    This article considers two versions of the stochastic bin packing problem with chance constraints. In the first version, we formulate the problem as a two-stage stochastic integer program that considers item-to-bin allocation decisions in the context of chance constraints on total item size within the bins. Next, we describe a distributionally robust formulation of the … Read more

    Scenario Decomposition for 0-1 Stochastic Programs: Improvements and Asynchronous Implementation

  • Shabbir Ahmed
  • Deepak Rajan
  • Kevin Ryan
    • Categories Parallel Algorithms, Stochastic Programming Tags , ,

    A recently proposed scenario decomposition algorithm for stochastic 0-1 programs finds an optimal solution by evaluating and removing individual solutions that are discovered by solving scenario subproblems. In this work, we develop an asynchronous, distributed implementation of the algorithm which has computational advantages over existing synchronous implementations of the algorithm. Improvements to both the synchronous … Read more

    Ambiguous Joint Chance Constraints under Mean and Dispersion Information

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Vladimir Roitch
  • Wolfram Wiesemann
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    We study joint chance constraints where the distribution of the uncertain parameters is only known to belong to an ambiguity set characterized by the mean and support of the uncertainties and by an upper bound on their dispersion. This setting gives rise to pessimistic (optimistic) ambiguous chance constraints, which require the corresponding classical chance constraints … Read more

    A two-level SDDP Solving Strategy with Risk-Averse multivariate reservoir Storage Levels for Long Term power Generation Planning

  • Andre Diniz
  • Maria Elvira P. Maceira
  • D.D. Penna
  • C. L. Vasconcellos
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    Power generation planning in large-scale hydrothermal systems is a complex optimization task, specially due to the high uncertainty in the inflows to hydro plants. Since it is impossible to traverse the huge scenario tree of the multi-stage problem, stochastic dual dynamic programming (SDDP) is the leading optimization technique to solve it, originally from an expected-cost … Read more

    Revisiting some results on the sample complexity of multistage stochastic programs and some extensions

  • Marcus de Mendes C. R. Reaiche
    • Categories Stochastic Programming Tags , , ,

    In this work we present explicit definitions for the sample complexity associated with the Sample Average Approximation (SAA) Method for instances and classes of multistage stochastic optimization problems. For such, we follow the same notion firstly considered in Kleywegt et al. (2001). We define the complexity for an arbitrary class of problems by considering its … Read more