Edge Matters: A Predict-and-Search Framework for MILP based on Sinkhorn-Nomalized Edge Attention Networks and Adaptive Regret-Greedy Search

1. Insufficient Comparison with Diverse GNN Models

Weakness: Although the paper introduces the SKEGAT model and demonstrates its effectiveness, the comparison is largely limited to GAT and GCN in the ablation study. This narrow scope misses the opportunity to benchmark SHARP against other cutting-edge graph neural network models, such as Graph Isomorphism Networks (GIN) or Transformer-based graph architectures, which might provide additional insights into the specific benefits of the proposed method.

Suggestion: Include more comprehensive comparisons with a broader range of GNN architectures, such as GIN or Graph Transformer models, which have been effective in graph representation tasks. This would further validate the superiority of SKEGAT and provide deeper insights into its strengths and limitations.

2. Limited Generalizability to Non-bipartite Graph Structures

Weakness: The current approach primarily focuses on bipartite graph representation and normalization techniques for MILP. This focus may restrict its applicability when dealing with non-bipartite or more complex graph structures that are common in real-world MILP problems. The methodology lacks a discussion of how the framework could be adapted or extended to handle these different types of graph structures effectively.

Suggestion: Consider including a section on potential extensions of the SHARP framework to handle more diverse graph structures. Discussing how the framework might generalize beyond bipartite graphs and the challenges associated with such extensions would strengthen the paper's scope and practical relevance.

3. Sparse Evaluation Metrics

Weakness: The evaluation metrics used, such as primal gap, survival rate, and primal integral, provide useful insights but might not fully capture the practical usability and efficiency of the SHARP framework in different settings. For example, the time complexity analysis is provided only in terms of O-notation, without concrete runtime measurements or memory consumption data.

Suggestion: Add empirical analysis of runtime and memory usage to better demonstrate the efficiency and scalability of SHARP, particularly for large-scale MILP problems. These practical metrics would make the results more compelling, particularly for industrial applications where resource constraints are a critical consideration.

4. Limited Analysis of Hyperparameter Sensitivity

Weakness: The paper includes hyperparameters like the confidence threshold (β) and the regret coefficient (λ), but there is no detailed analysis of their impact on performance. Hyperparameter tuning is crucial for machine learning-based approaches, and an insufficient discussion of this aspect could make it challenging for practitioners to apply the framework effectively.

Suggestion: Conduct a sensitivity analysis of key hyperparameters (e.g., β, λ) to understand their influence on solution quality and efficiency. Providing guidelines on selecting appropriate values based on problem characteristics would improve the usability and robustness of the framework.

5. Lack of Robustness Analysis

Weakness: The robustness of the SHARP framework is not thoroughly evaluated, especially under varying problem types or noisy input data. Given the complexity of MILP problems and the use of learned models, SHARP's stability and reliability under different conditions should be assessed.

Suggestion: Include an evaluation of SHARP under different problem conditions, such as varying problem sizes, constraint tightness, or input noise. Adding experiments that illustrate how the performance of SHARP changes with different levels of problem difficulty or data quality would strengthen the paper's claims about its robustness and adaptability.

6. Missing Intuitive Explanation for Key Concepts

Weakness: The explanations for some of the key concepts, such as Sinkhorn normalization and the regret-greedy approach, are technically dense and may be challenging for readers who are less familiar with advanced optimization or graph-based ML methods.

Suggestion: Simplify or add intuitive examples to explain concepts like Sinkhorn normalization and the confidence threshold-based regret greedy search. This would improve accessibility, making the paper more approachable for a wider audience, including practitioners who may not be experts in graph-based learning methods.

7. Scalability Limitations in Industrial Scenarios

Weakness: The scalability of SHARP, while mentioned, is not extensively tested against large-scale industrial datasets beyond the benchmark problems considered. Moreover, the impact of increased computational costs due to EGAT's attention mechanisms on industrial-scale problems is not clearly addressed.

Suggestion: To make the contribution more convincing for real-world industrial applications, add experiments on larger, more complex datasets that resemble real-world MILP problems. Explicitly addressing the trade-offs between scalability and computational cost for attention mechanisms would clarify SHARP’s suitability for large-scale industrial use.

The following weaknesses stand out for me (again under the caveat mentioned in the Strengths section)

