Parallel Algorithms

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

  • Dominic C. Flocco
  • Philine Schiewe
  • 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

    Log-Averaged Mirror Prox for Fast, Large-Scale Optimal Transport in Linear Space

  • Matthew X. Burns
  • Jiaming Liang
    • Categories Convex Optimization, Parallel Algorithms Tags , , , ,

    We propose Log-Averaged Mirror Prox (LAMP), a linear-space primal-dual method for large-scale optimal transport. LAMP implements primal mirror prox updates by tracking an averaged dual sequence, reducing storage complexity from \({O}(nm)\) to \({O}(n+m)\) while preserving dense, GPU-friendly reductions. Consequently, LAMP preserves the last-iterate \(\widetilde{{O}}( nm\varepsilon^{-1})\) arithmetic complexity of conservatively parameterized primal-dual mirror prox. We further … Read more

    The Decentralized Trust-Region Method with Second-Order Approximations

  • Hong Wang
    • Categories Parallel Algorithms Tags , ,

    This paper presents a novel decentralized trust-region framework that systematically incorporates second-order information to solve general nonlinear optimization problems in multi-agent networks. Our approach constructs local quadratic models that simultaneously capture objective curvature and enforce consensus through penalty terms, while supporting multiple Hessian approximation strategies including exact Hessians, limited-memory quasi-Newton methods, diagonal preconditioners, and matrix-free … Read more

    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

    Smoothie: Mixing the strongest MIP solvers to solve hard MIP instances on supercomputers – Phase I development

  • Yuji Shinano
  • Stefan Vigerske
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , , ,

    Mixed-Integer Linear Programming (MIP) is applicable to such a wide range of real-world decision problems that the competition for the best code to solve such problems has lead to tremendous progress over the last decades. While current solvers can solve some of the problems that seemed completely out-of-reach just 10 years ago, there are always … Read more

    A note on asynchronous Projective Splitting in Julia

  • Utkarsh Sharma
  • Kashish Goel
  • Aryan Dua
  • Sebastian Pokutta
  • Zev Woodstock
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization, Parallel Algorithms

    While it has been mathematically proven that Projective Splitting (PS) algorithms can converge in parallel and distributed computing settings, to-date, it appears there were no open-source implementations of the full algorithm with asynchronous computing capabilities. This note fills this gap by providing a Julia implementation of the asynchronous PS algorithm of Eckstein and Combettes for … Read more

    New results related to cutters and to an extrapolated block-iterative method for finding a common fixed point of a collection of them

  • Yair Censor
  • Daniel Reem
  • Maroun Zaknoon
    • Categories Convex Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    Given a Hilbert space and a finite family of operators defined on the space, the common fixed point problem (CFPP) is to find a point in the intersection of the fixed point sets of these operators.  Instances of the problem have numerous applications in science and engineering. We consider an extrapolated block-iterative method with dynamic … Read more

    Fully First-Order Methods for Decentralized Bilevel Optimization

  • Xiaoyu Wang
  • Xuxing Chen
  • Shiqian Ma
  • Tong Zhang
    • Categories Nonlinear Optimization, Parallel Algorithms, Stochastic Programming Tags , , ,

    This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis … Read more

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

  • Marco Langiu
  • Manuel Dahmen
  • Dominik 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

    Edge expansion of a graph: SDP-based computational strategies

  • Akshay Gupte
  • Melanie Siebenhofer
  • Angelika Wiegele
    • Categories Combinatorial Optimization, Parallel Algorithms, Semi-definite Programming Tags , , , ,

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relaxation first to reduce the search space considerably. The problem … Read more