MIPGen: Learning to Generate Scalable MIP Instances

We sincerely thank Reviewer yz8X for their positive feedback and valuable suggestions! We have corrected all the errors pointed out in the "Minor questions/comments" section. For the other issues, below we address every comment in detail:

1. In the experiment section, one of the main target should be to examine whether the generated MIP instances still preserve the combinatorial structure of MIS, CA, and MVC. The approaches you mentioned like MIP solver performance, graph statistics can give good estimation, but more importantly, is there any way to directly verify if the generated MIP instances are still also MIS, CA, or MVC? I believe that some auxiliary polynomial time algorithms can be given to check if a MIP instance is the MIP formulation of MVC (or MIS, CA). Then you can run the algorithm over all MIP instances, and report the percentage of generated instances that still preserve the exactly combinatorial structure of the benchmark problems.

Our MIPGen is currently based on a split-merge process framework. Throughout this process, no new variables or constraints are introduced, nor are new features generated. For the problem classes MIS, CA, and MVC, we can assure that the generated problems remain within their original categories. Taking the MIS problem as an example, the process of MIPGen generating new problems is akin to altering the positions of non-zero elements in the problem's coefficient matrix. For the original problem, this equates to redistributing the constraints of all vertices in the MIS problem graph.

Additionally, our current method for verifying the type of generated problems involves re-encoding these problems using the VGAE encoder and then re-clustering their encoded representations to confirm whether they belong to the same category as the original training problems. This approach is more universally applicable, as for other real-world MIP problems, not just standard benchmark problems, it is challenging to find a polynomial-time algorithm that can verify their category.

2. In table 3, here you are comparing the objective value of the best available solution within a fixed time limit. Have you tried comparing the solving time to reach optimality?

The reason for not providing complete solving times in our experimental data is due to the selection of benchmark problems like the MIS problem, which are NP-hard and cannot be optimally solved in a short time. In our trials using SCIP to solve MIS problems from our dataset (10,000 variables, 30,000 constraints), we did not obtain an optimal solution even after 24 hours. Therefore, we chose a relatively reasonable wall time of 1200s to compare the optimal gap and demonstrate the problem-solving difficulty.

3. Section 4.1.1. "Our experiment confirms that the generated MIP in stances have similar solving difficulty to the original input problem": I'm not sure about that. As far as I can see, the solving difficulty of the original input problem is not similar to the 100% version.

Thank you for the suggestion. In the newly submitted paper, we have revised the corresponding statement at section ^xx^ to "Our goal is to generate problem instances with similar solving difficulties as much as possible."

4. Section 4.1.1. "as the reconstruction percentage surges, more and more math structures in the problem are destroyed." Here you make the assumption that, more math structures will increase the solving difficulty of the MIP problem. However, this is not necessarily true. Adding constraints with random non-zero coefficients at every variable can also significantly increase the solving difficulty but it has no math structure as well.

Our conclusion is a preliminary one based on observations from the experimental results presented in the paper. Indeed, there are cases where solving difficulty increases without the generation of complex mathematical structures. We plan to further analyze and research this phenomenon in future work on other problems.

Thank you for your constructive comments and suggestions, which have greatly aided in enhancing the quality of our paper. We have diligently integrated your feedback into the revised manuscript. Below, we restate your comments and provide our detailed responses:

1. The technical novelty is somewhat limited. The key components are based on existing works, for example the random feat based method is from (Chen et al., 2022), the instance clustering is based on a simple EM procedure based on Gaussian Mixture Model, and the node splitting and merging is based on (You et al., 2019).

In response to your first comment, we have further elaborated on the novel aspects of our work. Building upon the foundational work in [2], we introduced a split-merge framework tailored for generating MIP problems. This framework is complemented by our innovative data augmentation experiments, designed to validate the efficacy of our method. Additionally, our method, MIPGen, uniquely incorporates the capability to amalgamate tree-like structures for generating large-scale MIP problems. This feature is particularly beneficial in training ML-based frameworks on smaller MIP instances to subsequently tackle larger-scale problems of the same type. We acknowledge the current framework's limitations and plan to explore more intricate generation strategies in our future work.

