Month: April 2026

Robust Bilevel Optimization with a Wait-and-See Follower: A Column-and-Constraint Generation Approach

  • Henri Lefebvre
  • Johannes Thürauf
    • Categories Bilevel Optimization, Robust Optimization Tags , , , ,

    We study optimistic robust bilevel problems with uncertainty in the follower’s problem, where the follower adopts a so-called wait-and-see approach. In this setting, the leader decides without knowledge of the specific realization of the uncertainty. Then, the uncertainty realizes in a worst-case manner, and afterward the follower makes her own decisions. For this challenging problem … Read more

    Probabilistic analysis of dual decomposition on two-stage stochastic integer programs

  • Jingye Xu
    • Categories Integer Programming, Stochastic Programming Tags ,

    Two-stage stochastic integer programs provide a powerful framework for modeling decision-making under uncertainty, but they are notoriously difficult to solve at scale due to their high dimensionality and intrinsic nonconvexity. Decomposition-based algorithms such as Benders methods and Branch-and-Price (related dual decomposition methods) have become standard computational approaches for such problems and demonstrate excellent empirical performance … Read more

    Stochastic Three Points Method with an Inexact Oracle and Its Application to Steady-State Optimization

  • Geovani Nunes Grapiglia
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    We consider unconstrained derivative-free optimization problems in which only inexact function evaluations are available. Specifically, we study the setting where the oracle returns function values with partially controllable inexactness, with the error bounded linearly by a user-specified accuracy parameter, but with an unknown proportionality constant. This framework captures optimization problems arising from approximate simulations or … Read more

    A unified framework for inexact adaptive stepsizes in the gradient methods, the conjugate gradient methods and the quasi-Newton methods for strictly convex quadratic optimization

  • Zexian Liu
    • Categories Convex Optimization, Quadratic Programming, Unconstrained Optimization Tags , , , ,

    The inexact adaptive stepsizes for the conjugate gradient method and  the quasi-Newton method are very rare. The exact stepsizes in the gradient method, the conjugate gradient method and the  quasi-Newton method for strictly convex quadratic optimization have a unified framework, while the unified framework for inexact adaptive stepsizes  in the gradient method, the conjugate gradient … Read more

    Reverse stress testing for supply chains

  • Busra Gultekin
  • Frans J.C.T. de Ruiter
  • Meike Reusken
  • Sander de Leeuw
    • Categories Applications - OR and Management Sciences, Integer Programming, Supply Chain Management Tags , , ,

    This study introduces reverse stress testing for supply chains, designed to identify the minimal deviations from normal operations that would drive supply chains to a predefined performance failure. First, we present a framework for reverse stress testing with the purpose of assessing supply chain vulnerabilities. The framework involves six steps: selecting risk variables, defining baselines, … Read more

    Accuracy Certificates for Convex Optimization at Accelerated Rates via Primal-Dual Averaging

  • Matthew X. Burns
  • Jiaming Liang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    Many works in convex optimization provide rates for achieving a small primal gap. However, this quantity is typically unavailable in practice. In this work, we show that solving a regularized surrogate with algorithms based on simple primal-dual averaging provides non-asymptotic convergence guarantees for a computable optimality certificate. We first analyze primal and dual methods based … Read more

    Enhancing the separation of rank-1 Chvátal-Gomory cuts from knapsack sets

  • Giacomo Maggiorano
  • Stefano Gualandi
  • Pasquale Avella
    • Categories 0-1 Programming, Branch and Cut Algorithms, Integer Programming Tags , , ,

    We present an exact method for separating Chvátal-Gomory cuts from binary knapsack sets, consisting of two steps: i) enumerating a finite set of possible optimal multipliers for the knapsack constraint; ii) for each candidate, adjusting optimally the remaining multipliers. We prove that ii) can be formulated as a binary knapsack problem, leading to a pseudopolynomial-time … 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

    Paving and computing the set of nondominated points for the bi-objective 0/1 uncapacitated facility location problem

  • Xavier Gandibleux
  • Anthony Przybylski
    • Categories Combinatorial Optimization, Multi-Criteria Optimization Tags , , , , ,

    The paper presents a three-phase algorithm to compute the set of nondominated points for the binary version of the uncapacitated facility location problem with two objectives. The first phase constructs a paving in objective space which is a collection of boxes that covers all nondominated points. The paving procedure is a branch and bound algorithm … Read more

    Pricing Discrete and Nonlinear Markets With Semidefinite Relaxations

  • Cheng Guo
  • Lauren Henderson
  • Ryan Cory-Wright
  • Boshi Yang
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Semi-definite Programming Tags , , , ,

    Nonconvexities in markets with discrete decisions and nonlinear constraints make efficient pricing challenging, often necessitating subsidies. A prime example is the unit commitment (UC) problem in electricity markets, where costly subsidies are commonly required. We propose a new pricing scheme for nonconvex markets with both discreteness and nonlinearity, by convexifying nonconvex structures through a semidefinite … Read more