analiza aiqbench
This research proposes a novel autoregressive transformer approach to solve 0-1 integer programming problems, leveraging Gumbel-softmax activations and Lagrangian penalties to navigate feasible solution spaces. By effectively treating binary variables as continuous weights during training, the method demonstrates a "tunneling effect" that allows it to cross barriers in the objective landscape, outperforming standard solvers on dense quadratic knapsack instances with up to 10,000 variables.
Autoregressive Differentiable Method for Integer Programming
arXiv:2610.02528v1 Announce Type: new 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.
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.
Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2610.02528 [cs.LG]
(or arXiv:2610.02528v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.02528 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 254 cuvinte
Subiecte conexe
Links #3: 2026/06 Part 1
LessWrong · 15 iun. 2026
Hard Constraints, Smooth Gradients: Learning Feasible Inventory Policies via Differentiable Projection
arXiv · 5 aug. 2026
Efficiently Optimizing the Quantum Value of Bell Inequalities using Batched Gradient Descent
arXiv · 2 oct. 2026
Free-Placement Optimization of Ground Station Locations for Low-Earth Orbit Satellites
arXiv · 12 iun. 2026