Stochastic Programming

Incorporating Service Reliability in Multi-depot Vehicle Scheduling: A Chance-Constrained Approach

  • Margarita P Castro
  • Merve Bodur
  • Amer Shalaby
    • Categories Cutting Plane Approaches, Stochastic Programming, Transportation Tags , , ,

    The multi-depot vehicle scheduling problem (MDVSP) is a critical planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. Our model guarantees service reliability measured by on-time performance (OTP), a … Read more

    Benders decomposition with scaled cuts for multistage stochastic mixed-integer programs

  • Ward Romeijnders
  • Niels van der Laan
    • Categories Stochastic Programming Tags , ,

    We consider Benders decomposition algorithms for multistage stochastic mixed-integer programs (SMIPs) with general mixed-integer decision variables at every node in the scenario tree. We derive a hierarchy of convex polyhedral lower bounds for the value functions and expected cost to-go functions in multistage SMIPs using affine parametric cutting planes in extended spaces for the feasible … Read more

    MUSE-BB: A Decomposition Algorithm for Nonconvex Two-Stage Problems using Strong Multisection Branching

  • Marco Langiu
  • Manuel Dahmen
  • D. Bongartz
  • Alexander Mitsos
    • Categories Global Optimization, Parallel Algorithms, Stochastic Programming Tags , , , ,

    We present MUSE-BB, a branch-and-bound (B&B) based decomposition algorithm for the deterministic global solution of nonconvex two-stage stochastic programming problems. In contrast to three recent decomposition algorithms, which solve this type of problem in a projected form by nesting an inner B&B in an outer B&B on the first-stage variables, we branch on all variables … Read more

    Stackelberg Games with k-Submodular Function under Distributional Risk-Receptiveness and Robustness

  • Seonghun Park
  • Manish Bansal
    • Categories Game Theory, Robust Optimization, Stochastic Programming

    We study submodular optimization in adversarial context, applicable to machine learning problems such as feature selection using data susceptible to uncertainties and attacks. We focus on Stackelberg games between an attacker (or interdictor) and a defender where the attacker aims to minimize the defender’s objective of maximizing a k-submodular function. We allow uncertainties arising from … Read more

    Exploiting Overlap Information in Chance-constrained Program with Random Right-hand Side

  • Wei Lv
  • Wei-Kun Chen
  • Yu-Hong Dai
  • Xiao-Jiao Tong
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We consider the chance-constrained program (CCP) with random right-hand side under a finite discrete distribution. It is known that the standard mixed integer linear programming (MILP) reformulation of the CCP is generally difficult to solve by general-purpose solvers as the branch-and-cut search trees are enormously large, partly due to the weak linear programming relaxation. In … Read more

    Optimization without Retraction on the Random Generalized Stiefel Manifold

  • Simon Vary
  • Bin Gao
  • Pierre-Antoine Absil
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , ,

    Optimization over the set of matrices \(X\) that satisfy \(X^\top B X = I_p\), referred to as the generalized Stiefel manifold, appears in many applications involving sampled covariance matrices such as the canonical correlation analysis (CCA), independent component analysis (ICA), and the generalized eigenvalue problem (GEVP). Solving these problems is typically done by iterative methods … Read more

    A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Set

  • Man-Chung Yue
  • Yves Rychener
  • Daniel Kuhn
  • Viet Anh Nguyen
    • Categories Robust Optimization, Stochastic Programming

    The state-of-the-art methods for estimating high-dimensional covariance matrices all shrink the eigenvalues of the sample covariance matrix towards a data-insensitive shrinkage target. The underlying shrinkage transformation is either chosen heuristically – without compelling theoretical justification – or optimally in view of restrictive distributional assumptions. In this paper, we propose a principled approach to construct covariance … Read more

    Subgradient Convergence Implies Subdifferential Convergence on Weakly Convex Functions: With Uniform Rates Guarantees

  • Feng Ruan
    • Categories Nonsmooth Optimization, Stochastic Programming

    In nonsmooth, nonconvex stochastic optimization, understanding the uniform convergence of subdifferential mappings is crucial for analyzing stationary points of sample average approximations of risk as they approach the population risk. Yet, characterizing this convergence remains a fundamental challenge. This work introduces a novel perspective by connecting the uniform convergence of subdifferential mappings to that of subgradient … Read more

    Multistage Stochastic Facility Location under Facility Disruption Uncertainty

  • Bonn Kleiford Seranilla
  • Nils Löhndorf
    • Categories Production and Logistics, Stochastic Programming, Supply Chain Management Tags , , ,

    We consider a multistage variant of the classical stochastic capacitated facility location problem under facility disruption uncertainty. Two solution algorithms for this problem class are presented: (1) stochastic dual dynamic integer programming (SDDiP), the state-of-the-art algorithm for solving multistage stochastic integer programs, and (2) shadow price approximation (SPA), an algorithm utilizing trained parameters of the … Read more

    A computational study of cutting-plane methods for multi-stage stochastic integer programs

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

    We report a computational study of cutting plane algorithms for multi-stage stochastic mixed-integer programming models with the following cuts: (i) Benders’, (ii) Integer L-shaped, and (iii) Lagrangian cuts. We first show that Integer L-shaped cuts correspond to one of the optimal solutions of the Lagrangian dual problem, and, therefore, belong to the class of Lagrangian … Read more