Cosm: Collective Switched Motion for Fast and Accurate Sparse Ising Optimization
This work provides a significantly faster and more accurate heuristic for sparse Ising optimization, which is relevant for researchers and practitioners working on combinatorial optimization problems.
This paper introduces Collective Switched Motion (Cosm), a heuristic algorithm for sparse Ising-type optimization problems. Cosm achieved optimal solutions on the three largest Gset instances (10,000-20,000 variables) and reduced state-of-the-art times-to-target from hundreds of hours to 36-303 seconds on two large bounded-degree Gset instances, representing 2-4 orders of magnitude improvement.
We introduce Collective Switched Motion (Cosm), a heuristic algorithm for solving sparse Ising-type optimization problems. Cosm combines locally interacting continuous circular variables with global coordination rules that facilitate collective dynamics. Pairwise interactions occur sequentially over a set of conflict-free edge partitions, resulting in an interaction network that switches periodically. Unlike conventional gradient-based approaches, Cosm enables structured, non-gradient dynamics that promote exploration beyond local minima. A correlated perturbation mechanism helps enable collective variable rotations. On the three largest Gset instances, which have 10,000-20,000 variables and represent 2D spin glasses, Cosm attains improved solutions that are verified as optimal using an exact solver. On two large bounded-degree Gset instances, a CPU-based implementation of Cosm reduces the state-of-the-art times-to-target from hundreds of hours to 36-303 s, reductions of 2-4 orders of magnitude. Additional tests on planted-solution benchmark instances show a lower scaling exponent than previous dynamical systems heuristics. These results highlight the effectiveness of Cosm in harnessing collective computation for improved sparse combinatorial optimization.