- 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
- 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.
- 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.
- The numerical results demonstrate clear performance improvements on several benchmarks when integrating the proposed method into existing L2O frameworks for MILP.
Critical weaknesses
- There are some computation steps and definitions seems to be unclear or possiblly miss-typed, such as the definition of in the triplet.
- 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.
- 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.
- Some hyper-parameters are not well-explained. Such as how to choose a proper .
Questions for authors
-
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)
-
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?
-
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].
-
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
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.
| Framework | Method | CA ↑ | SC ↓ |
|---|---|---|---|
| PaS | FMIP | 98240.07 | 123.54 |
| PaS | SHSP | 98487.72 | 123.41 |
| Apollo | FMIP | 97930.91 | 123.40 |
| Apollo | SHSP | 98489.24 | 123.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 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:
-
Clarified the definitions, including the meaning of the target indicator in the decoding-state triplet.
-
Clarified the distinction between structural coupling and a variable’s importance.
-
Clarified the hyperparameter settings and selection procedures, including how the number of hierarchies K was selected on the validation set.
-
Explained why we use equal-sized hierarchies.
-
Added comparisons with FMIP, a flow-matching method for MILP. Our method achieved better mean objective values in all reported comparisons.
-
Discussed reusing GNN structural embeddings through lightweight updates as a potential way to reduce inference cost.
-
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!
Thank you for the detailed feedback.
W1: Clarification of Definitions
Thank you for your constructive comment. In the triplet, mi indicates whether variable i is a prediction target at the current decoding step. It is set to 1 for current prediction targets and 0 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 K on the validation set separately for each benchmark. For each candidate K∈{2,4,6,8}, we computed the mean validation objective averaged across PaS+SHSP and Apollo+SHSP. The table reports these mean validation objectives.
We chose the K with the best average validation objective for each benchmark. This gave K=2 for CA, IP, and SC, and K=4 for WA.
Regarding the masking probability, we set it to pmask(i)=0.5×(1−ci), 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.
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.