Source-linked AI summary
Autoregressive Differentiable Method for Integer Programming
Ouns El Harzli, Yudong Cao
TL;DR
The paper asks whether autoregressive differentiable models can improve binary-integer-program incumbents, a relevant question because solvers may spend substantial time improving good feasible solutions. ADIP initializes a transformer from a feasible solver incumbent and optimizes its weights through a relaxed objective with a Lagrangian penalty. On random QKP instances, it improves solver incumbents under matched budgets, with results also indicating access to distinct attraction basins.
Problem
The paper asks whether autoregressive differentiable models can improve binary-IP incumbents, since solvers may spend substantial time improving good feasible solutions.
Source: §1 · p. 1Method
ADIP fits an autoregressive transformer to a feasible solver incumbent, then optimizes its weights against a relaxed objective with a Lagrangian feasibility penalty.
Source: §1 · pp. 1–2Results
On random QKP, ADIP improves solver incumbents under matched budgets, outperforming SCIP in 100% of the n = 10000 runs.
Source: §5.2 · p. 7, §7 · p. 9Takeaways & Limitations
The results suggest autoregressive neural reparameterization can provide a complementary search mechanism for hard discrete optimization.
Source: §7 · p. 9ADIP is trained separately for each instance, requires a feasible external-solver incumbent, and has been evaluated on random QKP instances.
Source: §6 · p. 9
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The introduction frames ADIP as an instance-specific neural mechanism for improving feasible binary-integer-program solutions, initialized from a solver incumbent rather than trained to solve instances from scratch. It presents a two-phase transformer procedure for optimizing a relaxed objective while retaining feasible hard solutions.
1 INTRODUCTION
- Solvers can spend substantial time improving a good feasible incumbent even though modern branch-and-cut solvers and primal heuristics are powerful.The introduction motivates a complementary primal-improvement mechanism rather than replacing conventional integer-programming machinery.Source: §1 · p. 1
- ADIP is initialized from a solver incumbent for each instance, separating feasibility discovery from neural improvement rather than learning across an instance dataset.The transformer exploits an incumbent already found by a solver instead of learning the combinatorial problem from scratch.Source: §1 · p. 1
- The experiments focus on quadratic knapsack problems with non-convex objectives, while the method applies when a binary objective has a differentiable continuous relaxation.The QKP testbed is strongly NP-hard even with small integer weights.Source: §1 · p. 2
- ADIP trains a fixed-order causal transformer to imitate a feasible incumbent with smoothed targets, then optimizes its weights against the relaxed objective with a Lagrangian penalty.Gumbel-softmax encourages near-discrete exploration, and the best feasible hard solution encountered is retained.Source: §1 · p. 2, Figure 1 · p. 2
- The paper evaluates ADIP on random QKP instances under matched budgets against open-source solvers and studies a tunneling-like phenomenon in its search trajectories.The stated contributions also include results on incumbent-improvement hardness, search-space retention, and state-dependent geometry in decision space.Source: §1 · p. 2
2 RELATED WORK
The related work situates ADIP among differentiable integer programming, autoregressive optimization, and quantum-inspired approaches. Its distinguishing feature is direct objective optimization through an autoregressive model initialized from a feasible solver incumbent.
2 RELATED WORK
- DiffILO uses independent Bernoulli parameters and a stochastic constraint surrogate, whereas ADIP differentiates an explicit continuous Gumbel-softmax autoregressive relaxation (Jang et al., 2017; Maddison et al., 2017).Sornwanee (2026) argues that DiffILO's sample-wise loss contains a discontinuous indicator, making its differentiation-expectation interchange generally invalid.Source: §2 · p. 3
- Unlike prior autoregressive methods for optimization, ADIP fits a feasible solver incumbent and backpropagates the original relaxed objective through the model's shared parameters.The passage contrasts this with sequential variable fixing before a conventional solver and autoregressive distributions for Ising-type optimization.Source: §2 · p. 3
- Unlike constrained tensor networks, ADIP does not architecturally encode feasibility; it starts from a feasible incumbent and uses a Lagrangian penalty.The Generative Quantum Eigensolver uses an autoregressive model to generate quantum circuits, while Quantum Hamiltonian Descent motivates ADIP's tunneling analogy.Source: §2 · p. 3
3 PRELIMINARIES
The preliminaries describe a fixed-order causal transformer that generates binary decisions autoregressively. Relaxed token embeddings and Gumbel-softmax provide a path for differentiable self-generation.
3 PRELIMINARIES
- Under a fixed variable ordering, the causal transformer Tθ factorizes; the passage does not specify what it factorizes.The feasible set is F = {x ∈ {0, 1}^n : Ax ≤ b}, with continuous relaxation ˜x ∈ [0, 1]^n.Source: §3 · p. 3
- A relaxed bit is embedded as a convex combination of the embeddings for tokens 0 and 1, allowing gradients through the generated prefix.The embedding is (1 − x̃_i)e_0 + x̃_i e_1.Source: §3 · p. 3
- The method uses straight-through Gumbel-softmax: the forward pass selects a hard bit, while the backward pass differentiates the continuous relaxation.The cited passage defines the Gumbel-softmax inputs as logits, independent Gumbel noises, and a positive temperature.Source: §3 · p. 3
4 METHODOLOGY
ADIP initializes a causal transformer from a solver’s feasible incumbent, then optimizes its weights against a penalized differentiable relaxation while retaining the best feasible decoded solution. The analysis establishes that incumbent improvement remains hard, the autoregressive parameterization preserves the binary search space, and transformer-space optimization induces distinct, state-dependent dynamics.
4.1 OVERVIEW
- ADIP imitates a solver’s feasible incumbent, then optimizes transformer weights on a penalized differentiable relaxation while retaining the best feasible hard-decoded candidate.The method uses Gumbel–softmax for the relaxed autoregressive sequence.Source: §4.1 · p. 4, §4 · p. 4, §4.5 · p. 5
4.2 COMPLEXITY OF INCUMBENT IMPROVEMENT
- Incumbent improvement for QKP remains NP-complete even when a feasible starting solution is given.The result assumes integer-valued objective coefficients and strictly positive integer weights.Source: §4.2 · p. 4
4.3 EXPRESSIVITY OF THE AUTOREGRESSIVE PARAMETRIZATION
- The autoregressive parameterization can approximate every binary solution, so it retains the combinatorial search space and its worst-case hardness.Threshold decoding at 1/2 is surjective onto binary vectors under the stated transformer expressivity assumption.Source: §4.3 · p. 4
4.4 PHASE 1: FEASIBLE INCUMBENT IMITATION
- Phase 1 trains the transformer to reproduce the feasible incumbent with finite-logit targets, preserving gradients for subsequent optimization.The hard decoding matches the incumbent when predicted probabilities fall on the correct side of 1/2.Source: §4.4 · p. 5
4.5 PHASE 2: DIFFERENTIABLE OPTIMIZATION IN TRANSFORMER WEIGHT SPACE
- For integer-valued constraints, a sufficiently large Lagrangian penalty makes every infeasible binary solution worse than the incumbent, but does not guarantee feasibility of relaxed points.The guarantee requires λ > UQ − finc; relaxed points can have arbitrarily small violations.Source: §4.5 · p. 5
4.6 AUTOREGRESSIVE RELAXED ROLLOUT
- Autoregressive rollout couples decision coordinates because changing an early relaxed token changes the prefix used to generate later tokens.Gradients therefore propagate through the complete generated sequence rather than treating relaxed variables as independent.Source: §4.6 · p. 5
4.7 NEAR-DISCRETE EXPLORATION WITH GUMBEL-SOFTMAX
- Gumbel–softmax encourages near-binary exploration, and lowering temperature narrows transitions while increasing gradient variance.As temperature approaches zero, the relaxed bit converges almost surely to a binary outcome; the diverging variance motivates keeping temperature above zero.Source: §4.7 · p. 6
4.8 WHY OPTIMIZE IN TRANSFORMER SPACE?
- Transformer-space optimization applies a state-dependent positive-semidefinite geometry to the relaxed objective gradient, allowing parameterizations of the same map to induce different dynamics.The induced geometry depends on the network Jacobian and can differ between functionally identical rescalings.Source: §4.8 · p. 6
5 EXPERIMENTS
The experiments test ADIP as a matched-budget primal-improvement method on random quadratic knapsack instances and examine whether its transformer trajectory reaches different relaxed-objective basins. ADIP beats SCIP in an increasing share of runs at larger tested sizes, while its relaxed-gradient endpoints differ from those of the initial incumbent.
5.1 QUADRATIC KNAPSACK BENCHMARK AND PROTOCOL
- The benchmark uses random nonsymmetric integer-valued quadratic knapsack objectives at n = 400, 1000, and 10000, with 100 instances at n = 400 and 10 at each larger size.Each solver gets 500 seconds to produce an incumbent; ADIP then trains for 500 seconds, compared with the solver alone running for 1000 seconds.Source: §5.1 · p. 7
5.2 MAIN RESULTS
- ADIP outperforms SCIP in 58% of runs at n = 400, 90% at n = 1000, and 100% at n = 10000 under matched budgets.The authors suggest ADIP is stronger when solvers leave greater room for improvement at large problem sizes.Source: §5.2 · p. 7
- Figure 2 shows a representative objective-value trajectory in which the best feasible decoded solution improves during transformer training from a SCIP incumbent, with staircase steps reflecting discrete-incumbent rather than relaxed-objective improvements.Source: §5.2 · pp. 7–8
5.3 BARRIER-CROSSING AND TUNNELING-LIKE BEHAVIOR
- The tunneling-like experiment compares direct relaxed-gradient endpoints from the solver incumbent and from relaxed transformer outputs, testing whether the transformer trajectory enters another region of the landscape.Direct descent is performed over the continuous feasible relaxation and stops at convergence or when the feasible boundary prevents further improvement.Source: §5.3 · p. 8
- ADIP visits relaxed points whose direct-gradient endpoints differ from the initial incumbent’s, indicating access to different attraction basins in the non-convex relaxed landscape.Basin identity is determined from endpoints in the original space; t-SNE is used only for visualization.Source: §5.3 · p. 8, Figure 3 · p. 9
6 LIMITATIONS
ADIP’s demonstrated scope is instance-specific random QKP, and its use depends on an external solver’s feasible incumbent.
6 LIMITATIONS
- ADIP is trained separately for each instance and requires a feasible incumbent from an external solver.The experiments focus on random QKP instances; broader integer-programming benchmarks and amortization across related instances remain future directions.Source: §6 · p. 9
- The Lagrangian penalty does not guarantee feasibility of every relaxed intermediate point, although the algorithm retains the best feasible hard solution encountered.Gumbel-softmax exploration remains close to the original combinatorial structure.Source: §6 · p. 9
- The tunneling analogy is geometric and empirical, not a global-optimization guarantee.Source: §6 · p. 9
7 CONCLUSION
The conclusion presents ADIP as a transformer-based nonlinear reparametrization for primal improvement in integer programming. On random QKP instances, it improves solver incumbents under matched budgets and accesses distinct relaxed-landscape basins.
7 CONCLUSION
- ADIP uses an autoregressive transformer as a nonlinear reparametrization of relaxed binary decision variables for primal improvement in integer programming.Source: §7 · p. 9
- On random QKP instances, ADIP improves state-of-the-art solver incumbents under matched computational budgets and accesses distinct attraction basins of the relaxed landscape.Source: §7 · p. 9
- The authors conclude that autoregressive neural reparametrization can provide a complementary search mechanism for hard discrete optimization.Source: §7 · p. 9
A.1 ADDITIONAL DETAILS ON RELATED WORKS
The related-work discussion distinguishes ADIP’s differentiable optimization through an autoregressive model from constrained tensor-network, generative quantum, and Hamiltonian-descent approaches. Its claimed distinction is optimization directly through transformer-generated relaxed decision variables, with a geometric tunneling analogy that remains empirical.
A.1 ADDITIONAL DETAILS ON RELATED WORKS
- The QKP benchmark follows Lopez Piqueres & Chen (2025), whose constrained MPS architecture restricts support exactly to feasible binary configurations.The passage says exact linear-constraint encoding via MPS can require exponentially many parameters; ADIP instead initializes from a SCIP incumbent and uses a Lagrangian feasibility penalty.Source: §A.1 · p. 13
- Unlike constrained MPS distribution updates, ADIP differentiates the relaxed QKP objective end-to-end through an autoregressive map and optimizes the transformer’s shared parameters.Source: §A.1 · p. 13
- ADIP shares GQE’s idea of lifting optimization into a classical generative model’s parameter space, but directly generates relaxed binary decision variables so the objective can be backpropagated.Source: §A.1 · p. 13
- ADIP’s tunneling analogy resembles QHD’s motivation of reaching trajectories inaccessible to classical local descent, but ADIP uses a classical transformer reparametrization rather than quantum Hamiltonian evolution.Source: §A.1 · p. 13
- Unlike QIHD’s explicit momentum-position Hamiltonian dynamics with constraint penalties, ADIP obtains non-Euclidean decision-space dynamics implicitly through an autoregressive neural reparametrization.Source: §A.1 · pp. 13–14
A.2 EXPERIMENTAL DETAILS
The experiments use matched wall-clock budgets to compare ADIP with solver-only baselines and include diagnostics of improvement and relaxed-landscape basins.
Compute environment
- Runs use CPU-only PyTorch on a single 14-core Apple M4 Max with 36 GB unified memory, and solver and BLAS/OpenMP threads are restricted to one.The transformer has two layers, dimension 64, four heads, and banded sparse attention; Phase 2 uses Gumbel-softmax at temperature 0.5.Source: §A.2 · p. 14
Warm-start models
- Dense indefinite quadratic instances are linearized for HiGHS, CBC, and CP-SAT with O(n^2) auxiliary binaries and constraints, while SCIP solves the native quadratic model.The linearized models become severe for LP-based MIP solvers already at n = 1,000.Source: §A.2 · p. 14
Matched-budget protocol
- Each solver receives 500 s to find an incumbent; ADIP then receives 500 s, while the matched baseline continues alone for 1,000 s total.ADIP also has a 2,000-step cap and may stop early on a plateau.Source: §A.2 · p. 14
Basin / tunneling diagnostic
- The basin diagnostic uses projected gradient ascent from ADIP trajectory points and SCIP incumbent snapshots, counting endpoints as distinct above an L2 distance of 10^-3.The t-SNE view projects the points, but basin identity is determined in the original [0, 1]^n space.Source: §A.2 · p. 15
Additional experimental figure
- Larger residual SCIP MIP gaps after 500 s tend to leave more room for ADIP improvement, but do not deterministically predict success.Figure 4 covers n = 400 across 100 seeds.Source: §A.2 · p. 15, Figure 4 · p. 15
A.3 PROOF OF THEOREM 1
These proofs establish hardness for finding a strict QKP incumbent improvement, characterize the binary solutions representable by hard-decoded transformers, and show how equivalent parameterizations can induce different optimization trajectories.
A.3 PROOF OF THEOREM 1
- A polynomial augmentation makes existence of a feasible solution strictly improving on the incumbent equivalent to a YES instance of decision QKP.The proof uses an added variable that consumes the full capacity, preventing a strict improvement when that variable is selected.Source: §A.3 · pp. 15–16
A.4 PROOF OF PROPOSITION 1
- The hard-decoded transformer parametrization covers every binary vector in {0, 1}^n.The proof invokes transformer universal approximation and thresholds each output coordinate at 1/2.Source: §A.4 · p. 16
A.5 PROOF OF COROLLARY 1
- Global optimization over transformer parameters is NP-hard because hard-decoded transformer optimization contains the original binary quadratic program exactly.Source: §A.5 · p. 16
A.6 PROOF OF PROPOSITION 2
- With a feasible incumbent, no infeasible binary point can globally maximize the penalized objective under Proposition 2's condition.Source: §A.6 · p. 17
A.7 PROOF OF PROPOSITION 3
- The variance of the estimator scales as Θ(τ^-1) in the stated zero-temperature analysis.The proof notes that its expectation converges to a finite value as τ tends to zero.Source: §A.7 · p. 17
A.8 PROOF OF THEOREM 4
- Functionally equivalent transformer parameterizations can induce different relaxed-space geometries and trajectories for a quadratic objective.The theorem establishes that the same autoregressive map can have different trajectory kernels under a query/key rescaling.Source: §A.8 · pp. 18–19