TY - GEN
T1 - A Perturbation-Augmented Unsupervised Learning Framework for Integer Linear Programming
AU - Deng, Yufan
AU - Pu, Tianle
AU - Hu, Zhijing
AU - Geng, Zijie
AU - Zeng, Li
AU - Hu, Xingchen
AU - Huang, Kuihua
AU - Wu, Junjie
AU - Fan, Changjun
N1 - Publisher Copyright:
© 2026 Owner/Author.
PY - 2026/8/8
Y1 - 2026/8/8
N2 - 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.
AB - 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.
KW - integer linear programming
KW - learning to optimize
KW - machine learning for combinatorial optimization
UR - https://www.scopus.com/pages/publications/105051077782
U2 - 10.1145/3770855.3817737
DO - 10.1145/3770855.3817737
M3 - 会议稿件
AN - SCOPUS:105051077782
T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
SP - 851
EP - 862
BT - KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2
PB - Association for Computing Machinery
T2 - 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1, KDD 2026
Y2 - 9 August 2026 through 13 August 2026
ER -