A Perturbation-Augmented Unsupervised Learning Framework for Integer Linear Programming

Integer linear programming (ILP) plays a pivotal role in combinatorial optimization, with applications ranging from logistics to scheduling. Recently, unsupervised learning has emerged as a promising paradigm for solving ILPs without costly labeled solutions. However, existing methods often converge prematurely to polarized probability distributions, losing solution diversity and trapping the process in local optima. To alleviate this, we propose PUMA, a Perturbation-augmented Unsupervised learning fraMework for integer linear progrAmming. PUMA introduces a stochastic neighborhood perturbation (SNP) operator that injects structured noise into the sampled solution space. The perturbation magnitude follows an exponential decay schedule, promoting exploration in early stages and refinement later. Theoretically, we show that PUMA optimizes a penalized objective with a dynamically decaying regularization term. Extensive experiments on benchmark ILP problems demonstrate that PUMA significantly mitigates the early collapse of solution diversity. It reduces the primal gap by 39.73% on average compared to state-of-the-art baselines. Furthermore, when used as a heuristic to warm-start traditional solvers, PUMA enables Gurobi to achieve an additional 91.17% reduction in the primal gap, and SCIP a 58.12% reduction.