2. MIP instance clustering has already been studied in the literature, e.g., in [Kadioglu2010] and [Song2023]. These approaches can already effectively clustering heterogeneous MIP instances, and the techniques are much simpler than the proposed one. The authors did not give a proper discussion and comparison regarding existing MIP clustering methods.

Thank you for highlighting this issue.

The method for MIP instance clustering in [3] involves designing Instance Features for MIP problems, followed by clustering the normalized instance features using the g-means algorithm. The effectiveness of this approach heavily relies on the design of the Instance Features. The instance features in [3] include statistical indicators of MIP problems, such as the percentage of binary (integer or continuous) variables, a vector of coefficients of the objective function, and a vector representing the number of constraints for each variable ii. However, this method lacks a representation of the key structural aspect of the MIP problem's coefficient matrix. We believe that basic statistical indicators are insufficient to distinguish complex MIP problems encountered in the real world.

In [4], the method for MIP instance clustering begins with identifying a subgraph in the bipartite graph representing MIP problems using a random walk approach. The information of nodes and edges from this subgraph is then converted into a sequence $Y$, and an Auto Encoder is trained on these sequences $Y$ from all MIP problems, followed by clustering using the k-means algorithm based on the inferred features of each problem. In contrast, the clustering method in MIPGen directly employs a VGAE to train on the bipartite graphs representing MIP problems, followed by clustering with the EM algorithm. We consider the clustering method in MIPGen to be somewhat more streamlined than the method in [4]. Additionally, the experiments in [4] involved clustering four standard benchmark problems: Indset, Setcover, Cautions, and Facilities. Since these MIP benchmark problems have clear definitions and distinct differences, differentiating between them is relatively straightforward. The MIP instance clustering experiment in MIPGen utilizes the MIPLIB benchmark [6], which includes 240 complex, real-world MIP problems of significant research value. As the MIPLIB benchmark lacks an official classification, we validated whether MIPGen's clustering method could categorize problems from the MIPLIB benchmark with similar sources and descriptions into the same group. Furthermore, we have included visualizations of the intermediate results of clustering the MIPLIB benchmark in our paper. For details on the clustering experiments, please refer to Appendix B of our paper.

Moreover, [5] explores a method for computing similarities between MIP problems. It proposes representing MIP problems based on the structure of their coefficient matrices, depicting the positions of non-zero elements in these matrices as 640x480 black and white images. These feature images are then trained using a VAE, with the distance between the feature vectors of different problems output by the VAE representing their similarity. We believe that [5]'s method loses important information such as the MIP problem's RHS, optimization objective coefficients, and values of non-zero elements in the coefficient matrix. In contrast, the clustering method for MIP problems in MIPGen, which employs VGAE to directly represent the encoded bipartite graphs, is a straightforward and effective approach.

Thank you for your constructive comments and suggestions, which have greatly aided in enhancing the quality of our paper. We have diligently integrated your feedback into the revised manuscript. Below, we restate your comments and provide our detailed responses:

1. Limited evaluation: While the authors evaluate MIPGen on three standard MIP instances, they do not provide more specific examples of how MIPGen has been used to generate scalable MIP instances or the exact results of these experiments beyond what is mentioned in the paper.

The experiments for generating scalable MIP instances are detailed in Section 4.2 of the paper, where we demonstrate that the generated large-scale MIP problems present increased solving difficulty.

2. Lack of comparison: The authors do not compare MIPGen with other generative models for MIP instances, which limits the ability to assess its relative performance.

Thank you for your recommendation. We have now included a baseline comparison with the method outlined in [1]. Our model is compared against this baseline in terms of problem-solving difficulty, problem similarity, and data augmentation experiments. Please refer to Section 4.1.2 of the revised paper for further details.

3. Lack of implementation details: The paper does not provide detailed implementation information, which may make it difficult for others to replicate the results or build on the proposed framework.

The paper is currently under blind review. Upon acceptance, we plan to open-source our code.

