GFORS: GPU-Accelerated First-Order Method with Randomized Sampling for Binary Integer Programs

  • Ningji Wei
  • Jiaming Liang
    • Categories 0-1 Programming, Constrained Nonlinear Optimization, Parallel Algorithms Tags , ,

    We present GFORS, a GPU-accelerated framework for large binary integer programs. It couples a first-order (PDHG-style) routine that guides the search in the continuous relaxation with a randomized, feasibility-aware sampling module that generates batched binary candidates. Both components are designed to run end-to-end on GPUs with minimal CPU–GPU synchronization. The framework establishes near-stationary-point guarantees for … Read more

    Inexact subgradient algorithm with a non-asymptotic convergence guarantee for copositive programming problems

  • Mitsuhiro Nishijima
  • Pierre-Louis Poirion
  • Akiko Takeda
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this paper, we propose a subgradient algorithm with a non-asymptotic convergence guarantee to solve copositive programming problems. The subproblem to be solved at each iteration is a standard quadratic programming problem, which is NP-hard in general. However, the proposed algorithm allows this subproblem to be solved inexactly. For a prescribed accuracy $\epsilon > 0$ … Read more

    Locating Temporary Hospitals and Transporting the Injured Equitably in Disasters

  • Shiva Moslemi
  • Secil Savasaneril
  • Mustafa Tural
    • Categories Applications - OR and Management Sciences, Transportation Tags , , , , , , , ,

    In the aftermath of an earthquake, one of the most critical needs is medical care for the injured. A large number of individuals require immediate attention, often overwhelming the available healthcare resources. The sudden surge in demand, coupled with limited resources, route congestion and infrastructure damage, makes immediate medical care provision a significant challenge. This … Read more

    A Practical Adaptive Subgame Perfect Gradient Method

  • Alan Luner
  • Benjamin Grimmer
    • Categories Convex Optimization, Second-Order Cone Programming Tags , , , , , ,

    We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on … Read more

    Faster Solutions to the Interdiction Defense Problem using Suboptimal Solutions

  • Joshua Ong
    • Categories (Mixed) Integer Linear Programming, Energy Tags ,

    The interdiction defense (ID) problem solves a defender-attacker-defender model where the defender and attacker share the same set of components to harden and target. We build upon the best response intersection (BRI) algorithm by developing the BRI with suboptimal solutions (BRI-SS) algorithm to solve the ID problem. The BRI-SS algorithm utilizes off-the-shelf optimization solvers that … Read more

    A guided tour through the zoo of paired optimization problems

  • Oliver Stein
    • Categories Bilevel Optimization, Game Theory, Nonlinear Optimization Tags , , , , , , , , ,

    Many mathematical models base on the coupling of two or more optimization problems. This paper surveys possibilities to couple two optimization problems and discusses how solutions of the different models are interrelated with each other. The considered pairs stem from the fields of standard and generalized Nash equilibrium problems, optimistic and pessimistic bilevel problems, saddle … Read more

    Data-Driven Optimization for Meal Delivery: A Reinforcement Learning Approach for Order-Courier Assignment and Routing at Meituan

  • Ramon Auad
  • Felipe Lagos
  • Tomas Lagos
    • Categories Dynamic Programming, Meta Heuristics, Transportation Tags

    The rapid growth of online meal delivery has introduced complex logistical challenges, where platforms must dynamically assign orders to couriers while accounting for demand uncertainty, courier autonomy, and service efficiency. Traditional dispatching methods, often focused on short-term cost minimization, fail to capture the long-term implications of assignment decisions on system-wide performance. This paper presents a … Read more

    blockSQP 2: exploiting structure to improve performance

  • Reinhold Wittmann
  • Sebastian Sager
    • Categories Dynamic Programming, Nonlinear Optimization Tags , , , ,

    Abstract One approach to solving optimal control problems is Bock’s direct multiple shoot- ing method. This method yields lifted nonlinear optimization problems (NLPs) with a spe- cific block structure. Exploiting this structure via tailored optimization algorithms can be computationally beneficial. We propose such methods, primarily within the framework of fil- ter line search sequential quadratic … Read more

    Extreme Strong Branching for QCQPs

  • Santanu S. Dey
  • Dahye Han
  • Yang Wang
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Global Optimization

    For mixed-integer programs (MIPs), strong branching is a highly effective variable selection method to reduce the number of nodes in the branch-and-bound algorithm. Extending it to nonlinear problems is conceptually simple but practically limited. Branching on a binary variable fixes the variable to 0 or 1, whereas branching on a continuous variable requires an additional … Read more

    Optimizing pricing strategies through learning the market structure

  • Khosroparviz Naderivarandi
  • Ezgi Karabulut
  • Burak Gokgur
    • Categories Optimization in Data Science, Yield Management Tags , , ,

    This study explores the integration of market structure learning into pricing strategies to maximize revenue in e-commerce and retail environments. We consider the problem of determining the revenue maximizing price of a single product in a market of heterogeneous consumers segmented by their product valuations; and analyze the pricing strategies for varying levels of prior … Read more