acceptodds
Under review as a conference paper at ICLR 2027

SHSP: Structure-Aware Hierarchical Solution Prediction for Mixed-Integer Linear Programming

16 views

Abstract

Mixed-Integer Linear Programming (MILP) is a fundamental optimization paradigm in combinatorial optimization and has been widely applied across real-world domains. Due to its NP-hard nature, obtaining optimal solutions for large-scale or highly constrained MILP instances remains computationally prohibitive. Learning-based solution prediction has therefore emerged as a promising approach to provide high-quality variable assignments for solver acceleration. However, existing methods typically adopt a one-shot prediction paradigm that predicts the marginal probabilities of all variables simultaneously. As a result, the conditional dependencies among variables are only implicitly captured through message passing, with the burden of modeling the combinatorial structure falling entirely on the representational capacity of graph neural networks. To address this limitation, we propose the Structure-Aware Hierarchical Solution Prediction (SHSP) framework that replaces the parallel marginal decoding of one-shot methods with a novel hierarchical conditional decoding mechanism. Specifically, SHSP constructs a variable coupling graph from the constraint structure, decodes variables sequentially along a hierarchy of increasing coupling strength, and conditions each hierarchy on previously predicted assignments. To mitigate error accumulation during the decoding process, SHSP further incorporates a confidence-aware mask-and-repair mechanism to identify and correct unreliable intermediate predictions. We integrate SHSP with multiple learning-guided search methods, and evaluate it on four standard MILP benchmarks. Experimental results demonstrate that SHSP significantly outperforms existing one-shot prediction baselines, achieving a 54% average reduction in solution gap.

Primary area:
optimization
Keywords:
Mixed-Integer Linear Programming, Learning for Combinatorial Optimization, Graph Neural Networks, Structure-Aware Solution Prediction

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_beswOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposed to augment existing L2O frameworks for MILPs with an hierarchical-aware GNN component that iteratively predicts variables' assignments. Specifically, a variable coupling graph is used to rank and group variables, and each group is then sequentially predicted in their rank of importance, where predictions with low confidence are masked. Finally, a repair procedure is conducted to further improve the quality of the prediction.

Critical strengths
  1. The idea of variable coupling graph is novel and well-motivated. The computed score, which involves both expected error and optimization-related information, gives a heuristic assesment of the potential importance of a variable to the whole problem.
  2. Sequentially predicting variables sounds like a more proper approach for MILP compared to the existing 1-pass frameworks, as it may better capture variables' dependencies and alleviate constraint-violating predictions.
  3. The numerical results demonstrate clear performance improvements on several benchmarks when integrating the proposed method into existing L2O frameworks for MILP.
Critical weaknesses
  1. There are some computation steps and definitions seems to be unclear or possiblly miss-typed, such as the definition of mm in the triplet.
  2. The definition of each variables' importance seems rather heuristic. There might be some important decision varaibles with low score as they might not be in many constraints.
  3. The inference cost, although being numerically small, is still multiple times larger than the underlying L2O approaches. Because of the iterative nature of the proposed approach, this cost would increase dramatically as the problem size increases, which prohibit it from scaling up.
  4. Some hyper-parameters are not well-explained. Such as how to choose a proper KK.
Questions for authors
  1. All variables are sorted in ascending order of VCS and evenly partitioned into K hierarchies. This seems to be a very naive partitioning rule, which completely ignores that different groups of variables can have different sizes. Could the author clarify on this? Did the author considered to use the magnitude of VCS to partition variables?(like knn)

  2. There are many diffusion-based approaches for combinatorial optimization, such as [1] and [2]. What is the major advantage of the proposed framework comparing against them when operating on CO or binary optimization?

  3. As I said in weakness section, the computational burden seems to be a problem especially for larger problems. Is it possible to compose GNN embeddings with dynamic and static parts? After each group is fixed, the embedding is updated with some simple rules, such as proposed in [3].

  4. Symmetry is still a problem when predicting in groups as symmetric variables can share the same VCS. Is there any possible fix within the proposed framework for symmetry?

[1] Sun, Zhiqing, and Yiming Yang. "Difusco: Graph-based diffusion solvers for combinatorial optimization." Advances in neural information processing systems 36 (2023): 3706-3731.

[2] Sanokowski, Sebastian, Sepp Hochreiter, and Sebastian Lehner. "A diffusion model framework for unsupervised neural combinatorial optimization." arXiv preprint arXiv:2406.01661 (2024).

[3] Gupta, Prateek, et al. "Hybrid models for learning to branch." Advances in neural information processing systems 33 (2020): 18087-18097.

3 comments

Thank you for the detailed feedback.

W1: Clarification of Definitions

Thank you for your constructive comment. In the triplet, mim_i indicates whether variable ii is a prediction target at the current decoding step. It is set to 11 for current prediction targets and 00 otherwise. We have updated Section 3.2 to clarify the relevant definitions and any ambiguous descriptions.

W2: High-VCS Variables and Important Decision Variables

We would like to clarify a conceptual distinction: variables with high Variable Coupling Scores (VCS) are not necessarily important decision variables. VCS measures constraint-induced structural coupling rather than a variable's importance to the objective value. Its purpose is to identify variables whose assignments may strongly affect other variables through shared constraints, thereby guiding prediction and variable selection for search-space reduction.

A variable may have a substantial impact on the objective value even if its VCS is low, because its influence on the objective and its structural coupling are distinct properties. Such important decision variables may remain unfixed and can still be optimized by the downstream MILP solver.

W4: Hyperparameter Selection

Thank you for your constructive comment. We selected the number of hierarchies KK on the validation set separately for each benchmark. For each candidate K∈{2,4,6,8}K \in \{2,4,6,8\}, we computed the mean validation objective averaged across PaS+SHSP and Apollo+SHSP. The table reports these mean validation objectives.

KKCA ↑WA ↓IP ↓SC ↓
298211.375698.91513.075124.395
498146.075698.90513.180124.415
698177.055698.97513.125124.460
898176.250698.96013.090124.440