4. What is the purpose of using the EM algorithm? Why not choose other clustering algorithms? The EM assumes the cluster is based on Mixture Gaussian, which may not be the real representation. How about the spectral clustering? How do you choose the number of clusters? How do you know the clustering result is perfect? What are your criteria?

Thank you for highlighting this issue. In MIPGen, the method for clustering MIP problems is divided into two stages: first, a Variational Graph Auto-Encoder is trained to extract feature representations of the MIP problems, followed by the use of the Expectation-Maximization algorithm to cluster these feature representations. We opted for the EM algorithm because its Gaussian Mixture Model is well-suited for adapting to clusters of complex shapes and is easily applicable to large datasets. Moreover, spectral clustering is quite sensitive to outliers in the input data. The MIPLIB benchmark, which includes a diverse range of real-world problem scenarios and varying scales, contains numerous outliers in its problem representations, thus making spectral clustering a less favorable option for us at this time.

The MIP instance clustering experiment in MIPGen uses the MIPLIB benchmark [2], comprising 240 complex, real-world MIP problems of significant research value. However, for a mixed set of training instances, it is not practical to assume that the value of 'k' (number of clusters) is pre-known. In our clustering experiment with MIPLIB, we set the number of clusters to 100, approximately corresponding to the types and number of problems in MIPLIB. As there is no official classification in the MIPLIB benchmark, we validated whether MIPGen's clustering method could categorize problems from the MIPLIB benchmark with similar sources and descriptions into the same group. Additionally, we have included visualizations of the intermediate results of clustering the MIPLIB benchmark in our paper. For more details on the clustering experiments, please refer to Appendix B of our paper.

5. It looks like 240 cases is a really small dataset for training deep neural networks. What is the hyperparameter for the VGAE model?

The dataset for clustering MIP problems comprises only 240 problems, as it utilizes the benchmark set from MIPLIB. The hyperparameters for our VGAE model are as follows:

6. It is not clear in the paper how algorithm 1 converts the bipartite graph into a tree structure.

Algorithm 1 converts the bipartite graph into a tree-like structure by selecting the node with the highest degree for node splitting. This process is repeated until the number of edges equals the number of nodes. We have also updated the pseudocode for Algorithm 1 in the paper to enhance clarity.

7. What is NNZ in Table 6

NNZ stands for 'Number of Non-Zero', referring to the count of non-zero elements in the coefficient matrix of the MIP problems.

Reference

[1] Bowly, S., Smith-Miles, K., Baatar, D., & Mittelmann, H. (2020). Generation techniques for linear programming instances with controllable properties. Mathematical Programming Computation, 12(3), 389-415.

[2] https://miplib.zib.de/tag_benchmark.html

Thank you for your constructive comments and suggestions, which have been exceedingly helpful in improving our paper. We have carefully incorporated them into the revised manuscript. Below, we restate your comments followed by our detailed responses:

1. The definition of graph modularity is not given and commonly used metrics for fidelity are not introduced.
2. Additionally, the experiments are not enough to verify the significance of MIPGen. First, only graph modularity may not be sufficient to gauge the graph fidelity and more metrics are necessary to ensure a comprehensive similarity comparison.

We appreciate your insightful suggestion! We have now included additional experiments focusing on problem similarity. Alongside the original structural evaluation metrics, we have introduced new metrics such as coefficient density, node degree distribution, and the distribution of LHS/RHS. These metrics further assess the similarity between newly generated and original problems. For detailed information, please refer to section 4.1.2 of the updated paper.

3. The infeasibility of instances are not well addressed.

Our paper's primary innovation lies in expanding the scale of generated problems. To achieve this objective, we implemented a split-merge strategy. While this approach, involving random splitting and merging, may lead to the creation of infeasible instances, it's noteworthy that all instances generated for this study were feasible. We recognize the potential for generating infeasible instances and intend to incorporate MILP duality in our future research to ensure the feasibility of generated problems. Additionally, it's important to note that infeasible problems can also be valuable. For instance, the MIPLIB benchmark includes several infeasible problems which require solvers to spend a considerable amount of time to determine their infeasibility. Your insightful advice is greatly appreciated.

