Stochastic Programming

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

  • Csaba I. Fábián
  • Achim Koberstein
  • Leena Suhl
  • Christian Wolf
    • Categories Optimization Software Benchmark, Stochastic Programming Tags , , ,

    Traditionally, two variants of the L-shaped method based on Benders’ decomposition principle are used to solve two-stage stochastic programming problems: the single-cut and the multi-cut version. The concept of an oracle with on-demand accuracy was originally proposed in the context of bundle methods for unconstrained convex optimzation to provide approximate function data and subgradients. In … Read more

    Decomposition Algorithm for Optimizing Multi-server Appointment Scheduling with Chance Constraints

  • Yan Deng
  • Siqian Shen
    • Categories Cutting Plane Approaches, Stochastic Programming

    We schedule appointments with random service durations on multiple servers with operating time limits. We minimize the costs of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server overtime. Using finite samples of the uncertainty, we formulate the problem as a mixed-integer linear program, and propose a two-stage … Read more

    Optimization over the Pareto Outcome set associated with a Convex Bi-Objective Optimization Problem: Theoretical Results, Deterministic Algorithm and Application to the Stochastic case

  • Henri Bonnel
  • Julien Collonge
    • Categories Multi-Criteria Optimization, Stochastic Programming

    Our paper consists of two main parts. In the first one, we deal with the deterministic problem of minimizing a real valued function $f$ over the Pareto set associated with a deterministic convex bi-objective optimization problem (BOP), in the particular case where $f$ depends on the objectives of (BOP), i.e. we optimize over the Pareto … Read more

    A Stochastic Quasi-Newton Method for Large-Scale Optimization

  • Richard H. Byrd
  • Samantha Hansen
  • Jorge Nocedal
  • Yoram Singer
    • Categories Data-Mining, Stochastic Programming, Unconstrained Optimization Tags , , ,

    Abstract The question of how to incorporate curvature information in stochastic approximation methods is challenging. The direct application of classical quasi- Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust … Read more

    Mitigating Uncertainty via Compromise Decisions in Two-stage Stochastic Linear Programming

  • Suvrajeet Sen
  • Yifan Liu
    • Categories Stochastic Programming Tags , ,

    Stochastic Programming (SP) has long been considered as a well-justified yet computationally challenging paradigm for practical applications. Computational studies in the literature often involve approximating a large number of scenarios by using a small number of scenarios to be processed via deterministic solvers, or running Sample Average Approximation on some genre of high performance machines … Read more

    Confidence Levels for CVaR Risk Measures and Minimax Limits

  • Edward Anderson
  • Huifu Xu
  • Dali Zhang
    • Categories Robust Optimization, Semi-infinite Programming, Stochastic Programming

    Conditional value at risk (CVaR) has been widely used as a risk measure in finance. When the confidence level of CVaR is set close to 1, the CVaR risk measure approximates the extreme (worst scenario) risk measure. In this paper, we present a quantitative analysis of the relationship between the two risk measures and its … Read more

    A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management

  • Kibaek Kim
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Scheduling, Stochastic Programming Tags , , , , ,

    We study the problem of integrated staffing and scheduling under demand uncertainty. The problem is formulated as a two-stage stochastic integer program with mixed-integer recourse. The here-and-now decision is to find initial staffing levels and schedules, well ahead in time. The wait-and-see decision is to adjust these schedules at a time epoch closer to the … Read more

    Generalized Gauss Inequalities via Semidefinite Programming

  • Paul J. Goulart
  • Daniel Kuhn
  • Bart Paul Gerard Van Parys
    • Categories Convex Optimization, Statistics, Stochastic Programming Tags , ,

    A sharp upper bound on the probability of a random vector falling outside a polytope, based solely on the first and second moments of its distribution, can be computed efficiently using semidefinite programming. However, this Chebyshev-type bound tends to be overly conservative since it is determined by a discrete worst-case distribution. In this paper we … Read more

    Benders, Nested Benders and Stochastic Programming: An Intuitive Introduction

  • James Murphy
    • Categories Stochastic Programming Tags , , , , , , ,

    This article aims to explain the Nested Benders algorithm for the solution of large-scale stochastic programming problems in a way that is intelligible to someone coming to it for the first time. In doing so it gives an explanation of Benders decomposition and of its application to two-stage stochastic programming problems (also known in this … Read more

    Penalty Methods with Stochastic Approximation for Stochastic Nonlinear Programming

  • Shiqian Ma
  • Xiao Wang
  • Ya-xiang Yuan
    • Categories Nonlinear Optimization, Stochastic Programming

    In this paper, we propose a class of penalty methods with stochastic approximation for solving stochastic nonlinear programming problems. We assume that only noisy gradients or function values of the objective function are available via calls to a stochastic first-order or zeroth-order oracle. In each iteration of the proposed methods, we minimize an exact penalty … Read more