We chose the KK with the best average validation objective for each benchmark. This gave K=2K=2 for CA, IP, and SC, and K=4K=4 for WA.

Regarding the masking probability, we set it to pmask(i)=0.5×(1−ci)p_{\mathrm{mask}}(i) = 0.5 \times (1 - c_i), with a maximum probability of 0.5.

For the solution-weighting temperature, we use the following problem-specific values, chosen according to the objective-value scale and optimization direction.

Benchmarksolution-weighting temperature
CA−40000
WA400
IP1
SC100

We selected the three additional thresholds jointly on the validation set. For each framework and benchmark, we chose the combination with the best mean objective value.

We have updated Appendix E.5 accordingly.

Q1: Hierarchical Partitioning Strategy

Thank you for your constructive comment. We did consider using the magnitudes of VCS values to partition variables. However, we ultimately chose equal-sized hierarchies with the aim of promoting stable training. We have added further discussion in Appendix G on alternative variable partitioning strategies.

Q2: Comparison with Diffusion-Based Methods

Thank you for your insightful question. The diffusion methods in [1] and [2] have shown promising results on combinatorial optimization. However, evaluating them on our MILP benchmarks would require additional adaptation, which is difficult to complete within the short rebuttal period. Therefore, we chose to compare with FMIP [3]. FMIP uses flow matching, which is closely related to diffusion-based generative modeling. We compared FMIP and SHSP within PaS and Apollo using Gurobi on the CA and SC benchmarks. We will update the comparisons with the diffusion-based methods in our final version.

FrameworkMethodCA ↑SC ↓
PaSFMIP98240.07123.54
PaSSHSP98487.72123.41
ApolloFMIP97930.91123.40
ApolloSHSP98489.24123.37

SHSP achieves better mean objective values in all four comparisons. These results support the effectiveness of structure-guided conditional prediction within the evaluated MILP search frameworks. We have updated Section 4.4 and Table 8 to incorporate this comparison.

Furthermore, our hierarchical prediction strategy could also be integrated into FMIP, enabling it to generate variable assignments in groups conditioned on earlier predictions.

[1] Sun, Zhiqing, and Yiming Yang. "Difusco: Graph-based diffusion solvers for combinatorial optimization." Advances in neural information processing systems 36 (2023): 3706-3731.

[2] Sanokowski, Sebastian, Sepp Hochreiter, and Sebastian Lehner. "A diffusion model framework for unsupervised neural combinatorial optimization." arXiv preprint arXiv:2406.01661 (2024).

[3] Hongpei Li, Hui Yuan, Han Zhang, Jianghao Lin, Dongdong Ge, Mengdi Wang, and Yinyu Ye. FMIP: Joint continuous-integer flow for mixed-integer linear programming. In Proceedings of the 14th International Conference on Learning Representations, Rio de Janeiro, Brazil, 2026.

W3&Q3: Computational Efficiency and GNN Embeddings

Thank you for your constructive comments and insightful questions. Following the idea in [4], we could run the GNN once to obtain structural embeddings and reuse them through lightweight updates at subsequent decoding steps.

In our setting, however, the small KK means that only a few GNN forward passes are required. Since GNN inference already takes little time on our benchmarks, the potential reduction in overall runtime may be modest.

Nevertheless, this approach is compatible with our framework and could benefit our method on much larger instances. We have added further discussion in Appendix G on this potential efficiency improvement.

[4] Gupta, Prateek, et al. "Hybrid models for learning to branch." Advances in neural information processing systems 33 (2020): 18087-18097.

Q4: Handling Variable Symmetry

Thank you for your insightful question. Yes, symmetric variables can share the same variable coupling score (VCS) and may be assigned to the same hierarchy. In this case, their predictions are not directly conditioned on one another.

However, hierarchical prediction can still be useful, since variables in later hierarchies can use earlier retained assignments to refine their predictions, potentially improving the consistency of the overall assignment.

One possible extension is to identify symmetric variables and assign them to separate decoding steps, allowing later predictions to condition on earlier assignments. We have added the discussion in Appendix G.


Thank you again for these comments and questions. We hope our responses help clarify the paper and look forward to your feedback.

Dear Reviewer besw,

Thank you again for your detailed review and constructive suggestions. With approximately 24 hours remaining in the discussion period, we would like to briefly follow up on our rebuttal.

In response to your concerns, we have:

  1. Clarified the definitions, including the meaning of the target indicator in the decoding-state triplet.

  2. Clarified the distinction between structural coupling and a variable’s importance.

  3. Clarified the hyperparameter settings and selection procedures, including how the number of hierarchies K was selected on the validation set.

  4. Explained why we use equal-sized hierarchies.

  5. Added comparisons with FMIP, a flow-matching method for MILP. Our method achieved better mean objective values in all reported comparisons.

  6. Discussed reusing GNN structural embeddings through lightweight updates as a potential way to reduce inference cost.

  7. Discussed how to handle variable symmetry.

We would appreciate hearing whether these responses have addressed your concerns. If any points remain unclear, we would be happy to clarify them before the discussion closes. Thank you again for your time!

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

SHSP replaces one-shot MILP solution prediction with a sequence of predictions over variable groups. A coupling graph determines the weak-to-strong decoding order, while confidence-based masking and a final repair pass aim to limit error propagation. The predictions are combined with a structure-aware variable selection rule and integrated into Neural Diving, Predict-and-Search, and Apollo-MILP. Experiments cover four benchmarks with Gurobi and SCIP, plus a small MIPLIB subset.

Critical strengths

The paper addresses a real limitation of marginal prediction: individually plausible assignments can conflict when used together. Passing partial predictions back into the network is a reasonable way to address this without invoking the solver at every decoding step. The separation between prediction order and downstream fixing order is also interesting.

The evaluation goes beyond prediction accuracy and measures the resulting search performance across three frameworks and two solvers. Some gains are substantial, particularly on CA with Gurobi. Including graph construction in the time budget is appropriate. Tables 5 and 12 also help separate the predictor's contribution from that of the fixing strategy, rather than attributing the entire improvement to prediction alone.

Critical weaknesses

