arXiv：cs.LG· Ouns El Harzli, Yudong Cao·· 3 小时前AI 评分38
自回归可微方法求解整数规划
Autoregressive Differentiable Method for Integer Programming
AI 导读
研究者提出一种自回归可微方法求解 0-1 整数规划：固定二进制变量顺序，训练 Transformer 在可行域内逐位预测，并用 Lagrangian 惩罚与 Gumbel-softmax 激活进一步探索可行集。在二次背包问题的非凸实例上，该方法对多达 10,000 个二进制变量的稠密问题持续优于当前最优开源求解器，并实证了类似隧穿效应的现象。
正文
Abstract:We introduce an autoregressive differentiable method to solve 0-1 integer programs. We fix an arbitrary order of the binary variables and we train a transformer to predict the next bit while remaining in the feasible set. Our method is first trained on feasible incumbents provided by any solver, thus allowing us to initialize the transformer in the feasible set. Our procedure then implements a Lagrangian penalty to penalize infeasible solutions, and the transformer is further trained to explore the feasible set using Gumbel-softmax activations on the relaxed objective. We have tested our method on non-convex instances of quadratic knapsack problem and demonstrated consistent improvement upon state-of-the-art open-source solvers for dense problems up to 10,000 binary variables. In particular, we empirically demonstrate a phenomenon akin to a tunneling effect where the effective change of variables from binary variable to the continuous weights of the transformer that the method implements enables crossing barriers in the relaxed objective landscape.
| Subjects: | Machine Learning (cs.LG); Optimization and Control (math.OC) |
| Cite as: | arXiv:2610.02528 [cs.LG] |
| (or arXiv:2610.02528v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.02528 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Ouns El Harzli [view email]
[v1]
Thu, 1 Oct 2026 21:58:10 UTC (4,950 KB)
来源：arXiv：cs.LG · arxiv.org