- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes State-Conditioned Refinement (SCoR) for unsupervised integer linear programming (ILP). SCoR incorporates localized constraint feedback into the refinement process by propagating constraint residual information to incident variables and adaptively scaling variable-wise updates. Experiments on standard binary ILP benchmarks demonstrate improvements over existing unsupervised solvers.
Critical strengths
-
The paper is well written and easy to follow. The experimental results are promising.
-
SCoR serves as an additional refinement module that can be integrated into different unsupervised ILP optimization frameworks.
Critical weaknesses
-
The proposed method appears to be primarily based on residual-aware attention over a bipartite graph and learned diagonal preconditioning. The methodological novelty beyond combining these existing techniques is not sufficiently clear.
-
The theoretical analysis is not closely connected to the actual model design. In particular, Proposition 4.2 characterizes the potential advantage of variable-wise update allocation, but the proposed model does not explicitly optimize for such an allocation. Therefore, the theoretical results provide limited justification for the effectiveness of the learned refinement mechanism.
Questions for authors
-
The computational overhead of SCoR is not sufficiently discussed. Could the authors provide more details on the training and inference times, particularly in comparison with the base methods?
-
Could the authors compare SCoR against simpler preconditioning strategies, such as gradient-based diagonal scaling or residual-based scaling, to better demonstrate the necessity of the proposed architecture?
2 comments
I thank the author for the detailed response to my concerns. It has addressed some of my concerns. However, I think that my concerns for the theoretical justification still exist. The improvement from DiffILO is also limited. At this stage I prefer to maintain my score.
We thank the reviewer for the feedback on the design, theory, and computational cost. We added simpler scaling baselines with comparable parameter counts for the learned alternatives and measured the additional training and prediction time.
Response to Weakness 1 and Question 2. Methodological contribution and simpler alternatives
SCoR learns how to allocate a base update across variables using the current states of their incident constraints. Figure 1 illustrates why this matters on CA. Aggregate violation decreases by 3.4%, yet 19.7% of the evaluated constraint residuals worsen. The learned scaling head uses local constraint feedback to respond to these different constraint states when deciding how much of the base update each variable receives. This relationship is learned jointly with the predictor through the existing unsupervised objective in both DiffILO and PUMA.
We compared SCoR-DiffILO with fixed gradient-magnitude scaling, a learned gradient-logit controller, and mean residual aggregation. The gradient-logit controller uses the current logit, marginal probability, and normalized gradient. Mean aggregation retains the residual-conditioned values and activity gate and gives incident constraints equal weights. We widened the first hidden layer in both learned alternatives to bring their parameter counts within 0.53% of the full refinement module and 0.06% of the full model (Appendix C.9, Table 14).
SCoR achieves the best mean objective on SC and CA under the shared search protocol. On SC, fixed gradient scaling and mean aggregation also improve upon DiffILO. On CA, the full model improves on DiffILO while each simpler alternative yields a lower objective. The mean-aggregation comparison supports learning the relative weights of incident constraints with comparable model capacity.
Response to Weakness 2. Connection between Proposition 4.2 and the learned mechanism
Proposition 4.2 asks what can be gained by redistributing a fixed amount of update magnitude. It shows that moving part of the update from a weaker-gradient coordinate to a stronger-gradient coordinate with remaining capacity can yield a strictly larger decrease in the local linear model. This provides a rationale for variable-wise scaling. The performance of a particular learned controller is an empirical question.
In SCoR, the scales are learned through the refined base objective in Eq. (17). Holding the initial prediction and base direction in Eq. (11) fixed gives
=d_i^{(0)}\frac{\partial\mathcal L_{\mathrm{base}}(z^{\mathrm{ref}};\mathcal G,\xi_{\mathrm{ref}})}{\partial z_i^{\mathrm{ref}}}.$$ The scale of each variable receives a training signal through its effect on the refined prediction. The controller determines the effective budget $B=\sum_i\eta_i|d_i^{(0)}|$ as part of the update. The discussion after Proposition 4.2 and in Appendix B.1 explains this distinction between the fixed-budget analysis and the finite-step training objective. The experiments above assess the resulting controller against simpler alternatives under the shared search protocol. **Response to Question 1. Computational cost** Training and neural refinement require no solver calls or solver-generated solution labels. Table 12 in Appendix C.7 reports the incremental costs relative to DiffILO and PUMA. | Method | SC params | CA params | IS params | SC time (h) | CA time (h) | IS time (h) | |---|---:|---:|---:|---:|---:|---:| | DiffILO | 177,620 | 390,644 | 390,644 | 15.748 | 10.587 | 10.234 | | SCoR-DiffILO | 198,133 | 439,157 | 439,157 | 16.344 | 10.849 | 10.949 | | PUMA | 147,254 | 390,710 | 390,710 | 16.230 | 14.271 | 12.282 | | SCoR-PUMA | 164,055 | 440,279 | 440,279 | 16.435 | 14.654 | 13.067 | SCoR increases the parameter count by 11.4%–12.7% and **total training time by 1.3%–7.0%**, including the refinement computation. The increases on SC, CA, and IS are 3.8%, 2.5%, and 7.0% for DiffILO and 1.3%, 2.7%, and 6.4% for PUMA. At test time, the measured prediction-stage overhead, including refinement, was at most 1 second per instance. This corresponds to at most 0.1% of the common 1,000-second limit on downstream solver search. --- We have also updated the manuscript. Changes are marked in blue in the revised PDF. We hope our response resolves your concerns, and we are open to any further discussions.