acceptodds
Under review as a conference paper at ICLR 2027

Learning to Control Feasibility–Objective Trade-off for Integer Linear Programs

Abstract

Solution predictors for integer linear programs (ILP) struggle to balance feasibility against objective quality, and no existing method learns to control this trade-off at inference. We introduce LibrAx, an unsupervised solution predictor that exposes this trade-off as a spectrum controllable at inference: a single forward pass yields the spectrum. Unlike soft-constrained losses, its semi-hard constrained loss keeps the penalty bounded while retaining an exactness guarantee. On the Very Hard tier of Distributional MIPLIB, LibrAx attains a lower primal gap than existing solution predictors on average, with 100% feasibility, producing solutions within 1.2 seconds. ILP solvers need – that time to match LibrAx's solution quality on average, widening to – on an unseen, harder tier.

Primary area:
optimization
Keywords:
machine learning for combinatorial optimization, integer linear programming, unsupervised learning, graph neural networks, primal heuristics

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_daRQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper introduces LibrAx, an unsupervised ILP solution predictor that aims to control the trade-off between objective quality and solution feasibility. The authors propose an Active-Constraint GNN motivated by the observation that optimal solutions to LP relaxations can lie at intersections of active constraints. They further introduce a semi-hard constrained loss to prioritize feasibility as constraint violations increase, along with a multi-head architecture that enables inference-time control over the feasibility–objective trade-off. Experiments are conducted on three ILP problem classes: Maximum Independent Set (MIS), Combinatorial Auctions (CA), and Set Covering (SC). LibrAx achieves 100% feasibility across the evaluated datasets while maintaining competitive primal gaps.

Critical strengths
  1. Strong empirical results. The proposed method demonstrates promising performance, achieving 100% feasibility across all evaluated datasets while maintaining competitive solution quality and inference efficiency.

  2. Clear presentation. The paper is well organized and clearly written. The motivation and methodological components are easy to follow.

  3. Meaningful research direction. Introducing inference-time control over the trade-off between feasibility and objective quality is an interesting and practically relevant direction for learning-based ILP solution prediction.

Critical weaknesses
  1. Limited justification for the Active-Constraint GNN. The motivation behind the Active-Constraint GNN is intuitive for LP problems, where optimal solutions can be found at intersections of active constraints. However, it is less clear how well this intuition extends to ILPs, where optimal integer solutions do not necessarily lie at such intersections. Furthermore, the ablation results in Table 3 show that removing the AC layer has only a marginal impact on final performance. Additional evidence would help establish the necessity and effectiveness of this architectural design.

  2. Limited evaluation on standard benchmark settings. Although the experiments cover three widely studied ILP problem classes, the evaluation focuses on the Very Hard and Very Hard2 distributions rather than the more commonly used benchmark configurations. Including results on these standard settings would facilitate more direct comparisons with existing methods and provide a more comprehensive assessment of the proposed approach.

Questions for authors
  1. Gradient stability of the semi-hard constrained loss. The authors carefully design the loss to ensure that the penalty value remains bounded. However, does this also guarantee bounded gradients, particularly as the penalty weight increases? If the gradients can still become arbitrarily large, the proposed loss may not fully resolve the training instability associated with large penalty weights. It would be helpful to clarify this distinction and provide further analysis of gradient behavior.

  2. Comparison with independently trained models. How does the proposed multi-head architecture compare with an ensemble of independently trained models, each using a different value of (\alpha_h)? Such a comparison would help clarify whether the performance gains arise from the learned trade-off spectrum and shared representations or simply from having access to multiple operating points.

  3. Fairness of the fixed-versus-sweep comparison. In Table 2, are the Fix and Swp settings evaluated using the same number of candidate solutions? If Swp evaluates more candidates, could the observed improvements primarily result from a best-of-(N) selection effect rather than the proposed inference-time controllability? A comparison under matched candidate budgets would help isolate the contribution of the trade-off spectrum.

4 comments

Thank you for the thoughtful and constructive review. Your feedback helped us more clearly articulate the motivation behind our architectural choices and sharpen the role of the learned trade-off spectrum. It also helped us present the supporting analyses more directly.

(W1) Clarifying the role of the Active-Constraint layer

We agree that an ILP optimum need not lie at an intersection of active constraints, as discussed in Section 2.1. While the submitted manuscript already motivated the AC layer through LP-guided primal heuristics that search around LP-relaxation solutions, our contribution statement could be read as making the stronger claim that high-quality ILP solutions themselves concentrate near intersections of tight constraints. We have therefore revised the corresponding contribution statement in the Introduction (Lines 69–71) to align it with the intended motivation:

"We design the Active-Constraint (AC) layer, motivated by the active-constraint structure that LP-guided primal heuristics exploit. Its message passing can approximate the operator that recovers such intersections, and the layer empirically accelerates training convergence."

To better justify the AC layer as an architectural inductive bias, we also moved the discussion of GNN architectures for ILP solution prediction from the appendix to the main text.

The marginal final-performance difference in Table 3 alone does not fully establish the effectiveness of the AC layer. The convergence analysis in Appendix E.13 directly complements this comparison: using a parameter-matched standard bipartite GNN over three training seeds, removing the AC layer slows convergence across MIS, CA, and SC. Thus, the role supported by our results is primarily to accelerate training convergence, rather than to produce uniformly large gains in final PG across every domain.

(W2) Benchmark choice and cross-benchmark evaluation

We agree that standardized evaluation would facilitate more direct comparisons across methods. However, there is currently no single commonly adopted benchmark configuration for ILP solution predictors. As noted by Distributional MIPLIB [1], prior learning-based MILP studies often generate their problem distributions independently; even DDIM [2] and DiffILO [3] use different configurations within the same MIS, CA, and SC problem classes:

