Stochastic Programming

Skip or Insert? A Priori Optimization for the Vehicle Routing Problem with Time Windows and Stochastic Customers

  • Yulin Han
  • Hande Yaman
    • Categories Combinatorial Optimization, Production and Logistics, Stochastic Programming Tags , , , , , , ,

    We study an extension of the vehicle routing problem with time windows by incorporating stochastic customers, i.e., ad-hoc service requests. The uncertainty in stochastic customers is captured through scenarios. Two a priori optimization approaches, a classical and a new one lead to two different problems, both of which are modeled as scenario-based two-stage stochastic programs. … Read more

    Distributionally Robust Optimization with General Uncertainty Structure

  • Judith Brugman
  • Dimitris Bertsimas
  • Johan Van Leeuwaarden
  • Dick den Hertog
    • Categories Nonlinear Optimization, Robust Optimization, Stochastic Programming Tags , , , , , ,

    We develop an exact solution framework for a broad class of Distributionally Robust Optimization (DRO) problems with general uncertainty structure. Within the class of moment- and confidence-set-based ambiguity sets, existing exact methods are largely limited to max-of-affine functions under ambiguity sets with strictly nested confidence sets. To enlarge this scope while preserving tractability, we introduce … Read more

    Stage-wise hybrid nested Benders’ decomposition-stochastic dual dynamic programming for virtual power plants

  • Youngdoo Choi
  • Seokwoo Kim
  • Sanghyeon Bae
  • Dong Gu Choi
    • Categories Dynamic Programming, Energy, Stochastic Programming Tags , , ,

    Participants in energy markets make sequential decisions across multiple time horizons under uncertainty, leading to large-scale multistage stochastic optimization problems. Stochastic dual dynamic programming is widely used for its tractability, but its application to modern energy markets is challenged by nested dependencies induced by participation across multiple interrelated markets under increasing uncertainty from distributed energy … Read more

    Scalable Finite Adaptability via Polyhedral Partition and Learning

  • Zolykha Rezaei
  • Ningji Wei
  • Eojin Han
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming Tags , ,

    We study finite adaptability for decision-making under uncertainty, where a small set of candidate solutions is prepared in advance and the best response is selected after uncertainty is realized. While existing methods have made significant progress on exact formulations, scalability remains a persistent challenge due to (i) the combinatorial nature of assigning decisions to uncertainty … Read more

    Relief-based Anesthesiologist Scheduling with Stochastic Surgery Durations

  • Ankit Bansal
  • Osman Y. Ozaltin
    • Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming Tags , , ,

    We present a two-stage stochastic programming model for scheduling anesthesiologists to operating rooms under uncertainty in surgery durations. The proposed model takes a relief order to balance anesthesiologists’ workload as input and captures the trade-offs between anesthesiologist relief times, handoffs and under-staffing. To address the computational challenges of solving the proposed model, we derive supervalid … Read more

    Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization

  • Anthony Palmieri
  • Francesco Rinaldi
  • Sara Shashaani
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , ,

    We propose and analyze a stochastic direct-search method for unconstrained zeroth-order minimization of locally Lipschitz, possibly nonsmooth, objectives. The method combines random polling directions with a stochastic extrapolating line search based on a sufficient-decrease test of order \(p\). Under conditional accuracy assumptions on the stochastic estimates, which can be verified for mean-zero finite-higher-moment oracle noise … Read more

    Stochastic Bilevel Optimization for the Network Design of Multimodal Transit Systems with Heterogeneous Rider Preferences under Uncertain Travel Times and Demand

  • Yiling Zhang
  • Beste Basciftci
    • Categories Bilevel Optimization, Stochastic Programming, Transportation

    Designing efficient and user-friendly multimodal transit networks is critical for modern urban mobility. We study a novel stochastic multimodal transit network design problem that integrates fixed-route services with on-demand shuttles, explicitly accounting for heterogeneous rider preferences, uncertain travel times, and passenger demand. The hierarchical decision-making process is modeled using a two-stage stochastic bilevel optimization problem, … Read more

    Stochastic convergence of parallel asynchronous adaptive first-order methods

  • Serge Gratton
  • Philippe L. Toint
    • Categories Data Science Algorithms, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

    A new class of asynchronous adaptive first-order optimization methods is introduced, comprising asynchronous variants of several popular algorithms. Versions of these methods using momentum and/or inexact normalization are also considered. The convergence of methods in the class on non-convex functions is analyzed in a fully stochastic setting, and is shown to be (up to logarithmic … Read more

    Non-convergence Analysis of Probabilistic Direct Search

  • Cunxin Huang
  • Zaikun Zhang
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , ,

    We present a non-convergence theory for probabilistic direct search, a randomized derivative-free optimization method, where non-convergence means the failure to produce iterates that achieve stationarity asymptotically. The motivation is to understand whether the submartingale-like assumption in the existing convergence theory is essential or merely an artifact of the analysis techniques. For convex objectives, we prove … Read more

    Lipschitz Gradient Guarantees for Probability Functions and a New Algorithm for Probability Maximization

  • Wim van Ackooij
  • Carolina Chiu
  • Welington de Oliveira
  • Pedro Pérez-Aros
    • Categories Stochastic Programming Tags , , ,

    This work studies probability functions that appear in stochastic programming models. Although their differentiability has been widely investigated, the Lipschitz continuity of their gradients, crucial for the design and analysis of modern optimization algorithms, has received little attention. We develop a general framework that ensures differentiability and gradient Lipschitz continuity under practical conditions. Our framework … Read more