Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces MixedComplementarityProblems.jl, an open-source interior point solver for mixed complementarity problems (MCPs) implemented in Julia, which matches the reliability of the dominant closed-source solver, PATH. The new solver excels in batched parallel processing, achieving approximately 100x speedup on multi-agent trajectory optimization problems compared to sequential calls to PATH, particularly under CPU multithreading. Additionally, while the GPU implementation shows promise for larger instances, it does not outperform the CPU version until the problem size increases significantly, highlighting the solver's adaptability across different computational environments.
Achieving a 100x speedup in solving multi-agent trajectory optimization problems, this open-source solver challenges the dominance of closed-source alternatives like PATH.
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.