Kenneth M. Zick

Kenneth M. Zick

Sparse Ising problems can be found in application areas such as logistics, condensed matter physics and training of deep Boltzmann networks, but can be very difficult to tackle with high efficiency and accuracy. This report presents new data demonstrating significantly higher performance on some longstanding benchmark problems with up to 20,000 variables. The data come from a new heuristic algorithm tested on the large sparse instances from the Gset benchmark suite. Relative to leading reported combinations of speed and accuracy (e.g., from Toshiba's Simulated Bifurcation Machine and Breakout Local Search), a proof-of-concept implementation reached targets 2-4 orders of magnitude faster. For two instances (G72 and G77) the new algorithm discovered a better solution than all previously reported values. Solution bitstrings confirming these two best solutions are provided. The data suggest exciting possibilities for pushing the sparse Ising performance frontier to potentially strengthen algorithm portfolios, AI toolkits and decision-making systems.

Kenneth M. Zick, Nikhil Shukla, Alexander Marakov

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.