DomainDDIM (constraints / variables)DiffILO (constraints / variables)
MIS6,396 / 1,5005,943 / 1,500
CA786 / 1,500576 / 1,500
SC1,000 / 2,0003,000 / 2,000

We therefore use the publicly available Distributional MIPLIB as a common evaluation basis. Within this benchmark, we focus on VH and VH2 because they represent settings where obtaining high-quality feasible solutions within a limited computational budget remains nontrivial, providing meaningful room to evaluate a learned solution predictor.

To further address cross-benchmark comparability, we added an evaluation on the MIS benchmark used by DiffILO (denoted IS in DiffILO) in Appendix E.5. Across three seeds, LibrAx achieves a mean objective of 669.4±0.3669.4 \pm 0.3 with 100% feasibility, without retuning its penalty-related hyperparameters. DiffILO does not report an aggregate mean or multi-seed variability for its standalone predictions on this benchmark, but Figure 4 of the original DiffILO paper shows two infeasible test instances. Thus, this additional cross-benchmark evaluation shows that LibrAx's performance remains robust on this additional benchmark configuration used by a prior method.

(Q1) Gradient stability under increasing penalty weight

We agree that a bounded penalty value alone does not imply bounded gradients. We therefore added a gradient analysis in Appendix B.2, focusing on whether increasing the penalty weight γ\gamma can make the penalty gradient arbitrarily large.

For an infeasible rounded point, letting v=Lviolv=L_{\mathrm{viol}}, we show

\le \frac{\alpha}{4v(v+1)} \le \frac{\alpha}{4\delta(1+\delta)},$$ where $\delta>0$ is the minimum positive violation for the given instance. The detailed derivation is provided in Appendix B.2. Importantly, this bound is independent of $\gamma$, so the penalty gradient with respect to the violation remains bounded as the penalty weight increases. At feasible rounded points, the ReLU-based violation term contributes zero prediction gradient under our implementation.

(Q2) Comparison with independently trained single-head models

To address this question, we compare LibrAx with Ens-α\alpha, which independently trains H=8H=8 single-head models with evenly spaced α∈[1,3]\alpha \in [1,3] and selects the best solution across them.

DatasetEns-α\alphaT-τ\tauSwp(8)
MIS-VH7.46.66.8
CA-VH31.320.320.9
  • Each entry reports PG↓.

All three methods in the above table use matched candidate counts. On both datasets, Ens-α\alpha achieves 100% feasibility but yields higher PG than the jointly trained LibrAx variants (T-τ\tau and Swp(8)). The detailed results, including the individual single-head models, are reported in Appendix E.10.

Thus, the gain cannot be explained solely by evaluating multiple operating points; the results suggest a benefit from joint learning and shared representations among heterogeneous heads within a single conditioned model. Joint training is also computationally more efficient, since Ens-α\alpha requires HH separate training runs and model evaluations at inference, whereas LibrAx learns the trade-off heads within one model.

(Q3) Fixed-versus-sweep under matched candidate budgets

The Fix and Swp settings in Table 2 do not use the same number of candidates. To isolate the effect of candidate count, we provide a matched-budget comparison in Appendix E.8.

We consider two fixed-point variants that generate the same number of candidates as Swp: Fix-T, which uses H′=25H'=25 evenly spaced rounding thresholds at Fix's operating point, and Fix-B, which samples the same number of candidates using the prediction as a sampling probability. The matched-budget results are summarized below:

MethodMIS-VHMIS-VH2CA-VHCA-VH2SC-VHSC-VH2
Fix-T100 / 6.8100 / 6.1100 / 21.4100 / 21.4100 / 51.6100 / 74.8
Fix-B0 / 100.00 / 100.00 / 100.00 / 100.0100 / 57.1100 / 64.5
Swp100 / 6.5100 / 5.9100 / 20.0100 / 20.3100 / 45.7100 / 57.1
  • Each entry reports FR↑ / PG↓.

Under matched candidate counts, Fix-T remains worse than Swp in PG across all six domain-tier combinations, while Fix-B fails to produce feasible solutions on MIS and CA and remains worse than Swp on SC. Thus, Swp's advantage cannot be explained solely by a best-of-NN selection effect; varying the operating point provides an additional benefit beyond generating more candidates at a fixed operating point.


References

[1] Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods, arXiv, 2024.

[2] Effective Generation of Feasible Solutions for Integer Programming via Guided Diffusion, SIGKDD, 2024.

[3] Differentiable Integer Linear Programming, ICLR, 2025.

Thank you very much for the detailed response and additional experiments. I appreciate the authors' efforts to address my concerns. However, I still have a few remaining questions:

Firstly, while the additional convergence results provide useful evidence for the effectiveness of the AC layer, I am still not fully convinced that its benefits arise specifically from the proposed active-constraint inductive bias. The parameter-matched comparison demonstrates faster convergence, but does not isolate the contribution of active-constraint reasoning from other architectural differences.

Secondly, the bound is derived with respect to the constraint violation, rather than the model parameters. Could the authors clarify whether this bound also implies that the parameter gradients remain stable as the penalty weight increases, and under what assumptions?

Thank you for the follow-up and for highlighting these two points. We appreciate the opportunity to further clarify what the AC-layer ablation isolates and how the gradient bound extends to model-parameter gradients.

(Follow-up Q1) Isolating the contribution of the AC layer

1. Controlled architectural comparison

We would first like to clarify what is changed in the W/o AC ablation relative to LibrAx. The W/o AC variant is identical to LibrAx, except that the AC layers (Eq. 4) are replaced by standard bipartite GNN layers; the latter's hidden size is adjusted solely to make its parameter count comparable to, and slightly larger than, that of LibrAx, as described in Appendix E.13. To avoid any ambiguity, we have also clarified in Section 4.6 that

