stochastic programming

Finite-Sample Optimality and Constraint Satisfaction: Learning-Based Optimal Control in Dynamic Dispatch Networks

  • Moustafa Rashidy
    • Categories Data Science Theory, Production and Logistics, Transportation Tags , ,

    Dynamic dispatch networks in logistics and transportation require real-time, constraint-aware decision-making under stochastic demand. This paper bridges mathematical optimization, optimal control theory, and reinforcement learning by establishing non-asymptotic theoretical guarantees for learning-based optimal control in constrained stochastic dispatch systems. We formulate the problem as a constrained Markov decision process, enforce feasibility via a projection-based policy … Read more

    Pseudo-Compact Formulations and Branch-and-Cut Approaches for the Capacitated Vehicle Routing Problem with Stochastic Demands

  • Caio Tomazella
  • Pedro Munari
  • Reinaldo Morabito
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming Tags , , ,

    In this paper, we address the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD), in which routes are planned a priori and recourse actions are performed to ensure demand fulfillment. These recourse actions are defined through policies and may include replenishment trips or demand backlogging subject to penalties. We develop the first family of pseudo-compact … Read more

    On vehicle routing problems with stochastic demands — Scenario-optimal recourse policies

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Stochastic Programming, Transportation Tags , ,

    Two-Stage Vehicle Routing Problems with Stochastic Demands (VRPSDs) form a class of stochastic combinatorial optimization problems where routes are planned in advance, demands are revealed upon vehicle arrival, and recourse actions are triggered whenever capacity is exceeded. Following recent works, we consider VRPSDs where demands are given by an empirical probability distribution of scenarios. Existing … Read more

    Risk-Averse Stochastic User Equilibrium on Uncertain Transportation Networks

  • Wencheng Bao
  • Chrysafis Vogiatzis
  • Eleftheria Kontou
    • Categories Network Optimization, Robust Optimization, Transportation Tags , , , , ,

    Extreme weather events, like flooding, disrupt urban transportation networks by reducing speeds and capacities, and by closing roadways. These hazards create regime-dependent uncertainty in link performance and travel-time distribution tails, challenging conventional traffic assignment that relies on the expectation of cost or mean excess of cost summation. This study develops a risk- and ambiguity-aware traffic … Read more

    Normalization of ReLU Dual for Cut Generation in Stochastic Mixed-Integer Programs

  • Akul Bansal
  • Simge Küçükyavuz
    • Categories Stochastic Programming Tags , ,

    We study the Rectified Linear Unit (ReLU) dual, an existing dual formulation for stochastic programs that reformulates non-anticipativity constraints using ReLU functions to generate tight, non-convex, and mixed-integer representable cuts. While this dual reformulation guarantees convergence with mixed-integer state variables, it admits multiple optimal solutions that can yield weak cuts. To address this issue, we … Read more

    Primal-dual resampling for solution validation in convex stochastic programming

  • Yi Chu
  • Susan R. Hunter
  • Raghu Pasupathy
    • Categories Convex Optimization, Optimization in Data Science, Stochastic Programming Tags , ,

    Suppose we wish to determine the quality of a candidate solution to a convex stochastic program in which the objective function is a statistical functional parameterized by the decision variable and known deterministic constraints may be present. Inspired by stopping criteria in primal-dual and interior-point methods, we develop cancellation theorems that characterize the convergence of … Read more

    Stochastic Mixed-Integer Programming: A Survey

  • Ward Romeijnders
  • Yihang Zhang
  • Suvrajeet Sen
    • Categories Stochastic Programming Tags ,

    The goal of this survey is to provide a road-map for exploring the growing area of stochastic mixed-integer programming (SMIP) models and algorithms. We provide a comprehensive overview of existing decomposition algorithms for two-stage SMIPs, including Dantzig-Wolfe decomposition, dual decomposition, Lagrangian cuts, and decomposition approaches using parametric cutting planes and scaled cuts. Moreover, we explicitly … Read more

    On vehicle routing problems with stochastic demands — Generic disaggregated integer L-shaped formulations

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Stochastic Programming, Transportation Tags , , ,

    We study the vehicle routing problem with stochastic demands (VRPSD), an important variant of the classical capacitated vehicle routing problem in which customer demands are modeled as random variables. We develop the first algorithm for the VRPSD in the case where the demands are given by an empirical probability distribution of scenarios — a data-driven … Read more

    An extension of an interior-point method to include risk aversion in large-scale multistage stochastic optimization

  • Jordi Castro
  • Laureano F. Escudero
  • Juan F. Monge
    • Categories Linear Programming, Stochastic Programming Tags , , , ,

    In the earlier paper “On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach, European Journal of Operational Research, 310 (2023), 268–285” the authors presented a novel approach based on a specialized interior-point method (IPM) for solving (risk neutral) large-scale multistage stochastic optimization problems. The method computed the Newton direction by combining … Read more

    Approximating inequality systems within probability functions: studying implications for problems and consistency of first-order information

  • Wim van Ackooij
  • Pedro Pérez-Aros
  • David Villacís
    • Categories Nonsmooth Optimization, Stochastic Programming Tags , , , ,

    In this work, we are concerned with the study of optimization problems featuring so-called probability or chance constraints. Probability constraints measure the level of satisfaction of an underlying random inequality system and ensure that this level is high enough. Such an underlying inequality system could be expressed by an abstractly known or perhaps costly to … Read more