ML4MILP: A Benchmark Dataset for Machine Learning-based Mixed-Integer Linear Programming

1. There could be potential in combining the structural and neural embedding metrics into a unified measure. Currently, these metrics seem to be more qualitative than quantitative, as shown in Figure 5 where cluster 6 has large distances in both metrics, but the other clusters show discrepancies (e.g., cluster 1 has a higher structural distance than cluster 3, yet a lower neural embedding distance). Merging these metrics might help address such inconsistencies and provide more comprehensive evaluations.

2. It would be valuable to identify classes that are neither too similar nor too different to facilitate benchmarking for transfer learning or other generalization approaches, which would broaden the dataset’s applicability.

3. In the baseline algorithm comparison, the quantified scores only consider solution gaps; including solving time as an additional metric would provide a more holistic assessment of algorithm performance.

The authors have used spectral clustering with euclidean distance as a measure for classification of the dataset instances. This choice of this approach needs to be substantiated better. Specifically the choice and implementation of the clustering method, including the choice of parameters and number of clusters needs to be provided. A discussion on the scalability of this method is also required.

The use of the phrase "ML-based algorithms" should be clarified. This is a very broad term and could be seen in multiple contexts based on the reader's domain of expertise. As such, it may be better to call out the scope clearly.

Details on the specific steps for computation of structural and neural embeddings should also be included. For example, is there a reference for (2), what happens in limiting cases? What is |I| ?

It is not clear how reclassification of the dataset leads to addressing issues such as loss leading to NaN values. More analysis is required to substantiate such a claim.

The repository link provided is not accessible, it returns a connection timeout error.

Limitations in the current and possible (specific) directions for future work should be included.

Some other aspects of the paper: The graph (Figs 6 and 7) legend has a typo for 'befor'. The horizontal axis labels are also missing. What is shown on the Y-axis - change in loss function values or absolute values? How do we interpret this? The tables could be made concise, especially when lot of the values in the tables are repetitive (Tables 10,11,12 for eg.)

The main weakness of this paper is the proper motivation and description of various choices in the benchmark structure. Specifically:

• (W1) It is not clear why homogeneity within classes is necessary for evaluation of ML based schemes
  • (W1.1) It is not clearly motivated why we need homogeneity? If we are comparing ML based methods to non-ML based methods (such as standard branch and bound), we would want to expose the ML as heterogenous training set as possible to be able to generalize well to unseen problems. Why are we changing / simplifying the problem setup to make sure the ML method works well (as shown in Figure 6 and 7 where the homogenization process makes training and generalization easier)? Can the authors provide empirical evidence or theoretical justification for why homogeneity is beneficial in this context, and how does homogeneity help or hurt the ability to generalize to heterogeneous problems?
  • (W1.2) To motivate homogeneity, it is also important to clarify what "distances" between problem instances signify. There is no discussion of any intuition as to what it means to have a pair of instances with small or large distance. If two instances are close, does training a ML model on one imply that we can solve the other one fast or to optimality (and if so, how much faster than a non-ML based solver or how much improved optimality)? If two instances are far apart, does that mean a ML model trained on one will not be able to even solve the other one? On a higher level, why is this metric expected to lead to higher homogeneity among problem instances within a "class" subset? Can the authors discuss the practical significance of these distances in terms of ML model performance and generalization, with any supporting results demonstrating how generalization is related to distances between instances.
  • (W1.3) Furthermore, if there is some notion of distance that implies generalization to unseen problem instances, it is not clearly motivated why the structure based or neural embedding based distances are the right metric.
  • (W1.4) Also, if the distance (whatever is reported in Table 1; it is not clear what the quantity is) is so low, of the order of $10^{-8}$, is there any difference in the embeddings of the instances? This seems like a case where the GNN oversmooths and all instances have effectively the same representation.
  • (W1.5) The "Embedding Distance" in equation (2) needs further clarification. Graph autoencoders allow us to generate a representation for each vertex or edge in the graph (Figure 4 seems to imply just vertices). However, how are these vertex/edge representations used to compute the "Distance" between two different instances $\mathcal{I}_i, \mathcal{I}_j$ since there might be different number of vertices, edges, etc. How are the vertex embeddings converted to a graph embedding? Can the author describe how the vertex/edge embeddings are aggregated into a single graph embedding? Furthermore, please consider discussing how the choice of aggregation can lead to really small pairwise distances of the order of $10^{-8}$ in W1.4.
  • (W1.6) If I read the appendix correctly, the numbers in Table 1 and Figure 5 are generated from samples from the libraries of MIP problems, and not the complete set of problems. So the "neural embedding distance" is dependent on the set of instances used to train the embedding networks, and thus can vary significantly based on the sample of instances selected (especially if the fraction of samples is very small). It is important to understand how robust this notion of learned embeddings/distances to the data/subsample used for learning (not to mention, the details of the graph autoencoder hyperparamters).