"Except for the stated modification, each variant is identical to the default LibrAx."

Specifically, the surrounding MLPs, strictness-conditioning module, decoders, auxiliary objectives, and all remaining components and settings are kept unchanged. Both architectures follow the same variable–constraint–variable bipartite message-passing topology.

The active-constraint inductive bias is embodied in the AC layer as a whole (Eq. 4): its message-passing form is derived from the recovery operator of Lemma 1, and Proposition 1 shows that the layer admits an instantiation that realizes this operator.
We therefore ablate the AC layer as a unit and make our empirical claim at that level. The comparison isolates the architectural contribution of the AC layer while controlling the remaining architecture.

2. Scope of the empirical claim

Proposition 1 provides the representational motivation for the message-passing design, whereas the W/o AC ablation demonstrates the empirical convergence benefit of the AC layers. To make this distinction explicit, we revise the corresponding statement in Appendix E.13 from

"We attribute these gaps to the AC layer’s built-in recovery operator (Proposition 1), which spares the network from learning active-constraint structure from scratch."

to

"These convergence gaps demonstrate that the AC layers empirically accelerate training convergence, while Proposition 1 motivates the message-passing design by showing that the AC layer admits an instantiation that realizes the active-constraint recovery operator."

(Follow-up Q2) Extending the violation-gradient bound to parameter gradients

Our analysis in Appendix B.2 was intended to isolate whether increasing the penalty weight γ\gamma itself can cause gradient instability. For this reason, we analyzed the loss-side gradient with respect to the constraint violation. The resulting bound is independent of γ\gamma, showing that increasing γ\gamma does not itself cause this gradient factor to grow without bound. However, this bound alone does not imply that the gradients with respect to the model parameters θ\theta remain bounded as γ\gamma increases. We therefore further consider the corresponding parameter gradient.

For the penalty term P\mathcal{P}, the chain rule gives

\frac{\partial \mathcal{P}}{\partial v}\nabla_\theta v,$$ where $v=\mathcal{L}_{\mathrm{viol}}$. Therefore, if the gradient of the violation with respect to the model parameters remains bounded during training, then the penalty contribution to the parameter gradient is also bounded independently of $\gamma$. The same distinction applies to the full loss. Because $\omega$ is detached in the objective and integrality terms, increasing $\gamma$ does not introduce an additional gradient pathway through $\omega$, and these gradients are only scaled by $0<\omega\le1$. We have revised Appendix B.2 to make this distinction explicit. Specifically, we now state the **additional bounded-gradient assumption** and show that, if $\|\nabla_\theta v\|\le G$, then at infeasible rounded points, $$\|\nabla_\theta \mathcal{P}\| \le \frac{\alpha G}{4\delta(1+\delta)},$$ which is independent of $\gamma$. For the full loss, bounded parameter gradients additionally require the parameter gradients of the objective and integrality terms to remain bounded. Thus, our result does not claim unconditional boundedness of the model-parameter gradients; rather, it shows that, under these bounded-gradient assumptions, increasing $\gamma$ does not itself introduce an unbounded gradient factor.
Reviewer_BP3LOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces LibrAx, an unsupervised solution predictor for ILPs. Its components are:

  • Semi-hard constrained loss. A violation-aware gate ω = 1/(1 + γu^α) multiplies the (stop-gradient) objective and integrality terms, and the penalty term is 1 − ω. The penalty therefore stays bounded however large γ grows.
  • Multi-head strictness. H trade-off heads with different gate exponents α are conditioned on learned "strictness factors" τ.
  • Active-Constraint (AC) layer. Attention-weighted message passing motivated by recovering a variable from its active constraints.
  • Training aids. A compressed (√|c|) auxiliary objective and a feasibility-first curriculum with an adaptive γ scheduler.

At inference, τ is swept over 25 values for each of two decoders (50 candidates), and the best feasible candidate is returned. On the Very Hard (VH) tier of Distributional MIPLIB (MIS, CA, SC), LibrAx reaches 100% feasibility and a lower primal gap than DDIM and DiffILO on MIS and CA. It transfers to the harder VH2 tier and improves Gurobi's primal integral when used as a warm start.

Critical strengths
  1. A real problem with a simple fix. The penalty-weight dilemma of soft-constrained unsupervised losses is a genuine issue, and the bounded gated penalty addresses it neatly. The "w/ soft" ablation (PG 22.8% vs 20.0%, better on 95/100 instances, Wilcoxon) supports the design.
  2. Fast inference and robust feasibility. All six datasets reach 100% feasibility, and the model transfers to the VH2 tier without retraining.
  3. Honest cost accounting. The training cost comparison (Table 7) includes label collection, which is welcome.
  4. A thorough appendix. It covers gate-design alternatives, training dynamics as γ grows, loss–solution alignment, λ sensitivity, and a diagnosis of why DiffILO fails on MIS and CA.