I am not convinced that the stated training objective learns the conditional solution distributions used to motivate the method. In Section 3.2, once teacher forcing is disabled, the history is generated by the model, but each later prediction is still supervised against all solutions with the original weights. For a fixed generated history, the weighted BCE therefore targets the original marginal, not the marginal conditioned on solutions compatible with that history. For example, if the pool consists equally of (0,1) and (1,0), predicting the first variable as zero should make the conditional target of the second variable one; the written loss still gives it a target of 0.5. Appendix E.2 decays teacher forcing to zero after 50 of 500 epochs, so this is relevant to most of training. Iterative refinement may still help empirically, but the claimed move from marginal to conditional prediction needs a clearer justification or a correction to the training description.

The role of the proposed coupling hierarchy is not established by the ablations. Tables 5 and 12 compare the full hierarchical predictor with a one-shot predictor, but do not compare weak-to-strong ordering against random, reversed, or simple degree-based ordering with the same decoding budget. Thus, the gains could come from repeated prediction and repair rather than the particular structural score. The score itself also has an unresolved edge case: in Appendix C, a binary constraint such as x1+x2+x3 <= 2 has zero expected pairwise violation for every pair, leaving the normalization denominator zero, although the full constraint is nontrivial. How such rows are handled matters for both reproducibility and the interpretation of the hierarchy.

Questions for authors
  • When the model-generated history conflicts with some supervised solutions, are those solutions removed or reweighted for subsequent steps? If not, how does the loss learn a conditional distribution rather than the original marginals?
  • With the predictor, masking, repair, and fixing rule held constant, how much does weak-to-strong VCS ordering improve over random or reversed ordering? How are zero expected-violation denominators handled?
  • Are the reported improvements stable across training and masking seeds? The tables average over test instances but do not report variation across repeated runs, which would help interpret the smaller gains on WA and SC.
4 comments

Thank you for the detailed feedback.

W1&Q1: Training Objective and History-consistent Conditional Predictions

Thank you for raising this insightful question. The implemented objective is consistent with the loss described in the paper. When the history is generated by the model, all solutions in the training pool, including those that conflict with that history, contribute to the training objective with their original weights. We would like to clarify two aspects of our training design.

First, our training procedure enables the predictor to learn and exploit conditional dependencies. Teacher forcing allows the model to learn conditional relationships between earlier and subsequent variable assignments, similar to imitation learning. As the teacher-forcing ratio gradually decreases, the predictor is increasingly exposed to its own generated histories, helping it adapt to the histories encountered during inference. After teacher forcing is removed, the predictor can still leverage the conditional relationships learned during the teacher forcing stages, though the implemented training objective may not guarantee learning the optimal conditional probabilities.

Second, we adopt the current training objective rather than strict conditional-distribution supervision for practical reasons. As the number of assigned variables increases, the fixed solution pool may contain very few solutions compatible with a particular partial assignment, or none at all. Consequently, estimating conditional distributions from compatible solutions can become unreliable. Generating additional compatible solutions for individual histories would also incur substantial computational costs, especially given the combinatorial number of possible histories.

We have updated Appendix G to explain why we chose this design.

W2&Q2: Prediction Order Ablation and Handling Special Cases in Coupling Score Computation

Thank you for your insightful questions.

  1. We agree that the original ablations did not directly evaluate the choice of prediction order. We therefore conducted additional experiments comparing four orderings: ascending VCS (Weak-to-Strong), descending VCS (Strong-to-Weak), Random, and Degree-Based. The table reports mean objective values for PaS and Apollo using Gurobi as the downstream solver.
FrameworkPrediction orderCA ↑WA ↓IP ↓SC ↓
PaSWeak-to-Strong98487.72706.9911.97123.41
PaSStrong-to-Weak98314.52707.0112.10123.51
PaSRandom98441.76707.0312.11123.49
PaSDegree-Based98428.37707.0112.09123.53
ApolloWeak-to-Strong98489.24707.0111.71123.37
ApolloStrong-to-Weak98272.69707.0211.84123.44
ApolloRandom98353.33707.0611.79123.53
ApolloDegree-Based98410.71707.0511.82123.37

For both PaS and Apollo, weak-to-strong VCS ordering achieved better mean objective values than random and reversed ordering on each of the four benchmarks. It also outperformed degree-based ordering in seven of the eight framework–benchmark combinations and tied on Apollo–SC at the reported precision. These results support the proposed ordering on the evaluated benchmarks.

We have updated Section 4.3 and Table 4 to incorporate this ablation.

  1. When all retained variable pairs in a constraint have zero expected violation, the normalization denominator is zero. In this case, we set all pairwise coupling weights in that constraint to zero. Below, we explain why this situation arises and conduct experiments to see how it affects solving performance. The results show that this handling has a limited impact on solving performance.

This situation arises because our coupling score is designed to identify strong direct interactions between variable pairs induced by shared constraints, rather than attempting to characterize all possible dependencies among variables. By focusing on these pairwise interactions, our method provides focused structural guidance for hierarchical partitioning, enabling a clearer separation of variables by coupling score and thereby making the relevant dependencies easier for the predictor to learn. Importantly, even when certain interactions are not explicitly captured by the coupling score, the corresponding constraints remain represented in the bipartite graph, allowing the predictor to further exploit their structural information.

In the datasets we examined, this case occurred only in IP. Such constraints accounted for 5.13%–15.38% of all constraints per instance, with an average of 8.74%. To investigate the effect of explicitly handling these constraints, we designed an alternative version of VCS with the following modified expected-violation values:

