Just open-sourced a ~320-line Numba heuristic that consistently hits 0.3674–0.3677 on the standard G81 benchmark (20 000 nodes, 40 000 edges).
Key points:
- 99 % of the final cut is reached by iteration ~1200
- Built-in early stopping turns the remaining hours into minutes
- <80 MB RAM, no external solvers, no GPU
Quick comparison on the exact same graph (my runs, nothing fancy):
• Random 0.258
• Greedy (10 restarts) 0.324
• Simulated Annealing 0.349–0.356
• Basic Tabu Search 0.362–0.365
• Goemans-Williamson theoretical 0.878 → completely unusable at this scale
GravOpt at 1200 steps already beats almost every classical heuristic and is 50–200× faster.
Update: Just released an open-source Numba heuristic (~320 lines) hitting 0.3674–0.3677 on G81 benchmark (20k nodes, 40k edges):
- 99% convergence in ~1200 iterations
- Early stopping cuts hours to minutes
- <80MB RAM, no GPU, no external solvers
Quick comparison on same graph:
- Random: 0.258
- Greedy (10 restarts): 0.324
- Simulated Annealing: 0.349–0.356
- Tabu Search: 0.362–0.365
- Goemans-Williamson (theoretical): 0.878 → unusable at this scale
GravOpt with 1200 steps beats most classics and is 50–200x faster.
Key points: - 99 % of the final cut is reached by iteration ~1200 - Built-in early stopping turns the remaining hours into minutes - <80 MB RAM, no external solvers, no GPU
Quick comparison on the exact same graph (my runs, nothing fancy): • Random 0.258 • Greedy (10 restarts) 0.324 • Simulated Annealing 0.349–0.356 • Basic Tabu Search 0.362–0.365 • Goemans-Williamson theoretical 0.878 → completely unusable at this scale
GravOpt at 1200 steps already beats almost every classical heuristic and is 50–200× faster.
Code + the official G81 file (auto-downloaded if missing): https://github.com/Kretski/GravOpt-MAXCUT
Just run python gravopt.py and watch it go (downloads G81 automatically).
Did I just rediscover a 90s metaheuristic with better convergence + early stopping, or is this actually useful for 20k–200k QUBO instances in 2025?
Flame away, I can take it :)
https://github.com/Kretski/GravOpt-MAXCUT