4. Given the excerpt "As a lossless representation for MIP instances (Gasse et al., 2019), Bipartite Graph Representation (BGR) seamlessly transforms MIP instances into bipartite graphs...", can authors explain why the bipartite graph embedding in (Gasse et al., 2019) is lossless? Is there any proof for that?

The term "lossless" in this context means that the bipartite graph representation retains all information contained in a MIP problem. This representation is lossless because the nodes on each side of the bipartite graph encapsulate all information of the variables and constraints of the MIP problem, while the edges represent the coefficient matrix.

5. It is not clear what ML-based framework is used in experiments to evaluate the MIPGen and how it works.

As mentioned in section 4.1.3 of the paper, we utilized the framework described in [1] for our data augmentation experiments related to ML-based solutions.

6. The simple instance generation ought to be compared to underscore the effect of MIPGen. For example, simply fitting the degrees and parameters in instances into a distribution that may be already enough to generate new instances.

Thank you for your recommendation. We have included a baseline comparison with the method described in [3]. Our approach has been contrasted with this baseline in terms of problem-solving difficulty, problem similarity, and data augmentation experiments. For more details, please refer to section 4 of the updated paper.

Thank you for your constructive comments and suggestions, and they are exceedingly helpful for us to improve our paper. We have carefully incorporated them in the revised paper. In the following, your comments are first stated and then followed by our point-by-point responses.

1. The method is an application of existing SAT generation method into MIPs. The novelty design for MIPs is not sufficient.

Building upon the work in [2], we introduced the split-merge framework to the generation of MIP problems, complemented by data augmentation experiments to validate the efficacy of our method. Furthermore, MIPGen can amalgamate tree-like structures to generate larger-scale MIP problems. This enables the training of ML-based frameworks on smaller MIP problems to solve larger-scale problems of the same type. We plan to explore more complex generation strategies based on the split-merge framework in future work.

2. In the split-and-merge process, the constraints and variables features are not newly generated. So it is more appropriate for generating SATs instead of MIPs.
3. How to generate new node features and edge coefficients?

While our current method does not generate new features, it effectively rearranges the bipartite graph structure and splices tree-like structures. This approach perturbs the coefficient matrix and RHS of MIP problems while maintaining characteristics similar to the original problem, thus generating MIP problems akin to those being learned. We will consider the generation of new features in our subsequent work.

4. The considered graph statistics are only for structures, but not for coefficients. So the authors should consider new metrics for MIPs instead of SATs.

We appreciate your suggestion! We have added experiments on problem similarity. In addition to the original structural evaluation metrics, we have now employed additional metrics, including coefficient density, node degree distribution, distribution of LHS/RHS to assess the similarity between the newly generated and the original problems. We refer to section 4.1.2 of updated paper for detailed information.

5. The authors may want to add some baselines to demonstrate the effectiveness.

Thank you for your recommendation. We have included the baseline from [3] for comparison. Our method has been compared with this baseline in terms of problem-solving difficulty, problem similarity, and data augmentation experiments. Please refer to section 4 of the updated paper for more details.

6. A recent work [1], which appears in NeurIPS 2023, also uses deep learning to generate MIPs. So this paper is not the first one for this topic.

Acknowledging the work in [1], MIPGen is indeed not the first to use deep learning for generating MIP problems. However, it's important to note that this paper was released on ArXiv on 2023.10.4, which is after the ICLR submission deadline (2023.9.28). We have adjusted our statements accordingly in the revised paper.

7. Among the considered three datasets, MIS has all coefficients as 1, so it can be learned by the split-and-merge method like SAT problems. Do the other datasets have this characteristic?

The datasets we used, namely MIS, CA, and MVC, all have edge weights set to 1. Nevertheless, MIPGen is capable of handling problems with varying edge weights, as the edge weights in the bipartite graph are assigned corresponding coefficients. Additionally, the GNN model used by MIPGen is edge feature-aware.