\begin{cases} \epsilon, & \text{if } P_{uv}^{(c)} = 0\ \forall (u,v) \in E_c \text{ and } \max_{x \in D_c} \sum_k a_{ck} x_k > b_c, \\ P_{ij}^{(c)}, & \text{otherwise}, \end{cases} \qquad (i,j) \in E_c.$$ Here, $E_c$ denotes the legal variable pairs in constraint $c$. $D_c$ is the Cartesian product of their individual domains. We compared the original version with this alternative version on the 87 IP test instances containing such constraints. The table reports mean objective values, with lower values indicating better performance. | **Method** | **Original** version | Alternative version | | ----------- | -------------------- |:------------------- | | PaS+SHSP | **11.22** | 11.33 | | ND+SHSP | **11.36** | **11.36** | | Apollo+SHSP | **11.07** | 11.25 | The original version achieves lower mean objective values for PaS and Apollo, while the two approaches tie for ND. We suspect that this may be related to the alternative version being less effective at capturing particularly strongly coupled variables. These results indicate that assigning additional coupling weights to zero-expected-violation pairs does not necessarily provide more effective structural guidance for downstream solving. In the extreme case where all constraints in a problem are of this type, VCS provides no information for distinguishing variables. However, hierarchical prediction can still use earlier retained assignments to benefit later predictions. We have updated this discussion in Appendix G accordingly.

Q3: Robustness Across Random Seeds

Thank you for your insightful question. The reported improvements are stable. We repeated the experiments with three different random seeds and report mean objective values ± sample standard deviations across these runs. SHSP achieves better mean objective values in all 24 evaluated settings across the three frameworks, two solvers, and four benchmarks. These results show that the average improvements persist across the three runs.

GurobiMethodCA ↑WA ↓IP ↓SC ↓
NDOriginal94339.40 ± 3.23707.09 ± 0.0414.12 ± 0.06123.53 ± 0.07
NDSHSP97153.42 ± 29.05707.04 ± 0.0411.90 ± 0.06123.46 ± 0.06
PaSOriginal97849.73 ± 39.28707.04 ± 0.0312.09 ± 0.06123.54 ± 0.09
PaSSHSP98470.76 ± 14.98707.02 ± 0.0611.99 ± 0.02123.50 ± 0.09
ApolloOriginal97992.97 ± 10.14707.08 ± 0.0312.00 ± 0.03123.44 ± 0.03
ApolloSHSP98450.82 ± 33.27707.04 ± 0.0311.80 ± 0.14123.39 ± 0.02
SCIPMethodCA ↑WA ↓IP ↓SC ↓
NDOriginal94338.55 ± 0.97707.66 ± 0.1515.72 ± 0.53125.69 ± 0.17
NDSHSP97244.08 ± 26.83707.11 ± 0.0814.28 ± 0.51125.60 ± 0.22
PaSOriginal97203.57 ± 58.62708.32 ± 0.0519.70 ± 0.23125.47 ± 0.31
PaSSHSP97298.81 ± 94.06708.20 ± 0.0119.59 ± 0.26125.42 ± 0.09
ApolloOriginal96322.53 ± 46.25708.32 ± 0.1119.53 ± 0.85126.04 ± 0.29
ApolloSHSP97116.02 ± 76.05708.16 ± 0.0418.14 ± 0.47125.87 ± 0.37

We have updated Appendix F.2 and Table 20 accordingly.


Thank you again for these comments and questions. We hope our responses help clarify the paper and look forward to your feedback.

Dear Reviewer ZcTS,

Thank you again for your detailed review and constructive suggestions. With approximately 24 hours remaining in the discussion period, we would like to briefly follow up on our rebuttal.

In response to your concerns, we have:

  1. Clarified the training objective, the role of teacher forcing, and the practical reasons for this design.

  2. Added prediction-order ablations comparing Weak-to-Strong, Strong-to-Weak, Random, and Degree-Based orderings, with our proposed Weak-to-Strong ordering achieving the best mean objective values among them.

  3. Clarified the handling of zero denominators in expected-violation normalization.

  4. Repeated the main experiments with three random seeds and reported means and sample standard deviations. Our method achieved better mean objective values than the corresponding baselines in all evaluated settings.

We would appreciate hearing whether these responses have addressed your concerns. If any points remain unclear, we would be happy to clarify them before the discussion closes. Thank you again for your time!

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

In the solution prediction task for Mixed-Integer Linear Programming (MILP), existing methods typically use GNNs to predict the values of all variables in a one-shot manner, without explicitly considering dependencies among variables during prediction. The authors propose the SHSP (Structure-Aware Hierarchical Solution Prediction) framework, which constructs a variable coupling graph based on constraint violation and coefficient importance, and divides variables into different hierarchies according to their coupling scores, progressively predicting them from weakly coupled to strongly coupled variables. Additionally, the authors use a Mask-and-Repair mechanism to mask and repair low-confidence predictions, reducing error propagation. Finally, they combine variable coupling strength and prediction confidence to select variables to fix, reducing the solver's search space. The authors compare SHSP with multiple baselines, including ND, PaS, and Apollo, on four MILP datasets: CA, WA, IP, and SC. Experimental results show that SHSP reduces the Absolute Primal Gap by approximately 54% on average when using Gurobi as the solver.

Critical strengths
  1. The paper constructs a variable coupling graph based on the MILP constraint structure and measures the dependencies among different variables through variable coupling scores, providing a basis for subsequent hierarchical prediction, which has a certain degree of novelty.

  2. The paper replaces the traditional one-shot prediction of GNNs with hierarchical conditional prediction, predicting variables from weakly coupled to strongly coupled according to their coupling strength, and using predictions from previous hierarchies to assist subsequent variable predictions, which can better consider dependencies among variables.

  3. The authors use a Mask-and-Repair mechanism to reduce error propagation in multi-stage prediction, and combine variable coupling strength and prediction confidence to select variables to fix, improving MILP solving performance from both prediction and search-space reduction perspectives.

  4. SHSP outperforms multiple baselines, including ND, PaS, and Apollo, on four datasets: CA, WA, IP, and SC. The authors also conduct experiments with two solvers, Gurobi and SCIP, and validate the effectiveness of different components through ablation studies.