• (W2) It is not clear how the evaluations are set up based on the proposed benchmark, and it is not well motivated why this is the right way to benchmark ML based MILP solvers.
  • (W2.1) The evaluation in Tables 2 and 3 seem to show just one aspect of the setup, thus making the conclusions (such as how ML based schemes still underperform off-the-shelf solvers like Gurobi) somewhat limited in scope. One of the main motivation for introducing ML into the solution of MILP is to be able to solve similar problems quicker or equivalently get to a moderately strong solution fast which can then be used as a seed for off-the-shelf solvers. In that case, an evaluation that considers the time vs objective/gap tradeoff might be more useful as it will highlight the different regimes where ML based schemes would outperform or underperform off-the-shelf solvers. Since off-the-shelf solvers are generic algorithms (not to mention, with decades of research and engineering), they provide guaranteed performance given enough time. It is not clear how the time thresholds were selected for each problem class. In contrast, the mock evaluation shown in Figure 3 (bottom right) where we consider time vs performance tradeoff curves would be more informative than a single metric at some time threshold. The results such as in Tables 2 and 3 do not provide that level of information. Can the authors please include time vs. objective/gap tradeoff curves for each solver and problem class, similar to the mock evaluation in Figure 3. Alternately, can the authors please justify the choice of the specific time thresholds used in Tables 2 & 3, and discuss how these choices can change the conclusions drawn from the evaluations?
  • (W2.2) As with any learning based scheme, the performance will be heavily dependent on the size and quality of the training data, and the similarity or difference between the training and test data. The presented benchmark does not seem to say anything about the amount/quality of data available for training, and how the ML based schemes are trained for the purposes of the evaluation. Are they trained separately for each problem class? How does the size of the problem class (the number of instances available, the size of the individual instances) affect the relative performances of the different ML based schemes? All these factors will tell us more about when ML based schemes might work well, and the benchmark description and the result presentation does not properly address this.

Additional comments:

• (C1) It is not clear what is being said in section 3.1. On one hand, GNNs are claimed to be lossless encoders, on the other hand, the authors claim that GNNs are unable to model out-of-distribution or larger problems. But some larger models can handle that. The discussion is quite verbose, but it is not clear what are we computing the similiarities of and for what purpose?
• (C2) What does "represents the problem of scale being too large to accept the time to collect training samples" and "band training" in Table 2 caption mean?
• (C3) Table 1 needs more explanation. Are the different rows different "classes" of problems, with the "distances" measuring the pairwise (average?) distances between the instances in the class?
• (C4) Appendix C.3 does not seem to have the mentioned "Detailed classification results". It just states the classes for each MILP library. I did not see any training or validation curves for each of them, or the inter-class/intra-class distances. It would be good to point to the appropriate part of the paper.

While I can understand the motivation for having homogeneous instances within a class, heterogeneity also might be beneficial to illustrate generalization performance of solvers. I currently do not see this topic being much discussed in the paper.

Analyses of benchmark experiments is limited and only performed qualitatively based on raw numbers and visualizations. Maybe the authors could consider adding some statistical analyses on top of hypotheses so that they can illustrate an empirical workflow on the benchmark?

The presentation of the benchmarking results in Section 4.3 could be improved and more detailed. See also questions below.

The overall contribution (introduction of the benchmark and showing the lack of homogeneity of existing classes of instances of benchmarks based on similarity evaluation metrics with respect to structure and neural embedding distances) is somewhat limited in scientific insight and currently results in me having a hard time to vote for acceptance at a main ML and DL conference such as ICLR. Maybe submitting the paper to a Benchmark and Dataset track of a suitable conference might be more targeted?