- 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
-
Strong empirical results. The proposed method demonstrates promising performance, achieving 100% feasibility across all evaluated datasets while maintaining competitive solution quality and inference efficiency.
-
Clear presentation. The paper is well organized and clearly written. The motivation and methodological components are easy to follow.
-
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
-
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.
-
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
-
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.
-
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.
-
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
(Q2) Comparison with independently trained single-head models
To address this question, we compare LibrAx with Ens-, which independently trains single-head models with evenly spaced and selects the best solution across them.
| Dataset | Ens- | T- | Swp(8) |
|---|---|---|---|
| MIS-VH | 7.4 | 6.6 | 6.8 |
| CA-VH | 31.3 | 20.3 | 20.9 |
- Each entry reports PG↓.
All three methods in the above table use matched candidate counts. On both datasets, Ens- achieves 100% feasibility but yields higher PG than the jointly trained LibrAx variants (T- 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- requires 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 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:
| Method | MIS-VH | MIS-VH2 | CA-VH | CA-VH2 | SC-VH | SC-VH2 |
|---|---|---|---|---|---|---|
| Fix-T | 100 / 6.8 | 100 / 6.1 | 100 / 21.4 | 100 / 21.4 | 100 / 51.6 | 100 / 74.8 |
| Fix-B | 0 / 100.0 | 0 / 100.0 | 0 / 100.0 | 0 / 100.0 | 100 / 57.1 | 100 / 64.5 |
| Swp | 100 / 6.5 | 100 / 5.9 | 100 / 20.0 | 100 / 20.3 | 100 / 45.7 | 100 / 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- 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 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 , showing that increasing 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 remain bounded as increases. We therefore further consider the corresponding parameter gradient.
For the penalty term , 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.
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:
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:
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.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 γ can make the penalty gradient arbitrarily large.
For an infeasible rounded point, letting v=Lviol, 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.