Critical weaknesses
  1. SHSP predicts variables from weakly coupled to strongly coupled according to their coupling scores. The authors argue that weakly coupled variables are less affected by other variables and are therefore more suitable for earlier prediction, but the paper does not experimentally validate this assumption. The existing ablation studies only show that hierarchical prediction is more effective than one-shot prediction, but do not demonstrate that the weak-to-strong ordering is better. Please add ablation studies with different prediction orders, such as Strong-to-Weak and Random Ordering.

  2. The authors use Expected Violation and Coefficient Importance to construct the variable coupling graph. However, Expected Violation only considers the influence of two variables on a constraint, without considering the values of other variables in the same constraint. Can the coupling scores calculated in this way accurately reflect the dependencies among variables?

Questions for authors

See Weeknesses 1-2.

4 comments

Thank you for these constructive comments. We address the two concerns below.

Q1: Prediction Order Ablation

Thank you for your constructive comment. We agree that the original ablations did not directly evaluate the choice of prediction order. Thanks to your suggestion, we conducted additional experiments comparing three orderings: ascending VCS (Weak-to-Strong), descending VCS (Strong-to-Weak), and random ordering. The results below report mean objective values for PaS and Apollo using Gurobi as the downstream solver.

FrameworkPrediction orderCA ↑WA ↓IP ↓SC ↓
PaSWeak-to-Strong98487.72706.9911.97123.41
PaSStrong-to-Weak98314.52707.0112.10123.51
PaSRandom98441.76707.0312.11123.49
ApolloWeak-to-Strong98489.24707.0111.71123.37
ApolloStrong-to-Weak98272.69707.0211.84123.44
ApolloRandom98353.33707.0611.79123.53

For both PaS and Apollo, weak-to-strong VCS ordering achieved better mean objective values than random and reversed ordering on each of the four benchmarks. These results provide direct empirical support for the proposed ordering on the evaluated benchmarks. We have updated Section 4.3 and Table 4 to incorporate this ablation.

Q2: Validity of Coupling Scores

Thank you for raising this insightful question. Dependencies among variables are complex, and the interaction between a variable pair can depend on the assignments of other variables within the same constraint. We acknowledge that Expected Violation does not explicitly model these assignments and therefore cannot fully characterize such interactions. Below, we explain why we designed it in this way.

Our coupling score is designed to identify strong direct interactions between variable pairs induced by shared constraints, rather than attempting to characterize all possible dependencies among variables. By focusing on these pairwise interactions, our method provides focused structural guidance for hierarchical partitioning, enabling a clearer separation of variables by coupling score and thereby making the relevant dependencies easier for the predictor to learn. Importantly, even when certain interactions are not explicitly captured by the coupling score, the corresponding constraints remain represented in the bipartite graph, allowing the predictor to further exploit their structural information.

Although this characterization is relatively simple, it can still provide useful structural information to guide prediction and ultimately improve solving performance. The experimental results reported in the paper further support this view. We believe our method offers a useful insight: explicitly considering structural information during prediction can improve practical performance.

We have updated this discussion in Appendix G accordingly.


Thank you again for these comments. We hope our responses help clarify the paper and look forward to your feedback.

Thank you for your detailed response and additional experiments. I have two follow-up comments:

  1. Prediction Order Ablation: I appreciate the additional experiments comparing different prediction orders. However, the performance differences are relatively small on some datasets. If time permits, I would encourage the authors to report results averaged over multiple random seeds, along with standard deviations, to further validate the robustness of the findings.

  2. Validity of Coupling Scores: My concern is not that the method must fully model all dependencies among variables, but rather whether the coupling scores remain reliable for distinguishing weakly and strongly coupled variables when the assignments of other variables within the same constraint are not considered.

Q1: Robustness of Prediction Order Ablation

Thank you for this helpful suggestion. We have revised to repeat the prediction-order ablation experiments with three different random seeds due to time limit. The table below reports mean objective values ± sample standard deviations across the three runs, using Gurobi as the downstream solver. Bold values indicate the best mean objective within each framework.

FrameworkPrediction orderCA ↑WA ↓IP ↓SC ↓
PaSWeak-to-Strong98470.76 ± 14.98707.02 ± 0.0611.99 ± 0.02123.50 ± 0.09
PaSStrong-to-Weak98303.29 ± 34.22707.03 ± 0.0212.18 ± 0.14123.51 ± 0.01
PaSRandom98442.32 ± 18.06707.04 ± 0.0212.14 ± 0.03123.52 ± 0.07
ApolloWeak-to-Strong98450.82 ± 33.27707.04 ± 0.0311.80 ± 0.14123.39 ± 0.02
ApolloStrong-to-Weak98281.64 ± 15.43707.05 ± 0.0411.93 ± 0.10123.48 ± 0.05
ApolloRandom98321.94 ± 28.75707.06 ± 0.0111.84 ± 0.08123.50 ± 0.08

Weak-to-Strong ordering achieves better mean objective values than both Strong-to-Weak and Random ordering on all four benchmarks in both frameworks. These results show that the improvements in mean performance persist when averaged over three random seeds, providing additional empirical support for the proposed prediction order. We have updated Appendix F.2 and Table 22 accordingly. Thank you again for this helpful suggestion.

Q2: Validity of Coupling Scores

Thank you for clarifying your concern. We are sorry that we did not fully understand this concern before. We believe that the score remains reliable for distinguishing weakly and strongly coupled variables within our framework and therefore provides reliable structural guidance for hierarchical partitioning and prediction.

Our framework uses coupling score to construct a small number of hierarchies. Ranking differences within the same hierarchy do not change the partition. The framework therefore requires a stable separation of broad coupling levels, rather than a precise ordering of every variable. By combining pairwise Expected Violation and Coefficient Importance, our score helps identify reliable strong direct interactions between variables induced by shared constraints, thereby helping identify strongly coupled variables. Moreover, our structure-aware fixing strategy selects only high-VCS variables. Lower-VCS variables remain unfixed and can be optimized by the downstream solver. For variable selection, distinguishing high-coupling candidates from the remaining variables is more important than precisely ordering the lower-coupling variables. Therefore, we believe that our coupling score provides reliable structural information for our framework.

To test how considering the other variables affects the variable ranking based on VCS, we evaluated an alternative definition of Expected Violation that explicitly accounts for the other variables in the constraint:

bc,ij=bc−E[∑k≠i,jackXk],b_{c,ij} = b_c - \mathbb{E}\left[\sum_{k\ne i,j} a_{ck}X_k\right], Pij(c)=EXi,Xj[Δ□(aciXi+acjXj;,bc,ij)].P_{ij}^{(c)} = \mathbb{E}_{X_i,X_j}\left[\Delta_{\square}\left(a_{ci}X_i+a_{cj}X_j;\\,b_{c,ij}\right)\right].

Here, □∈{≤,≥,=}\square\in\{\le,\ge,=\} denotes the constraint sense. The expectations follow the same uniform-domain assumptions as the original Expected Violation definition. All subsequent normalization, coefficient-importance calculations, and VCS aggregation remain unchanged. We compared the variable rankings induced by the original VCS definition and the alternative definition. We evaluated their consistency on the test sets using Spearman’s rank correlation coefficient, where values closer to 1 indicate more similar rankings. We also measured group assignment agreement which means the proportion of variables assigned to the same hierarchical group under the two definitions:

DatasetVariable group-assignment agreementMean Spearman correlation
CA100.00%1.0000
IP99.43%0.9997
WA100.00%1.0000
SC (with ε regularization)100.00%1.0000

The two definitions produce nearly identical variable rankings and hierarchical partitions. These results support our view that our VCS remains reliable for distinguishing weakly and strongly coupled variables within our framework.

We have added the discussion in Appendix G.


Thank you again for these comments. We hope our responses help clarify the paper and look forward to your feedback.

Thanks for response, your rebuttal addressed most of my concerns. I will maintain my original rating.

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

The paper proposes SHSP, a structure-aware hierarchical solution predictor for MILPs with binary integer variables. It constructs a weighted variable coupling graph using pairwise expected constraint violation and coefficient importance, partitions binary variables by their coupling scores, and predicts assignments sequentially from weakly to strongly coupled groups. Earlier predictions provide context for subsequent groups. Confidence-based masking and a final repair step aim to mitigate error propagation, while a structure-aware variable selection rule guides downstream fixing or trust-region search. SHSP is integrated into Neural Diving, Predict-and-Search, and Apollo-MILP. Evaluation covers four main benchmarks with Gurobi and SCIP, together with a small MIPLIB subset, and reports improvements in objective values and primal gaps relative to the original predictors.

Critical strengths
  1. The predictor is integrated into three existing learning-guided search frameworks and evaluated with two downstream solvers. This breadth makes the proposed interface practically relevant and provides evidence that its benefits can extend across different search pipelines.

  2. The reported improvements are substantial in several settings, particularly CA and IP with Gurobi. The paper also includes component ablations and explicitly accounts for graph construction and updates within the solving budget. These are useful elements of the empirical evaluation and support taking the observed gains seriously.

Critical weaknesses
  1. The central dependency-modeling mechanism is not adequately established. As written, the coupling normalization in Appendix C is undefined for some valid, non-redundant constraints. Separately, the multi-solution BCE objective does not explain how supervision becomes consistent with model-generated histories after teacher forcing is removed. Since the coupling scores determine both the hierarchy and variable selection, and conditional dependency modeling is the central claimed contribution, these are substantive methodological concerns. Questions 1 and 2 provide concrete examples requiring resolution.

  2. The experiments do not sufficiently identify the contribution of the proposed structural design. Tables 5 and 12 provide useful component ablations, but do not isolate the proposed ordering from alternative orderings with the same number of GNN passes. Appendix E.3 also allows SHSP to fix fewer variables than the original methods, leaving structural selection confounded with fixing cardinality. The absence of a closely related correlation-aware predictor baseline and uncertainty estimates further limits the conclusions. Substantial controlled validation is needed to establish the claimed source and robustness of the improvements.

Questions for authors

The following seven clarification and validation requests could materially affect my assessment.

  1. Is the coupling score well-defined on restrictive constraints with zero pairwise violation? In Appendix C (pp. 14–15), consider x1+x2+x3≤2x_1+x_2+x_3\leq 2 with binary variables. Every pair alone has zero expected violation, so the proposed normalization gives 0/00/0, although the full constraint excludes (1,1,1)(1,1,1). How is this handled in the implementation, and how is the actual coupling represented if regularization makes all these pair weights zero? Please also clarify the assumptions or preprocessing for unbounded or zero-width continuous-variable domains.

  2. How does the training objective learn history-consistent conditional predictions? Section 3.2 and Appendix E.2 describe weighted BCE over multiple solutions, with teacher forcing reduced to zero after 50 of 500 epochs. If the decoded history is independent of the supervised solution index, minimizing this BCE still targets weighted marginals. For equally weighted solutions (1,0)(1,0) and (0,1)(0,1), the second-variable target remains 0.50.5, whereas conditioning on x1=0x_1=0 requires x2=1x_2=1. Are training solutions filtered, reweighted, or otherwise matched to the decoded history? If the implemented objective differs from the written one, please specify it.

  3. Does the specific coupling score and weak-to-strong order explain the gains? Please compare random, reverse, and simple degree-based orderings under the same number of GNN passes, repair procedure, and fixing rule. The current ablations compare whole predictors, so they do not separate the proposed structural hierarchy from generic multi-step refinement. Such controls would directly test the paper's central structural hypothesis.

  4. Do the gains persist when the actual fixing counts are matched? Appendix E.3 (p. 16) states that k0k_0 and k1k_1 are only upper bounds and that no variables are added if thresholding selects fewer. Thus, using the same nominal bounds does not match the actual number of fixed variables. Please report realized fixing counts and feasible-completion rates, and compare against confidence-only selection with matched counts and against confidence thresholding without coupling-based filtering. These comparisons would distinguish structural selection from simply fixing fewer variables.

  5. How does SHSP compare with a predictor that already explicitly models variable correlations? Appendix A.2 acknowledges this property of CoCo-MILP, but the experiments compare against the original predictors in ND, PaS, and Apollo. A comparison using the same training data, downstream search framework, and time budget would clarify whether hierarchical decoding provides gains beyond a relevant correlation-aware predictor. If such a comparison is infeasible, please explain the specific incompatibility and narrow the corresponding claims.

  6. Are the improvements reproducible and robust to the method's randomness? Please provide variability across training seeds and stochastic masking runs, together with paired instance-level uncertainty estimates. This matters especially for small SCIP improvements, such as PaS on CA (0.51%) and IP (2.15%) in Table 3. Please also specify the exact masking probability currently written only as pmask(i)∝1−cip_{\mathrm{mask}}(i)\propto 1-c_i, the solution-weighting temperature τ\tau, and the validation protocol used to select the additional thresholds.

  7. What precisely does the headline 54% improvement summarize? The mean of the 12 tabulated relative reductions in Table 2 is approximately 54.0%, whereas the corresponding mean in Table 3 is approximately 25.9%; averaging all 24 configurations gives approximately 39.9%. Please state the aggregation scope explicitly. Also, Section 4.1 updates BKS using better solutions found by SHSP, so a zero gap establishes that the method reaches the resulting best-known incumbent. Please distinguish this from certified optimality and clarify the reference values used for all comparisons.

