Autoregressive Differentiable Method for Integer Programming
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.
Related
- Non-convex integer programming: a deterministic solution method of the large block sale problem
- A branch-and-filter method for mixed-integer linear programming
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Difference-of-Convex Regularization for Graph Learning by Differentiable Programming
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
BibTeX
@misc{harzli2026autoregressive,
title = {{Autoregressive Differentiable Method for Integer Programming}},
author = {Ouns El Harzli and Yudong Cao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02528},
eprint = {2610.02528},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02528},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Autoregressive Differentiable Method for Integer Programming
AU - Ouns El Harzli
AU - Yudong Cao
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02528
UR - https://arxiv.org/abs/2610.02528
AB - 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.
ER -