Parallel Graver Basis Extraction for Nonlinear Integer Optimization

Abstract

The augmentation scheme provides a nontraditional approach to nonlinear integer programming by iteratively refining incumbent solutions along objective-improving directions from the Graver basis. Its main computational bottleneck, however, lies in the practical difficulty of accessing such directions. To address this challenge, we develop a massively parallel heuristic for approximating Graver basis, extracting promising directions by optimizing nonconvex continuous problems using parallelizable first-order methods. Experiments on QPLIB and MINLPLib instances show that our method achieves comparable performance to advanced solvers.

Accepted by Operations Research Letters (https://doi.org/10.1016/j.orl.2026.107431)