5 comments

Thank you for the detailed feedback.

W1&Q1: Handling Special Cases in Coupling Score Computation

Thank you for raising these insightful questions. When all retained variable pairs in a constraint have zero expected violation, the normalization denominator is zero. In this case, we set all pairwise coupling weights in that constraint to zero. Below, we explain why this situation arises and report experiments evaluating the effect of setting zero weights. The results show that this handling has a limited impact on solving performance.

This situation arises because our coupling score is designed to identify strong direct interactions between variable pairs induced by shared constraints, rather than attempting to characterize all possible dependencies among variables. By focusing on these pairwise interactions, our method provides focused structural guidance for hierarchical partitioning, enabling a clearer separation of variables by coupling score and thereby making the relevant dependencies easier for the predictor to learn. Importantly, even when certain interactions are not explicitly captured by the coupling score, the corresponding constraints remain represented in the bipartite graph, allowing the predictor to further exploit their structural information.

In the datasets we examined, this case occurred only in IP. Such constraints accounted for 5.13%–15.38% of all constraints per instance, with an average of 8.74%. To investigate the effect of explicitly handling these constraints, we designed an alternative version of VCS with the following modified expected-violation values:

\begin{cases} \epsilon, & \text{if } P_{uv}^{(c)} = 0\ \forall (u,v) \in E_c \text{ and } \max_{x \in D_c} \sum_k a_{ck} x_k > b_c, \\ P_{ij}^{(c)}, & \text{otherwise}, \end{cases} \qquad (i,j) \in E_c.$$ Here, $E_c$ denotes the legal variable pairs in constraint $c$. $D_c$ is the Cartesian product of their individual domains. We compared the original version with this alternative version on the 87 IP test instances containing such constraints. The table reports mean objective values, with lower values indicating better performance. | **Method** | **Original** version | Alternative version | | ----------- | -------------------- |:------------------- | | PaS+SHSP | **11.22** | 11.33 | | ND+SHSP | **11.36** | **11.36** | | Apollo+SHSP | **11.07** | 11.25 | The original version achieves lower mean objective values for PaS and Apollo, while the two approaches tie for ND. We suspect that this is related to the alternative version being less effective at capturing particularly strongly coupled variables. These results indicate that assigning additional coupling weights to zero-expected-violation pairs does not necessarily provide more effective structural guidance for downstream solving. In the extreme case where all constraints in a problem are of this type, VCS provides no information for distinguishing variables. However, hierarchical prediction can still use earlier retained assignments to benefit later predictions. For continuous variables with unbounded domains, we first attempt to derive valid finite bounds from the constraints, for example through bound tightening during presolve, and use these bounds for coupling-score computation. If finite bounds remain unavailable, we exclude pairs involving those variables from coupling-score computation. We verified that all continuous variables in our experimental instances had finite bounds, so no pairs were excluded due to unbounded domains. For a variable with a zero-width domain, we substitute its fixed value into the constraints and adjust the constant terms accordingly before computing coupling scores. It therefore requires no pairwise coupling calculation. We have updated this discussion in Appendix G accordingly.

W1&Q2: Training Objective and History-consistent Conditional Predictions

Thank you for raising this insightful question. The implemented objective is consistent with the loss described in the paper. We would like to clarify two aspects of our training design.

First, our training procedure enables the predictor to learn and exploit conditional dependencies. Teacher forcing allows the model to learn conditional relationships between earlier and subsequent variable assignments, similar to imitation learning. As the teacher-forcing ratio gradually decreases, the predictor is increasingly exposed to its own generated histories, helping it adapt to the histories encountered during inference. After teacher forcing is removed, the predictor can still leverage the conditional relationships learned during the teacher forcing stages, though the implemented training objective may not guarantee learning the optimal conditional probabilities.

Second, we adopt the current training objective rather than strict conditional-distribution supervision for practical reasons. As the number of assigned variables increases, the fixed solution pool may contain very few solutions compatible with a particular partial assignment, or none at all. Consequently, estimating conditional distributions from compatible solutions can become unreliable. Generating additional compatible solutions for individual histories would also incur substantial computational costs, especially given the combinatorial number of possible histories.

We have updated Appendix G to explain why we chose this design.

W2&Q3: Prediction Order Ablation

Thank you for pointing out this issue.

We agree that the original ablations did not directly evaluate the choice of prediction order. Thanks to your suggestion, we conducted additional experiments comparing four orderings: ascending VCS (Weak-to-Strong), descending VCS (Strong-to-Weak), Random, and Degree-Based. The table reports mean objective values for PaS and Apollo using Gurobi as the downstream solver.

FrameworkPrediction orderCA ↑WA ↓IP ↓SC ↓
PaSWeak-to-Strong98487.72706.9911.97123.41
PaSStrong-to-Weak98314.52707.0112.10123.51
PaSRandom98441.76707.0312.11123.49
PaSDegree-Based98428.37707.0112.09123.53
ApolloWeak-to-Strong98489.24707.0111.71123.37
ApolloStrong-to-Weak98272.69707.0211.84123.44
ApolloRandom98353.33707.0611.79123.53
ApolloDegree-Based98410.71707.0511.82123.37