1. Limited Comparison with Recent MILP Solving Techniques - The paper compares SHARP primarily with traditional solvers like Gurobi and SCIP and a single machine learning-based approach (PaS). However, more recent methods in MILP solving, such as reinforcement learning or hybrid models integrating deep learning with heuristics, have not been considered.

2. Narrow Range of MILP Problems and Model Variants - The experiments are limited to only a few problem types (Combinatorial Auctions, Item Placement). Furthermore, the paper tests SHARP on a limited range of model sizes and problem complexities.

3. Sparse Analysis of Computational Overhead - The paper does not sufficiently address the computational cost of the SHARP framework, particularly the added complexity of SKEGAT and Sinkhorn normalization, which could potentially negate the performance gains in larger-scale settings. A more detailed analysis of SHARP’s computational overhead, including training and inference times compared to other ML-based solvers, would help readers assess its practical viability. Adding a discussion on how SHARP scales with larger datasets and graph sizes would also be beneficial.

4. Lack of Sensitivity Analysis on Hyperparameters - The paper presents fixed hyperparameter settings without exploring their sensitivity or impact on the model’s performance.

1. The authors acknowledge that their method is inspired by [1]; in fact, the proposed SHARP employs a nearly identical GNN framework to Light-MILPopt in [1]. Notably, both methods utilize EGAT and doubly stochastic normalization, with SHARP's sole distinction being the use of Sinkhorn normalization. However, I fail to see any fundamental difference between the two, as both appear capable of incorporating edge information into MILP modeling.

2. Although I was previously unfamiliar with ML-based MILP, I find it unreasonable that the authors draw extensively from the design of Light-MILPopt without (1) including it as a baseline or (2) thoroughly discussing the essential distinctions between the two.

3. The authors’ two core contributions include better usage of edge information, which seems to have already been addressed in [1], and the introduction of a post-hoc processing method, which, as acknowledged by the authors, largely derives from [2]. Thus, what exactly constitutes the authors' core contribution? It seems more akin to a combination of existing solutions.

Minor comments:

1. Line 151 explains the meaning of $W^l$, yet it does not appear in Eq. (3).
2. What does $\boldsymbol{a}^T$ represent in Eq. (4)?
3. The method in Algorithm 1 appears to be an existing algorithm; why is it included in the methodology section rather than the preliminary section?

[1] Light-MILPopt: Solving Large-scale Mixed Integer Linear Programs with Lightweight Optimizer and Small-scale Training Dataset

[2] Confidence Threshold Neural Diving

1. The evaluation is insufficient. Although the authors report metrics such as primal gap, survival rate, and primal integral, these do not directly illustrate the advantages of SKEGAT over GAT and GCN. The reported improvements may stem from the search module. At a minimum, an additional metric like "accuracy" should be included to demonstrate that SKEGAT yields more accurate predictions.

2. The modification from $\\sum\_{x\\in\\mathcal{X}\_0} x + \\sum_{x\\in\\mathcal{X}\_1} (1-x)\\leq \\Delta$ in [1] to the proposed $\\sum\_{x\\in\\mathcal{X}\_0} x + \\sum\_{x\\in\\mathcal{X}\_1} (1-x)\\leq \\lambda|\\mathcal{X}\_0\\cup\\mathcal{X}\_1|$ appears to be a straightforward normalization. The advantages and motivations for this change are not adequately justified.

3. There are quite a few writing issues that need to be addressed:

   • Incorrect statements:

     • The dimensions of matrix multiplications in lines 3-4 of Algorithm 1 do not match.
     • In line 257, should $**E**^k$ represent "the edge features of the $k$-th layer" instead of "$k$-th layer"?
     • The loss function in line 268 only works for problems with pure binary variables. An additional explanation for the continuous ones is needed.

   • Missing details:

     • What's the dimension of $\hat{**E**}$ in Section 2.3?
     • What properties does $**E**$ satisfy in line 144?
     • What's $W^l$ in line 151?
     • What's $a$ in equation (4)?

   • Typos:

     • Sinkhorn($\alpha^l$) -> Sinkhorn($\hat{\alpha}^l$) in equation (5)
     • $x*$ -> $x\^*$ in lines 310 and 312. Besides, please ensure its definition is introduced when first used.