MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems

• URL: http://arxiv.org/abs/2608.00959v1
• Date: Sun, 02 Aug 2026 03:10:50 GMT
• Title: MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems
• Abstract summary: Mixed complementarity problems arise as the first-order optimality conditions of nonlinear programs and noncooperative games.<n>The dominant solver for problems of this form is PATH, which offers strong performance on robotics problems but remains closed-source.<n>We present MixedarityProblems.jl, an open-source, pure Julia implementation of an interior point method for parametric MCPs.
• Score: 4.552097495048781
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mixed complementarity problems (MCPs) arise as the first-order optimality conditions of nonlinear programs and noncooperative games, and provide a natural formulation for multi-agent trajectory optimization problems that appear throughout robotics. The dominant solver for problems of this form is PATH, which offers strong performance on robotics problems but remains closed-source. We present MixedComplementarityProblems.jl, an open-source, pure Julia implementation of an interior point method for parametric MCPs that: (i) matches PATH's reliability on standard benchmarks, (ii) natively supports batched, parallel processing of many parameter instances, either across CPU threads or on an NVIDIA GPU, and (iii) supports efficient automatic differentiation of solutions with respect to problem parameters. On a multi-agent lane-change trajectory game representative of robotics planning problems, our CPU-multithreaded batched solver clears a batch of parametric instances ~100x faster than sequential calls to PATH. A GPU backend, running the same solver implementation unmodified, also clears these batches far faster than PATH, but does not outperform the multithreaded CPU on this problem; the GPU pulls ahead only once each per-instance KKT system grows large, and we characterize this regime dependence. We describe the solver's interior point formulation, the abstraction that lets a single solver implementation run unmodified across dense, batched-sparse, and single-large linear-algebra backends, and report benchmarks against PATH on both randomly generated quadratic programs and trajectory games.

Related papers

• CUDA MPC: A GPU-Native Solver for Model Predictive Control [0.0]
  Model Predictive Control (MPC) delivers constraint-aware control on systems with fast dynamics, high-dimensional models, or long horizons.<n>This paper introduces MPC, a GPU-native MPC framework that co-designs the optimization algorithm, execution model, and memory architecture for hardware.
  arXiv  Detail & Related papers  (2026-08-04T03:02:04Z)
• Scaling Nonlinear Optimization: Many Problems One GPU [45.58567999526917]
  We introduce textttjaxipm, the first GPU-batched NLP solver, based on IPOPT.<n>We demonstrate up to a $32.85times$ increase in throughput over IPOPT.
  arXiv  Detail & Related papers  (2026-06-24T19:34:41Z)
• Parallel Dynamic Programming for Conic Linear Quadratic Control [11.017626990661059]
  Linear Quadratic (LQ) control problems are at the heart of linear control theory and Model Predictive Control (MPC)<n>We present a parallel-in-time approach that solves computationally demanding conic optimal control problems through the use of the alternating direction method of multipliers (ADMM)<n> Numerical benchmarks on two real-world applications demonstrate as much as a 5x speedup compared to existing related approaches on multi-core CPU hardware.
  arXiv  Detail & Related papers  (2026-06-23T14:26:38Z)
• Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming [2.8852807790754618]
  We introduce a fully GPU-native trajectory optimization framework that combines sequential convex programming with a consensus-based alternating direction method of multipliers.<n>We validate the solver on a quadrotor agile flight task and a Mars powered descent problem using an on-board edge computing platform.<n> Benchmarks reveal a sustained 4x throughput speedup and a 51% reduction in energy consumption over a heavily optimized 12-core CPU baseline.
  arXiv  Detail & Related papers  (2026-03-11T12:39:14Z)
• It Takes Two to Tango: A Holistic Simulator for Joint Order Scheduling and Multi-Agent Path Finding in Robotic Warehouses [18.101514832695067]
  WareRover is a holistic simulation platform that enforces dynamic coupling between OS and MAPF.<n>Unlike standard benchmarks, WareRover integrates order streams, physics-aware motion constraints, and non-nominal recovery mechanisms into a single evaluation loop.
  arXiv  Detail & Related papers  (2026-02-15T05:51:58Z)
• Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
  Mixed-integer programming (MIP) extends linear programming by incorporating both continuous and integer decision variables.<n>This paper presents the first fully open-source implementation of deterministic parallel branch-and-bound for HiGHS, a high-performance MIP solver.<n>Our approach introduces a novel data-parallel architecture ensuring strict determinism by replicating complete solver state across worker threads.
  arXiv  Detail & Related papers  (2026-02-10T14:17:53Z)
• Optimization Techniques in Quantum Information [0.0]
  This thesis focuses on the intersection of mathematical and computational optimization and quantum information.<n>Main contributions are open-source software code.<n>The package PolyOptimization aims to fill the gap and provide a very resource-efficient intermediate layer together with a wide number of algorithms to reduce the problem size.
  arXiv  Detail & Related papers  (2025-12-17T17:51:10Z)
• INC: An Indirect Neural Corrector for Auto-Regressive Hybrid PDE Solvers [61.84396402100827]
  We propose the Indirect Neural Corrector ($mathrmINC$), which integrates learned corrections into the governing equations.<n>$mathrmINC$ reduces the error amplification on the order of $t-1 + L$, where $t$ is the timestep and $L$ the Lipschitz constant.<n>We test $mathrmINC$ in extensive benchmarks, covering numerous differentiable solvers, neural backbones, and test cases ranging from a 1D chaotic system to 3D turbulence.
  arXiv  Detail & Related papers  (2025-11-16T20:14:28Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local dual vectors. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. We propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs.
  arXiv  Detail & Related papers  (2023-08-17T21:15:04Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP) Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
  arXiv  Detail & Related papers  (2023-03-28T01:30:40Z)
• MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
  This work introduces a new MAP-solver, based on the popular Dual Block-Coordinate Ascent principle. Surprisingly, by making a small change to the low-performing solver, we derive the new solver MPLP++ that significantly outperforms all existing solvers by a large margin.
  arXiv  Detail & Related papers  (2020-04-16T16:20:53Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning. We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
  arXiv  Detail & Related papers  (2020-02-10T10:11:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.