For both PaS and Apollo, weak-to-strong VCS ordering achieved better mean objective values than random and reversed ordering on each of the four benchmarks. It also outperformed degree-based ordering in seven of the eight framework–benchmark combinations and tied in the remaining combination. These results demonstrate the effectiveness of the proposed ordering in our method.

We have updated Section 4.3 and Table 4 to incorporate this ablation.

W2&Q4: Experiments with Matched Numbers of Fixed Variables

Thank you for pointing out these issues. We have added additional experiments to address them.

  1. We report the mean realized fixing counts below, together with the corresponding upper bounds k0k_0 and k1k_1. Downstream search found a feasible solution for every evaluated instance, yielding a feasible-completion rate of 100% on each benchmark.
BenchmarkMean count fixed to 0 / k0k_0Mean count fixed to 1 / k1k_1Feasible-completion rate
CA365.64 / 6000 / 0100%
WA0 / 0497.02 / 500100%
IP376.23 / 4000.61 / 5100%
SC2000 / 20000 / 0100%
  1. We compare our method against confidence-only selection with matched counts. Across PaS and Apollo with Gurobi on the four benchmarks, SHSP achieves better mean objective values in 7 of the 8 settings and ties in the remaining setting. These results show that the gains persist when actual fixing counts are matched.
GurobiMethodCA ↑WA ↓IP ↓SC ↓
PaSfix-match98399.47707.0112.13123.44
PaSSHSP98487.72706.9911.97123.41
Apollofix-match98482.42707.0211.74123.37
ApolloSHSP98489.24707.0111.71123.37
  1. We also compare our method against confidence thresholding without coupling-based filtering.
GurobiMethodCA ↑WA ↓IP ↓SC ↓
PaSconfidence thresholding only98414.98707.0312.26123.44
PaSSHSP98487.72706.9911.97123.41
Apolloconfidence thresholding only98425.37707.0511.99123.37
ApolloSHSP98489.24707.0111.71123.37

Across PaS and Apollo with Gurobi on the four benchmarks, SHSP achieves better mean objective values in 7 of the 8 settings and ties in the remaining setting. These results show the effectiveness of coupling-based filtering.

The comparisons in items 2 and 3 help distinguish the contribution of structural selection from the effect of fixing fewer variables.

We have updated Appendix F and Tables 17-19 accordingly.

W2&Q5: CoCo-MILP Comparison

Following your suggestion, we have conducted additional comparisons with CoCo-MILP. We evaluate both methods using the same training data, downstream search framework, and 1000-second time budget, with Gurobi as the downstream solver. The table reports mean objective values.

GurobiMethodCA ↑WA ↓IP ↓SC ↓
NDCoCo-MILP96709.99707.0911.98123.53
NDSHSP97121.05707.0711.83123.51
PaSCoCo-MILP98446.92707.0512.26123.58
PaSSHSP98487.72706.9911.97123.41

SHSP achieves better mean objective values on all four benchmarks in both frameworks. These results support the effectiveness of the complete SHSP design when compared with a correlation-aware predictor within the same downstream search framework. We have updated Section 4.4 and Table 7 to incorporate this comparison.

Comments on the paper

2 comments

Dear Reviewer ZcTS,

Thank you for your reply. However, we would like to point out that our paper does not use EMA-based self-distillation, and this mechanism was not mentioned in your original review. Furthermore, your original review did not explicitly raise concerns about scalability, computational overhead, or methodological novelty.

It seems that your follow-up comment was intended for a different paper and was inadvertently posted here.

We would appreciate it if you could double-check whether your follow-up comment was intended for our paper and take another look at our rebuttal. If you have any remaining concerns or further questions about our paper, we would be very happy to address them.

Thank you again for your time!

AuthorsOpenReview ↗

General Response

Dear Reviewers and Area Chair,

Thank you for your careful reviews and constructive suggestions. Below, we summarize the main revisions made in response to your comments. We highlight main text changes in red.

Additional ablations (n5fi, Tj1P, ZcTS). We added prediction-order ablations comparing our Weak-to-Strong VCS ordering against reversed, random, and degree-based orderings. We also evaluated our fixing strategy against count-matched confidence-only selection and confidence thresholding without coupling-based filtering. Our method achieves better overall performance in both sets of ablations, providing further support for its effectiveness. (Section 4.3, Table 4 and Appendix F.1, Table 17-19)

Robustness across random seeds (n5fi, Tj1P, ZcTS). We repeated both the main evaluation and the prediction-order ablations with three random seeds, reporting means and sample standard deviations. The improvements in mean performance persist when averaged across the three runs. (Appendix F.2, Table 20-22)

Additional baselines (n5fi, besw). We added comparisons with CoCo-MILP, a correlation-aware predictor, and FMIP, a flow-matching method for MILP. SHSP achieves better mean objective values in all reported comparisons, which further supports the effectiveness of our method. (Section 4.4, Table 7-8)

Coupling-score validity and handling of special cases (n5fi, Tj1P, ZcTS). We clarified the rationale behind our coupling score and the handling of special cases in its computation. We also added two experiments to further assess these design choices. The results provide additional empirical support for our design. (Appendix G, Table 26-27)

Design choices and hyperparameters (n5fi, ZcTS, besw). We clarified the training objective, the role of teacher forcing, and the practical reasons for this training design. We also explained the use of equal-sized hierarchies and clarified the hyperparameter settings and the validation protocol used to select the additional thresholds. (Appendix G and Appendix E.5, Table 13)

Definitions and presentation (n5fi, besw). We clarified the decoding-state definitions and revised potentially misleading statements, including the scope of the reported 54% improvement and the distinction between matching the best-known feasible objective and achieving certified optimality. (Abstract, Section 3.2 and Section 4.1)

Further discussion (besw). We expanded the discussion of potential efficiency improvements through GNN embedding reuse and the handling of variable symmetry. (Appendix G)

We address each reviewer's questions in detail in the individual replies.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.