Critical weaknesses
  1. Practical significance is overstated, and absolute solution quality is modest.

    • LibrAx's primal gaps are 20.0% (CA-VH), 45.7% (SC-VH), and 57.1% (SC-VH2).
    • Single-threaded Gurobi matches these solutions in 4.8 s on CA-VH and 16.5 s on SC-VH. SCIP needs 6.3 s on SC-VH.
    • The "185–453× the time" figures divide these times by TTPs of 0.06–1.2 s measured on an A100 GPU, while the solvers run on a single CPU thread. This hardware asymmetry should be stated where the ratios are quoted, and absolute TTM should be shown next to them.
    • Only MIS shows a large absolute advantage (648 s on VH, 2,486 s on VH2).
  2. On these benchmarks, feasibility is easy. MIS and CA are packing problems, where the zero vector is feasible, and SC is a covering problem, where the all-ones vector is feasible. A 100% feasibility rate, therefore, says little about the difficulty of feasibility, even though the paper presents feasibility as the central challenge. The one domain with non-trivial structure (MMCN, Appendix E.10) has primal gaps of 65.7–66.3%, and LP rounding is the only baseline there. Please add classes where feasibility is genuinely hard, for example with equality constraints or mixed binary/general-integer structure, or narrow the claims.

  3. Baselines are incomplete or possibly under-tuned.

    • (a) There is no simple problem-specific heuristic (greedy MIS, greedy set cover, greedy winner determination) and no LP rounding with a trivial repair. The nearest-integer LP-R baseline achieves 0% feasibility on SC, making it a straw man.
    • (b) Running Gurobi or SCIP for the same short time budget would be a more direct reference than TTM ratios.
    • (c) DiffILO's 0% feasibility on MIS and CA is blamed on its penalty cap. However, the cap was not re-tuned on validation for these larger distributions; it was only removed entirely. DiffILO was also trained for 150 instead of 1,200 epochs on MIS. A fair comparison would tune DiffILO's penalty schedule using the same validation protocol as LibrAx.
    • (d) Predict-and-Search-style methods are excluded because they do not produce standalone feasible solutions. Yet the solver-acceleration experiment (Section 4.5) is exactly where such methods are normally evaluated, so they should appear there. RL-SPH (Lee & Kim, 2026) also seems relevant.
  4. The theory does not describe the training dynamics.

    • Proposition 2 is about the minimizers of the value of L_β. Training, however, follows the stop-gradient field sg[ω]∇(L_obj + λL_int) − ∇ω. This is not the gradient of L_β, which would also contain the term (L_obj − β + λL_int)∇ω, so the stationary points of the two need not coincide. Remark 1's statement that training "follows exactly the gradient field of the analyzed loss" holds only for this pseudo-gradient.
    • Every term except L_int is evaluated at the rounded point, so Proposition 2 reduces to an exact-penalty argument over the finite set ℤⁿ ∩ B.
    • Lemma 1 and Proposition 1 (the AC layer realizes Eq. 3 when d = 1 and all maps are identities) are close to tautological. The recovery operator needs the active set I(x) at the unknown solution, which the attention weights do not enforce; Appendix C.2 concedes they never vanish.
    • Removing the AC layer barely changes the final primal gap (20.2% vs 20.0%). The AC layer is therefore at most a convergence-speed aid, and the third contribution bullet should be reworded.
  5. The novelty of "learning to control the trade-off" is not isolated. At inference, τ is not used as a user-facing control. It generates diverse candidates, from which the best feasible one is picked. The right comparison is against the same number of candidates produced by (i) separately trained heads at different γ/α, (ii) a single head sampled stochastically, or (iii) DDIM's guidance sweep. The rand-τ ablation is a start but covers none of these.

  6. Experimental rigor.

    • All main results come from a single training seed (Appendix D). Table 1 has no confidence intervals or tests.
    • Hyperparameters were selected on CA-VH validation, and the ablation (Table 3) is also run on CA-VH. Please repeat the ablation on another domain and over several seeds.
    • The aggregate improvement factors are geometric means that include baselines with PG = 100% (no feasible solution found), which inflates the ratios. Please give per-dataset factors and treat failing baselines separately.
    • The abstract (2.7×, VH tier only) and the introduction (3.2×, both tiers) aggregate the headline improvement in different ways. Please report one clearly defined aggregate.
  7. Minor issues.

    • Setting TTM to 0 for methods with no feasible solution, while unmatched runs are charged the full time limit, makes aggregate TTM hard to interpret.
    • Table 3 and Figure 2 are hard to parse.
Questions for authors
  1. How do greedy problem-specific heuristics and LP rounding with a simple repair compare in feasibility rate and primal gap?
  2. What primal gaps do Gurobi and SCIP reach when given the same short time budget as LibrAx (e.g., 1–2 s)?
  3. How does DiffILO perform with its penalty cap tuned on validation for the VH distributions?
  4. What is the seed-to-seed variability (over at least 3 seeds) for Table 1?
  5. How does performance depend on the number of inference strictness values H′? How do baselines compare when given the same candidate budget through sampling or separately trained models?
  6. Can you report results on at least one Distributional MIPLIB class where feasibility is not trivial?
  7. Regarding Remark 1: do you claim that the stationary points of the stop-gradient dynamics are minimizers of L_β? If not, please clarify how Proposition 2 relates to what training actually does.
4 comments

We thank the reviewer for the careful reading and constructive feedback. We have revised the manuscript accordingly and provide additional analyses and experiments below to address the concerns.

(W1) Interpreting solution quality and solver effort

While the hardware setup was reported in the submitted manuscript, we have made the hardware asymmetry more explicit in the main text where TTM and the corresponding ratios appear (Lines 334–336, Line 345, and Line 389). We have also removed the solver-to-LibrAx time ratios from the headline claims in the revised Introduction. The corresponding absolute TTM values are reported in Table 1.

Absolute PG alone does not fully capture how difficult it is for an exact solver to attain that solution quality. Differences in PG do not necessarily translate into corresponding differences in solver effort across domains and difficulty tiers. For example, on VH, LibrAx has a substantially lower PG on CA than on SC (20.0% vs. 45.7%), yet Gurobi reaches LibrAx's solution quality faster on CA than on SC (4.8 s vs. 16.5 s). On VH2, the PGs differ even more substantially (20.3% vs. 57.1%), while the corresponding Gurobi TTMs are nearly identical (33.9 s vs. 31.1 s). This is why we report TTM: it measures the wall-clock effort required for a standalone solver to reach an objective value at least as good as a given method's solution.

