Stochastic Programming

Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service System Staffing and Scheduling with Arrival Rate Uncertainty

  • Merve Bodur
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , , , ,

    We study server scheduling in multiclass service systems under stochastic uncertainty in the customer arrival volumes. Common practice in such systems is to first identify staffing levels, and then determine schedules for the servers that cover these targets. We propose a new stochastic integer programming model that integrates these two decisions, which can yield lower … Read more

    Optimal scenario set partitioning for multistage stochastic programming with the progressive hedging algorithm

  • Fabian Bastin
  • Pierre-Luc Carpentier
  • Michel Gendreau
    • Categories Stochastic Programming Tags , , ,

    In this paper, we propose a new approach to reduce the total running time (RT) of the progressive hedging algorithm (PHA) for solving multistage stochastic programs (MSPs) defined on a scenario tree. Instead of using the conventional scenario decomposition scheme, we apply a multi-scenario decomposition scheme and partition the scenario set in order to minimize … Read more

    Dynamic Linear Programming Games with Risk-Averse Players

  • Alejandro Toriello
  • Nelson A. Uhan
    • Categories Applications - OR and Management Sciences, Game Theory, Stochastic Programming Tags , ,

    Motivated by situations in which independent agents, or players, wish to cooperate in some uncertain endeavor over time, we study dynamic linear programming games, which generalize classical linear production games to multi-period settings under uncertainty. We specifically consider that players may have risk-averse attitudes towards uncertainty, and model this risk aversion using coherent conditional risk … Read more

    Time Consistency Versus Law Invariance in Multistage Stochastic Optimization with Coherent Risk Measures: Multilevel Optimization Modeling and Computational Complexity

  • Jonathan Eckstein
    • Categories Stochastic Programming Tags , ,

    Coherent risk measures have become a popular tool for incorporating risk aversion into stochastic optimization models. For dynamic models in which un-certainly is resolved at more than one stage, however, use of coherent risk measures within a standard single-level optimization framework presents the modeler with an uncomfortable choice between two desirable model properties, time consistency … Read more

    Optimization Models for Differentiating Quality of Service Levels in Probabilistic Network Capacity Design Problems

  • Zhihao Chen
  • Siqian Shen
    • Categories Network Optimization, Stochastic Programming, Transportation

    This paper develops various chance-constrained models for optimizing the probabilistic network design problem (PNDP), where we differentiate the quality of service (QoS) and measure the related network performance under uncertain demand. The upper level problem of PNDP designs continuous/discrete link capacities shared by multi-commodity flows, and the lower level problem differentiates the corresponding QoS for … Read more

    Data-Driven Chance Constrained Stochastic Program

  • Yongpei Guan
  • Ruiwei Jiang
    • Categories Stochastic Programming

    Chance constrained programming is an effective and convenient approach to control risk in decision making under uncertainty. However, due to unknown probability distributions of random parameters, the solution obtained from a chance constrained optimization problem can be biased. In addition, instead of knowing the true distributions of random parameters, in practice, only a series of … Read more

    Ambiguous Probabilistic Programs

  • Jeff L Hong
  • Anthony Man-Cho So
  • Zhaolin Hu
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Probabilistic programs are widely used decision models. When implemented in practice, however, there often exists distributional ambiguity in these models. In this paper, we model the ambiguity using the likelihood ratio (LR) and use LR to construct various ambiguity sets. We consider ambiguous probabilistic programs which optimize under the worst case. Ambiguous probabilistic programs can … Read more

    Ancestral Benders’ Cuts and Multi-term Disjunctions for Mixed-Integer Recourse Decisions in Stochastic Programming

  • Yunwei Qi
  • Suvrajeet Sen
    • Categories Branch and Cut Algorithms, Stochastic Programming Tags , ,

    This paper focuses on solving two-stage stochastic mixed integer programs (SMIPs) with general mixed integer decision variables in both stages. We develop a decomposition algorithm in which the first stage approximation is solved using a branch-and-bound tree with nodes inheriting Benders’ cuts that are valid for their ancestor nodes. In addition, we develop two closely … Read more

    Separable Approximations and Decomposition Methods for the Augmented Lagrangian

  • Burak Buke
  • Peter Richtarik
  • Rachael Tappenden
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , , , , , ,

    In this paper we study decomposition methods based on separable approximations for minimizing the augmented Lagrangian. In particular, we study and compare the Diagonal Quadratic Approximation Method (DQAM) of Mulvey and Ruszczy\'{n}ski and the Parallel Coordinate Descent Method (PCDM) of Richt\'{a}rik and Tak\'{a}\v{c}. We show that the two methods are equivalent for feasibility problems up … Read more

    A Short Proof of Strassen’s Theorem Using Convex Analysis

  • Benjamin Armbruster
    • Categories Stochastic Programming Tags

    We give a simple proof of Strassen’s theorem on stochastic dominance using linear programming duality, without requiring measure-theoretic arguments. The result extends to generalized inequalities using conic optimization duality and provides an additional, intuitive optimization formulation for stochastic dominance. Citation Northwestern Univ., Aug., 2013 Article Download View A Short Proof of Strassen's Theorem Using Convex … Read more