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.
Figures & tables
Figure 1: Overview of ADIP. Starting from a feasible incumbent xinc obtained from a standard integer-programming solver, Phase 1 trains an autoregressive transformer to reproduce the incumbent using smoothed binary targets. Phase 2 optimizes the transformer parameters directly against the relaxed integer-program objective with a Lagrangian feasibility penalty, using Gumbel-softmax to maintain near-discrete outputs. Hard candidates are decoded throughout training, and the best feasible solution encountered is returned.
n
Base solver
Matched solver obj.
ADIP obj.
Improvement (%)
400
SCIP
2080.51(339.71)
2145.45(338.41)
5.71(4.57)
1000
SCIP
5081.30(562.45)
5710.90(620.19)
12.78(10.29)
10000
SCIP
0.00(0.00)
60.21(26.01)
∞
400
HiGHS
226.00(240.42)
893.00(796.20)
378.48(156.70)
1000
HiGHS
0.00(0.00)
300.00(323.85)
∞
400
CP-SAT
726.00(234.76)
1277.50(355.67)
77.31(8.35)
Table 1: Matched-budget results on random QKP instances. Means and standard deviations (between parentheses) are computed across 100 runs per experiment for size n=400 and 10 runs per experiment for sizes n∈{1000,10000} .
Figure 2: Representative objective-value trajectory: initial incumbent search and hard-decoded objective over ADIP training.
Figure 3: Visualization of the tunneling-like experiment. The solver incumbents, relaxed ADIP trajectory, and direct-relaxation endpoints are projected with t-SNE; the vertical axis shows objective value. Basin identity is determined in the original space.
n
Trajectory points
Distinct endpoints
Incumbent endpoint
Best endpoint
400
73
45
1931.3
1971.8
400
72
52
1842.5
2020.4
1000
90
35
4281.0
5083.0
1000
88
29
5248.0
5874.1
Table 2: Representative basin analysis of the relaxed landscape.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Percentage improvement of SCIP+ADIP vs. matched SCIP, plotted against the SCIP MIP gap after Tseed=500 s ( n=400 , 100 seeds).
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.