Accordingly, our use of the solver-to-LibrAx ratio is intended primarily to characterize how the relative time gap changes with instance difficulty. This is also why we refer to Gurobi and SCIP as learning-free references rather than baselines in Section 4.1 (Line 311). This comparison provides a reference for the amount of solver effort corresponding to the solution quality produced by a GPU-based predictor, rather than as a hardware-matched speedup claim over traditional solvers. From this perspective, the key observation is that the solver-to-LibrAx time gap becomes larger on the harder VH2 tier, increasing from 185×/453× on VH to 347×/603× on VH2 for Gurobi/SCIP under the stated hardware setup.

(W2, Q6) Feasibility–objective tension as central challenge

We do not claim that feasibility alone is difficult on these benchmarks. Rather, as stated in the Introduction (Lines 51–52):

“Since improving the objective pulls predictions toward the constraint boundary, the challenge lies in retaining feasibility while pursuing it.”

The same framing is reiterated in Section 5 (Lines 504–505), where maintaining feasibility while optimizing the objective is identified as the central challenge for ILP solution prediction. Accordingly, the existence of feasible solutions such as an all-zero or all-one vector does not remove the feasibility–objective tension we study.

As a complementary stress test, we also evaluate a setting where feasibility itself is nontrivial. MMCN provides such a setting and, as the reviewer suggests, contains a mixed binary/general-integer structure. On its Medium and Hard tiers, LibrAx attains 99% and 100% feasibility, respectively, whereas direct LP rounding finds no feasible solution on either tier. To strengthen this comparison, we additionally evaluate SCIP's rounding heuristic with infeasibility recovery (SCIP-R), which attains only 40% and 5% feasibility on the two tiers, respectively. Thus, even attaining feasibility alone is nontrivial on MMCN, while LibrAx maintains high feasibility in this setting.

(W3, Q1–Q3) Evaluation scope and complementary comparisons

To provide broader learning-free references, we include additional comparisons in Appendix E.2. We agree that problem-specific heuristics can be strong references. We do not include a different hand-crafted heuristic for each domain because our comparison targets generic ILP solution predictors; we avoid claiming superiority over domain-specific heuristics. To address the underlying concern that LP-R is a weak learning-free reference, we add SCIP-R, which applies SCIP's LP rounding heuristic with infeasibility recovery.

We also provide the requested direct comparison with Gurobi and SCIP under a 2-second time budget:

MethodMIS (VH / VH2)CA (VH / VH2)SC (VH / VH2)
Gurobi (2 s)19.2 / 20.826.1 / 25.696.3 / 97.7
SCIP (2 s)7.4 / 7.519.1 / 18.599.9 / 100.0
SCIP-R99.3 / 99.495.9 / 95.980.1 / 82.0
LibrAx6.5 / 5.920.0 / 20.345.7 / 57.1
  • Each entry reports PG ↓.
  • All methods attain 100% FR across the six settings.

LibrAx achieves lower PG than Gurobi on all six settings and lower PG than SCIP on MIS and SC, while SCIP performs better on CA. SCIP-R restores feasibility on SC, where LP-R fails, but still yields higher PG than LibrAx across all six settings. These short-budget results complement the TTM-based comparison.

For DiffILO, we followed the released implementation's default settings for the main comparison. Importantly, DiffILO's published update rule (Eq. 27) does not include a penalty cap, whereas its released implementation uses domain-specific upper bounds. Our initial uncapped experiment was therefore not an arbitrary alternative choice; it was intended to evaluate the update rule specified in the published formulation. We have made this choice explicit in Section 4.2 (Lines 353–354), where we clarify that the uncapped setting matches DiffILO's published update rule.

To address the reviewer's concern about whether the observed failure is specific to the default cap, we add a sensitivity sweep over intermediate cap values on MIS-VH, detailed in Appendix E.4:

Metric150 (default)5001,5005,000∞\infty (uncapped)LibrAx
FR ↑010095100100100
PG ↓100.09.551.999.899.86.5

The default cap yields no feasible solution, while removing the cap restores feasibility but degrades PG to 99.8%. An intermediate cap of 500 improves DiffILO to 100% feasibility and 9.5% PG, whereas larger caps again degrade objective quality. Thus, DiffILO's feasibility–objective trade-off is sensitive to the penalty configuration. DiffILO needs to cap the penalty weight to avoid penalty dominance; LibrAx's bounded penalty does not. LibrAx uses the same penalty configuration across domains and transfers to the larger, unseen VH2 tier.

To test whether the observed sensitivity could be attributed to asymmetric benchmark-specific tuning in favor of LibrAx, we add a cross-benchmark test. Appendix E.5 evaluates LibrAx on the MIS benchmark used by DiffILO. Without changing its penalty configuration, LibrAx maintains 100% FR and competitive objective quality across three seeds. In contrast, DiffILO's original penalty configuration loses feasibility when transferred to the Distributional MIPLIB setting and requires penalty retuning to recover better performance. This result suggests that the observed sensitivity is not explained solely by benchmark-specific tuning in favor of LibrAx.

Regarding DiffILO's 150-epoch training budget on MIS, its default 1,200 epochs would require over 400 hours on our setup. The 150-epoch run already requires approximately 54 hours, more than 15× LibrAx's training budget, and its training loss shows no improvement over the final 20% of training, as reported in Appendix E.1.

