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

    Covering for Set-Valued Mappings in the Absence of Metric Regularity

  • Mario Jelitte
  • Alexey F. Izmailov
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    Covering properties build the foundation of stability and sensitivity analysis of solutions to a generalized equation and more specific optimization-related stationarity and equilibrium problems. It has been well-understood that metric regularity of the mapping defining the generalized equation is a key to furnish Lipschitzian stability of the solution of interest. With this work, we want … Read more

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

  • AnthonyPalmieri
  • 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

    Nested Benders Decomposition for Large-Scale Multi-Follower Bilevel Optimization

  • Dominic C. Flocco
  • PhilineSchiewe
  • Steven A. Gabriel
    • Categories Bilevel Optimization, Parallel Algorithms, Transportation Tags , , , ,

    We propose a scalable nested Benders decomposition (BD) framework for single-leader, multi-follower bilevel optimization problems. The proposed framework is applicable to bilevel optimization problems in which each follower solves a linear program and is particularly well suited for instances involving a large number of followers. By identifying the upper-level decisions as complicating variables, the method … 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

    A path-following framework on fiber bundle for variational inequalities

  • Hongbo Sun
    • Categories Complementarity and Variational Inequalities Tags , , ,

    Variational inequality (VI) is a fundamental mathematical framework for many classical problems. We present a path-following framework for finite-dimensional VIs with arbitrary continuous functions and compact convex domains. The approach first approximately reduces a general VI to a smooth VI on simplex. Its key innovation is to formulate the smooth VI on simplex on a … Read more

    A Parameter-Free Restart Scheme with Only a Parallelizable $\log\log(1/\epsilon)$ Overhead

  • Yue Wu
  • Benjamin Grimmer
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    It is well-known that first-order methods can offer accelerated convergence rates in the presence of growth structures. Restarting schemes provide a general tool for such speed-ups. These schemes typically either require unrealistic problem knowledge, incur logarithmic overhead factors in oracle complexity, and/or have a nontrivial initial burn-in phase. We present a parameter-free approach for restarting … Read more

    Disjunctive Sum of Squares

  • Amir Ali Ahmadi
  • Sanjeeb Dash
  • Yixuan Hua
  • Bartolomeo Stellato
    • Categories Cone Programming, Convex Optimization, Semi-definite Programming Tags , , , , , , ,

    We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more