Improved Sparse Ising Optimization
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.