Finally, Predict-and-Search-style methods [1, 2, 5] and RL-SPH [7] address a related but different setting. Section 4.5 is intended to measure how a complete predicted solution can benefit a solver when used as an incumbent or trust-region center, rather than to compare ML-guided solving strategies. Consistent with this goal, Appendix E.9 applies the same trust-region protocol and search budget to all predictor outputs, isolating prediction quality from differences in ML-guided solving strategies. The results show that infeasible predictions can recover feasibility through solver refinement; nevertheless, higher-quality feasible predictions tend to provide stronger search centers under the same protocol. In particular, the RL-SPH paper also positions RL-SPH as addressing a role distinct from ILP solution predictors. Accordingly, we limit our claim to prediction quality under a common refinement protocol, rather than overall ML-guided solving performance, since Predict-and-Search-style methods and RL-SPH use method-specific solver-integration and search protocols.

(W4, Q7) Clarifying the scope and interpretation of our theoretical contributions

Regarding Q7, Proposition 2 concerns the global minimizers of the forward loss LβL_\beta, not the stationary points of the stop-gradient training dynamics. We have clarified this distinction in Section 3.2.1 (Lines 226-228) and Remark 1: the exactness guarantees characterize what the loss minimizes, rather than whether training reaches such a minimizer. Remark 2 further clarifies a point specific to Proposition 2: at fixed γ\gamma, the offset β\beta leaves the surrogate backward field unchanged because sg[ω]\mathrm{sg}[\omega] is detached, but this does not imply equivalence of forward minimizers. Moreover, we have added Corollary 1, which establishes the corresponding exactness result for the unshifted loss actually used in training (i.e., β=0\beta=0) under its stated condition.

For the AC layer, Lemma 1 and Proposition 1 are intended as a representational motivation rather than a guarantee that learned attention recovers the unknown active set.
Accordingly, we characterize the implemented AC layer as an inductive bias toward the active-constraint recovery operator, rather than claiming exact active-set identification during training. Finally, the AC layer should not be interpreted as providing a uniformly large improvement in final PG. Its primary empirical role is to accelerate training convergence, as shown in Appendix E.13. Consistent with this evidence, we reworded the third contribution statement:

"We design the Active-Constraint (AC) layer, motivated by the active-constraint structure that LP-guided primal heuristics exploit. Its message passing can approximate the operator that recovers such intersections, and the layer empirically accelerates training convergence."

(W5, Q5) Isolating learned trade-off control from candidate-budget effects

Although our benchmark protocol sweeps τ\tau over multiple values and selects the best feasible candidate, τ\tau itself remains directly user-selectable at inference.

To isolate this learned control from a best-of-NN effect, we added matched-candidate comparisons:

DatasetEns-α\alphaT-τ\tauSwp(8)
MIS-VH7.46.66.8
CA-VH31.320.320.9
  • Each entry reports PG↓.

Under the same candidate count, Ens-α\alpha—an ensemble of independently trained single-head models spanning different α\alpha values—achieves 100% feasibility but yields higher PG than the jointly trained LibrAx variants (T-τ\tau and Swp(8)). These results suggest a benefit from jointly learning heterogeneous trade-off heads within a single conditioned model.

Appendix E.8 further compares against fixed-operating-point variants under the same candidate budget:

MethodMIS-VHMIS-VH2CA-VHCA-VH2SC-VHSC-VH2
Fix-T100 / 6.8100 / 6.1100 / 21.4100 / 21.4100 / 51.6100 / 74.8
Fix-B0 / 100.00 / 100.00 / 100.00 / 100.0100 / 57.1100 / 64.5
Swp100 / 6.5100 / 5.9100 / 20.0100 / 20.3100 / 45.7100 / 57.1
  • Each entry reports FR↑ / PG↓.

The two fixed-operating-point variants (Fix-T and Fix-B) underperform Swp across all domains and tiers. In particular, Fix-B, which stochastically samples candidates from a single operating point, fails to attain feasibility on MIS and CA. These comparisons show that the benefit is not explained solely by candidate count or stochastic diversity.

Finally, Appendix E.11 examines sensitivity to the number of inference strictness values H′H':

DatasetH′=4H'=4H′=8H'=8H′=16H'=16H′=25H'=25H′=50H'=50
MIS-VH6.76.86.66.56.5
MIS-VH26.16.16.05.95.9
CA-VH20.620.920.220.019.8
CA-VH220.821.020.420.320.1
SC-VH53.748.246.345.744.9
SC-VH268.962.558.057.156.3
  • Each entry reports PG ↓; FR is 100% for all settings. The default is H′=25H'=25.

A denser sweep generally improves PG, but increasing it from the default 25 to 50 yields only modest additional gains, indicating diminishing returns from further increasing the candidate pool.

(W6, Q4) Experimental rigor

Regarding Q4, consistent with several recent learning-based ILP approaches [1–5], the results in Table 1 are not averaged over multiple training seeds. Nevertheless, to assess robustness, we provide multi-seed analyses for key methodological comparisons. In particular, Appendix E.12 evaluates the semi-hard and soft-constrained losses over three training seeds across all domains; Table 14 reports the seed-to-seed variability of LibrAx for all six settings in Table 1 as mean ± standard deviation over three training seeds. Across all three training seeds, LibrAx maintains 100% FR in all six settings, indicating stable feasibility across seeds with no seed-specific degradation in feasibility. Appendix E.13 further reports convergence behavior averaged over three seeds.

To address the concern that the original ablation was restricted to CA-VH, we also expanded the component ablation to MIS-VH:

DomainMetricLibrAxEns-α\alphaRand-τ\tauGrid-τ\tauW/ SoftW/o PSW/o INTW/o AUXW/o AC
CAFR ↑1001009910010095100100100
PG ↓20.031.328.321.822.837.4100.020.320.2
MISFR ↑10010090100100094100100
PG ↓6.57.416.66.56.9100.015.26.66.8

