DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming with Feasibility Guarantee

Thank you, Reviewer HSpe, for your valuable suggestions. We address your queries as follows:

1. Changing One Node at a Time: We appreciate your insightful suggestion. DIG-MILP currently supports iteratively selecting and altering a single node in the graph. However, we acknowledge that selecting and changing multiple nodes simultaneously might be an alternative and potentially effective approach, and we would leave this as a future work.

2. Feasible vs. Infeasible Instances: As mentioned in our universal response, we argue that given that almost all the existing scalable MILP datasets are feasible, it is naturally more interesting to generate feasible-bounded MILP instances. In real-world industrial applications, MILP problems modeled from real-world applications are usually feasible, or infeasible problems are transformed into feasible ones for solver application. Therefore, we argue that training models on feasible datasets to generate feasible MILP instances could be a justified approach.

3. JS-Divergence and Similarity Score: We use JS-divergence where a smaller value indicates higher similarity of two distributions. The similarity score is calculated in the way like (1 - JS divergence), implying that a larger score is preferable. Despite aiming for diversity in new data, it's crucial that the new MILP instances represent problem types similar to the original. This relevance ensures their practical utility in tasks like solver tuning and as augmentation in ML training. We measure such similarity to the original problem distribution by comparing various statistical metrics on graphs, leading to our comprehensive scoring metric that incorporates these diverse measures.

4. Training Data for CVS and IIS: The instances in MIPLIB2017 are of thousands of constraints and variables. In each training iteration, we sample a training batch by randomly choosing a node and delete it from the original bipartite graph, which leads to new training examples during the training process. Also for the downstream task, we train the model with the three original data with 20 newly generated instances by our model. We may consider larger datasets for further experiments.

We hope these responses clarify your concerns.

Thank you, Reviewer T4Ma, for your insightful questions. We address them as follows:

1. Difference and Improvement Over Paper [1]: As stated in our universal response, our work fundamentally differs from and is concurrent with [1]. We encourage you to refer to our universal response for a detailed explanation.
2. Clarification on Features in Table 1: The all 1’s and all 0’s denote the feature encoding in the first dimension of the node input feature. We use 1 and 0 to classify the variable node and constraint nodes from the bipartite graph.
3. Authenticity of Generated MILP Instances: We assert that feasible-bounded MILP instances are 'authentic’ because 1)most existing MILP datasets for training are feasible, and 2) MILP problems in industrial applications are typically feasible. Infeasible problems are generally transformed into feasible ones before being solved. Therefore, we believe training models on feasible datasets to generate feasible MILP instances is appropriate. Please refer to the universal response for more detailed explanation.
4. Legibility of Figures: Thank you for pointing out the issue with the font size in our figures. We will increase the font size to enhance readability in the revised manuscript. We appreciate your feedback and hope these responses clarify your concerns.

[1] Geng, Zijie, et al. "A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability." Neural Information Processing Systems (2023).

Thanks for the authors' response. However, my major concerns 3 and 5 have not been properly addressed.

1. (Concern 3 in weaknesses) I suggested that the authors explain the motivation of using the VAE model rather than the other generative models in detail. However, the authors replied that the choice of generative model is not the key of their work, which did not directly address my concern.
2. (Concern 5 in weaknesses) I suggested that the authors conduct three additional experiments, which are important for demonstrating the effectiveness of their proposed method. However, the authors did not provide these experiments.

Given the current status of my communication with the authors, I would keep my score.

We appreciate Reviewer KTFt's feedback and address the raised concerns as follows:

1. Technical Novelty is Incremental: We respectfully disagree with this assessment.Our paper is the first to apply a deep generative model for the generation of MILP instances with feasibility and boundedness guarantee. Please refer to the universal response for more details.
2. Clarity on Theoretical Derivations and Motivation for Using VAE: Our core contribution is to extract information from a well-designed generative space for producing new MILP examples with feasibility and boundedness guarantees. Theorem 1. in our paper provides theoretical backing for the guarantee, and the choice of generative model is not the key of our work. We acknowledge the reviewer's point about discussing our choice of generative model. Briefly, generating graphs from scratch, especially larger ones, might face complexity and scalability issues, hence our choice of VAE to modify parts of MILP examples iteratively. We will amend our paper to include comparisons with other models.
3. Comparison with Recent Work at NIPS [5]: Our work fundamentally differs from [5] and is concurrent, as detailed in our universal response.
4. Adequacy of Experiments: Thanks for your advice. We find most studies in the ML for MILP community focus on problems of a hundred variables to a thousand in size. Our experiments on two sizable MIPLIB datasets might sufficiently demonstrate the essence of our method. The downstream tasks suggested by the reviewer could they themselves be independent research branches and are far removed from the core issue we address. Furthermore, the framework of DIG-MILP supports general MILP generation, unlike G2SAT which works on stratification problems, making it unsuitable as a baseline in our context. We hope this adequately addresses the concerns and thank you for your valuable input.

Thank you, Reviewer NJds, for your detailed reading and suggestions on our paper. Below, we address the weaknesses raised by NJds:

1. Technical Novelty is Minor: We respectfully disagree with the reviewer’s assessment. Please refer to our universal response for clarification.
2. MILPs vs. IPs Clarification: Thank you for pointing this out. The short answer is yes, DIG-MILP supports generating MILP. It would only require training an additional classifier in the decoder to decide whether to round solution or slack variables into integers, which could then control whether the variables are discrete or continuous. When using DIG-MILP to solve IP instances, one could omit such classifiers. We will revise our manuscript to include such an explanation.
3. Feasibility of Generated MILPs: The short answer is the datasets do not contain infeasible MILPs. DIG-MILP indeed requires the training data with at least one set of solutions to generate feasible-bounded new instances. But we argue that such a requirement of training DIG-MILP solely on feasible datasets is both practical and appropriate. Please refer to universal response 3) for more detailed explanation.
4. Performance Compared to Random: We respectfully disagree with the reviewer’s argument. From the aspect of the structural similarity (15%-20% higher similarity score) and performance on the downstream tasks (10% higher Pearson correlation score in solver tuning and much lower MSE in ML model training), the performance of DIG-MILP is much better than the random baseline.
5. Hyper-configuration results: Hyper-configuration results can be inferred from the provided figures, where configurations resulting in shorter SCIP solving times on both original and generated data are preferred. Direct comparison of optimal hyper-configurations is challenging, because it may not be proper to evaluate the similarity of two sets of hyper-configurations by their distance directly on Euclidean space.
6. Optimal Value Prediction Task: Tackling the optimal value prediction task is a preliminary step in aiding MILP problems with ML models. We follow a general task setting introduced in [1]. Directly solving MILP is more challenging than predicting the optimal solution. In MILP generation task, one may first do well on the simpler task and then move towards more challenging tasks in the future work.

We hope this addresses your concerns and thank you once again for your valuable feedback.

[1] Chen et al. On the representation of solutions to elliptic pdes in barron spaces ICLR 2023.