The expanded ablation shows broadly consistent component-level conclusions across the two domains; Table 3 reports the corresponding results and significance tests. Following the comment on Table 3 (W7), we also reorganized the table to improve readability. Specifically, we moved the definitions of the variants to the opening paragraph of Section 4.6 and capitalized the variant names.

For the aggregate PG ratios, we follow the primal-gap convention of Berthold [6], assigning PG = 100% when no feasible solution is available. We consider this treatment appropriate at the solution-quality level since an infeasible solution is invalid. However, without sufficient context on how PG handles infeasible predictions, we agree that the resulting multiplicative aggregate ratios could be misleading as headline claims. We therefore removed them from the abstract and introduction.

(W7) Interpreting aggregate TTM

We clarify how the two boundary cases should be interpreted when reading the reported aggregate TTM. When a method produces no feasible solution, there is no valid solution quality for the solver to match, and we assign TTM = 0. The occurrence rate of this case equals 100100%−-FR, where FR is reported alongside TTM in Table 1.

At the other boundary, when a method produces a feasible solution that the solver fails to match within the one-hour budget, we assign TTM = 3,600 s. Capping TTM at 3,600 s prevents unmatched instances from arbitrarily increasing the reported TTM.

To make the occurrence of this boundary case explicit, the table below reports the only nonzero time-limit rates. Here, rTLGr_{\mathrm{TL}}^{G} and rTLSr_{\mathrm{TL}}^{S} denote the percentages of test instances for which Gurobi and SCIP, respectively, fail to match a method's feasible solution within the one-hour time limit. All omitted method–dataset pairs have zero rates.

MethodDatasetrTLGr_{\mathrm{TL}}^{G} (%)rTLSr_{\mathrm{TL}}^{S} (%)
LibrAxMIS-VH03
LibrAxMIS-VH2021
LibrAxCA-VH203

Accordingly, the mean TTM is intended to summarize overall solver effort under this evaluation rule, with 100100%−-FR and rTLr_{\mathrm{TL}} providing the occurrence rates of its two boundary cases.


References

[1] A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming, ICLR, 2023.

[2] Contrastive Predict-and-Search for Mixed Integer Linear Programs, ICML, 2024.

[3] Effective Generation of Feasible Solutions for Integer Programming via Guided Diffusion, SIGKDD, 2024.

[4] Differentiable Integer Linear Programming, ICLR, 2025.

[5] Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming, ICLR, 2025.

[6] Measuring the impact of primal heuristics, Operations Research Letters, 2013.

[7] RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs, ICML, 2026.

Reviewer_fpkkOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents LibrAx, an unsupervised ILP solution predictor that learns an inference-time feasibility-objective trade-off. It combines an active-constraint-inspired GNN, strictness conditioning, a gated loss, and curriculum training. Experiments demonstrate strong performance on difficult binary optimization benchmarks, transfer to larger instances, and benefits for solver warm starts.

Critical strengths
  1. Useful inference-time control. The learned strictness spectrum allows instance-specific operating-point selection without retraining. Table 2 shows consistent improvements over a validation-selected fixed operating point, while the ablations support the importance of conditioning and multiple heads.
  2. Strong empirical performance. LibrAx achieves 100% feasibility on all six main test sets, with substantial gains on MIS and CA. Generalization, warm-start experiments, and component analyses provide complementary evidence of its practical value.
Critical weaknesses
  1. The theoretical guarantee has limited practical scope. Proposition 2 establishes exactness for an offset loss, while training uses an unshifted loss with stop-gradient and straight-through rounding. Although Remarks 1-2 acknowledge this distinction, identical backward updates do not imply identical forward minimizers; the headline claims should more clearly separate loss exactness from the behavior of the implemented optimization procedure.
  2. The contributions of the loss and strictness parameterization need clearer isolation. The soft-loss ablation supports the proposed gate on CA-VH, but its contribution on MIS, SC, and VH2 remains untested. Moreover, the single-head and randomized-conditioning ablations do not isolate the benefit of learning strictness values over fixing them to evenly spaced values while retaining heterogeneous loss heads.
Questions for authors
  1. What does Proposition 2 establish about the actual optimization procedure beyond the existence of an exact offset loss? In particular, how should its guarantee be interpreted under stop-gradient and straight-through rounding?
  2. Does the advantage over the soft-constrained variant persist on MIS, SC, and VH2 when the architecture, strictness conditioning, and curriculum are held fixed? This comparison would clarify the gate's contribution to the broader performance gains.
  3. Is learning the strictness values necessary compared with fixing them uniformly over [0, 1] during training? This is particularly relevant on CA, where full feasibility requires τ = 0.83, outside the learned range [0.16, 0.77].
  4. How do the speedup factors change when feasibility checking and candidate selection are included in inference latency?
2 comments

Thank you for the constructive review. Your feedback helped us sharpen the presentation of our core contribution. In particular, the additional ablation analyses more clearly separate the roles of the semi-hard loss and of learning strictness factors.

(W1, Q1) Exactness guarantee for the unshifted loss

We agree that the relationship between Proposition 2 and the loss used in our experiments should have been presented more clearly. Proposition 2 is a general exactness result for the offset loss. The offset β\beta is introduced as an analysis device for establishing this general result. Therefore, Proposition 2 by itself should not be interpreted as directly establishing exactness of the unshifted loss used in our experiments. To bridge this gap, we added Corollary 1 in the revised manuscript, which treats the unshifted loss used in our experiments (i.e., β=0\beta=0). Corollary 1 shows that, under the additional condition Lobj(x⋆)<1L_{\mathrm{obj}}(\mathrm{x}^\star)<1, exactness also holds for the unshifted loss. This condition is satisfied for the MIS, CA, and SC benchmarks within the scope of the analysis.

We have made this separation explicit in the revised manuscript (Line 226):

"The offset β\beta is an analysis device for establishing a general exactness guarantee; for the unshifted loss in Eq. (7), Corollary 1 establishes exactness under its stated condition."

Thus, Proposition 2 provides the more general offset-loss result, whereas Corollary 1 is the result directly relevant to the loss used in our experiments.

We also agree that the exactness guarantees should be distinguished from the behavior of the actual optimization procedure. As you pointed out, the fact that adding β\beta leaves the surrogate backward field unchanged at fixed γ\gamma does not imply identical forward minimizers. We now state this explicitly in Remark 2.

(W2, Q2) Extended evaluation of the soft-constrained variant

We extended the soft-constrained loss ablation to MIS, CA, and SC on both VH and VH2, with the results reported in Appendix E.12. The soft-constrained variant replaces only the semi-hard constrained loss, while all other components are kept fixed.

Consistent with the original CA-VH observation, the soft-constrained variant reaches a comparable or lower constraint-violation level toward the end of training, but settles at a worse objective loss across all three domains, as shown in Figure 8. This suggests that increasing the penalty weight in the soft-constrained loss can favor violation reduction at the expense of objective quality, consistent with the penalty-weight dilemma discussed in the paper.

The table below summarizes the PG results from Table 14:

MethodMIS-VHMIS-VH2CA-VHCA-VH2SC-VHSC-VH2
Soft6.9 ± 0.06.7 ± 0.921.7 ± 0.821.4 ± 0.753.1 ± 1.866.1 ± 4.3
LibrAx6.6 ± 0.05.9 ± 0.021.0 ± 0.921.0 ± 1.146.9 ± 6.262.6 ± 5.0
  • Each entry reports PG↓ as mean ± standard deviation over three training seeds.

LibrAx achieves a lower mean PG than the soft-constrained variant in all six domain-tier combinations. Thus, the same advantage observed in the original CA-VH ablation is also observed on MIS and SC and extends to the harder VH2 tier.

(W2, Q3) Learned vs. uniformly fixed strictness values

To isolate the effect of learning the strictness values, we added Grid-τ\tau in Table 3, which fixes the strictness factors to evenly spaced values over [0,1][0,1] during training while retaining the same heterogeneous loss heads and all other components.

The table below summarizes the LibrAx and Grid-τ\tau results from Table 3:

MethodCA-VHMIS-VH
Grid-τ\tau21.8*6.5
LibrAx20.06.5
  • Each entry reports PG↓.
  • ∗* indicates a statistically significant difference from LibrAx under a Wilcoxon signed-rank test (p<0.05p<0.05).

Grid-τ\tau yields a higher PG on CA (21.8 vs. 20.0) but does not differ significantly from LibrAx on MIS (6.5 vs. 6.5). Thus, learning the strictness values appears to provide a modest and domain-dependent benefit rather than being strictly necessary.

Regarding the CA case, full feasibility is reached at τ=0.83\tau=0.83, beyond the trained strictness range [0.16,0.77][0.16,0.77]. Nevertheless, the inference sweep continues to produce feasible solutions beyond the trained range. We interpret this as evidence that the model learns a meaningful conditioning relationship between τ\tau and the heterogeneous α\alpha-dependent violation responses, rather than merely fitting the strictness values observed during training.

(Q4) Inference latency including feasibility checking and candidate selection

In the paper, TTP is defined as the time up to producing the rounded candidate solutions and excludes the subsequent feasibility check and candidate selection. To quantify the effect of these two steps while retaining the original TTP definition, we separately measured their wall-clock costs and added them to the reported TTP. We denote the resulting quantity as Total Time: Ttotal=TTTP+Tfeas. check+Tselection.T_{\mathrm{total}}=T_{\mathrm{TTP}}+T_{\mathrm{feas.\ check}}+T_{\mathrm{selection}}.

DatasetTTPFeas. CheckSelectionTotal TimeTime Ratio (G)Time Ratio (S)
MIS-VH0.1200.0060.0030.1295015.2×6136.6×
CA-VH0.0570.0020.0010.06080.5×2533.8×
SC-VH1.1850.0240.0011.21013.6×5.2×
Geo. Mean (VH)––––176.6×432.7×
MIS-VH20.2520.0250.0080.2848747.0×9997.1×
CA-VH20.0990.0040.0010.104325.9×3049.1×
SC-VH22.5170.0480.0022.56712.1×5.9×
Geo. Mean (VH2)––––325.6×565.8×

Here, Time Ratio (G/S) denotes the Gurobi/SCIP TTM divided by LibrAx Total Time, respectively. Including feasibility checking and candidate selection changes the geometric-mean Gurobi/SCIP-to-LibrAx time ratios from 185×/453× to 176.6×/432.7× on VH, and from 347×/603× to 325.6×/565.8× on VH2. However, the main qualitative observation is unchanged: the solver-to-LibrAx time gap becomes larger on the harder VH2 tier.

Because the learned methods and exact solvers run on different hardware, we interpret the above quantities as wall-clock time ratios under our stated hardware setup. For this reason, we have excluded these ratios from the headline claims in the revised Introduction.

Comments on the paper

2 comments

We thank all reviewers for their thoughtful and constructive feedback. We have uploaded a revised manuscript incorporating changes in response to the reviews, along with detailed responses to each reviewer.

For ease of review, major revisions made in response to the reviewers' comments are highlighted in blue. For newly added tables, figures, and sections, only the corresponding captions or section titles are highlighted in blue.

We appreciate the reviewers' comments, which helped us improve both the clarity and the evaluation of our work.

We have marked in orange the manuscript revisions made in response to the follow-up questions, to make the corresponding changes easier to identify.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.