A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability

Summary

The paper discusses the recent surge in using machine learning techniques for solving combinatorial optimization problems, particularly mixed-integer linear programs (MILPs). However, the limited availability of real-world instances often hinders optimal decision-making and unbiased solver assessments. To address this issue, the proposed solution is G2MILP, a deep generative framework for MILP instances. G2MILP represents MILP instances as bipartite graphs and employs a masked variational autoencoder to corrupt and replace parts of the graphs iteratively, generating new instances. This approach learns to generate realistic MILP instances without relying on expert-designed formulations, while preserving the structures and computational complexity of real-world datasets. The generated instances can assist in improving MILP solvers when data availability is limited. A set of benchmarks is designed to evaluate the quality of the generated MILP instances, and experimental results demonstrate their resemblance to real-world datasets in terms of both structure and computational difficulty.

Strengths

1. The paper takes a traditionally hard problem and proposes a novel solution to it. 2. Experiment results seem very compellingly, however the lack of good baseline makes hard to judge how good it actually is. 3. Presentation is good and clear.

Weaknesses

some minor issue might be lack of proper baseline, it's quite hard for the readers and reviewers to access how good this method actually is.

Questions

Is it possible to provide some "fair" comparisons on downstream proxy tasks with other popular methods? I must confess that I am not very familiar with the specific subdomain.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The authors propose a deep generative framework for MILP(mixed integer programs) instances. The work has applications in enhancing MILP solvers under limited data availability. MILP instances are represented as weighted bipartite graphs. The authors propose a masked variational autoencoder (VAE) method for graph generation. The problem is relevant and interesting. The experiments show that the proposed approach obtains significantly better results than existing methods.

Strengths

1. Important problem to tackle. The work has applications. 2. Paper is easy to understand. 3. The authors motivate different components of encoder decoder architecture nicely in the methodology section. 4. The experimental section consists of Structural similarity metrics, hardness comparison of generated MILP instances, application on downstream task. 5. Comparison on variety of datasets( MIS, Set cover, MIK(knapsack), including standard deviation, multiple runs. 6. Visualization of generated instances( through TSNE plots).

Weaknesses

1. Downstream Task( learning to solve MIP)- learning to branch etc. : Recently many neural MIP solvers have come up( Eg: -Gasse et al.[A]). The authors have also cited them. Is it possible for the authors to show whether they can improve the performance of such solvers by data augmentation( on any dataset) under low data availability. I agree the authors have shown improvement on predicting optimal value task. However, the above mentioned task is also important. It can make the paper stronger. 2. Presentation : Table 8 and Fig 2 not clear. Request the authors to add Standard deviation in Table 8 Appendix ( especially for Random). Also I see "Random" in Table 8 and not in Fig.2 ( Downstream task).. Also is there any difference between Table 8 and Fig 2? 3. Code is not provided by authors. [A] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact354 combinatorial optimization with graph convolutional neural networks. Advances in neural355 information processing systems, 32, 2019

Questions

Request the authors to answer the questions in weakness section. 1. Downstream task: Augmenting neural mip solvers with generated data. ( Especially under low data availability). 2. Presentation clarification( Fig 2 and Table 8).

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors have addressed it nicely.

Summary

The paper generates MIP instances with the help of VAEs. Experiment results show that the generated samples remain the characters of the training dataset from several aspects (e.g. the graph statistical value, the solving time of the generated samples, and the number of branching nodes of the generated samples), The evaluation shows that the generation helps the diversity, and preserves the difficulty. The samples may further help the NNs in downstream learning for MIP training, the authors introduces a task that predicts the optimal objective value, models trained on G2MILP shows obvious improvement on the testing dataset.

Strengths

The task is highly valuable. The idea of generating instances via deep neural networks is novel and sound. The whole framework provides an approach that generates new instances without the need to start form scratch. Experiment results prove the effectiveness of the proposed method across various datasets (MIS, MIK, set covering and a nurse scheduling problem from MIPLIB2017).

Weaknesses

N/A

Questions

In the experiment results, the ratio $\eta$ is controlled as $0.01, 0.05$ and $0.1$. At most only 10% of the nodes in the original V-C bipartite graph are changed. 1. Why doesn’t the generator set larger $\eta$ for a complete comparison? (As the other baselines may generate the instances from scratch.) From the table, the effectiveness of the method quickly drops as $\eta$ increases.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

As far as I could understand, the generator could only output the instances with the same problem scale.

Summary

The paper addresses the challenge of limited availability of real-world mixed-integer linear programs (MILPs) instances for machine learning techniques employed in combinatorial optimization problems. The scarcity of these instances often leads to sub-optimal decisions and biased solver assessments. Existing solutions either depend heavily on expert-designed formulations or fail to capture the intricate features of real-world instances. The authors propose G2MILP, the first deep generative framework for creating MILP instances. G2MILP treats MILP instances as bipartite graphs and uses a masked variational autoencoder to iteratively corrupt and replace parts of the original graphs, generating new ones. This approach allows G2MILP to learn to generate novel and realistic MILP instances without the need for expert-designed formulations, while simultaneously preserving the structures and computational hardness of real-world datasets. The generated instances can help improve MILP solvers when data availability is limited. The authors also present a set of benchmarks to evaluate the quality of the generated MILP instances. The experimental results show that G2MILP is capable of producing instances that closely mimic real-world datasets in terms of both structures and computational hardness.

Strengths

1. This is the first deep generative model for MILP instance generation based on the well known variant-constraint bipartite representation. 2. My favorite part of this work is the masking-based pre-training scheme, making me recall the masked language modeling objective in large language modeling. My feeling is that this direction could probably lead to large optimization model pre-training in the L2O field and this could be a very good start. 3. The empirical performance is good.

Weaknesses

1. I have the feeling that the problem similarity metric is too privileged for the proposed method, as it essentially modifies existing problem instances. 2. The effectiveness seems to drop quickly with higher ratio of variable/constraint alternations.

Questions

N/A

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

N/A

Summary

This paper is focused on using machine learning techniques to address combinatorial optimization problems, particularly mixed-integer linear programs (MILPs). Particularly, this paper proposed G2MILP, which is a generative model for generating realistic MILP instances. Without prior expert knowledge, G2MILP can generate expressive instances preserving computational hardness of real-world datasets. To achieve this, G2MILP adopts a masked VAE approach to iteratively mask original graphs to generate new ones. Extensive evaluations are made to demonstrate the effectiveness of the proposed approach. This paper shows how to adopt the well-established concepts (e.g., masked VAE) to the new data type (i.e., MILP instances).

Strengths

The main strength of this paper is its originality in my eyes. It introduces a generative framework for generating realistic MILP instances. Though different generative models have been established for various types of data, little attention is paid for using generative models to generate MILP instances for improving the solvers. To better develop training-based MILP solver, adequate training data is needed, and the proposed model can help.

Weaknesses

1. The contribution of the paper is unclear. Though the paper introduces a new research direction of generating MILP instances, its technical contributions are unclear. Representing MILP using bipartite graph and capturing features using GNN have been proposed by Gasse et al. The major technical contribution of this work is using masked VAE for expressive and realistic MILP instance generation, which I think is heuristic and lacks novelty. 2. The methodology is not easy to follow. Adopting the concept of masked VAE to generate expressive MILP instances seems a cute idea. But the masking process is confusing to me. 2.1. How do you generate the masked graph G_tilde? What is the distribution of p_tilde(G_tilde|G)? From lines 165-168, the masking is performed by randomly selecting a constraint vertex. Does this mean p_tilde(G_tilde|G) is just a uniform distribution or something like that? 2.2. What’s the intuition of making the masked graph as a conditional variable for the decoder? In masked VAE, the masked images are the input of the encoder. More explanations about the difference between the original masked VAE and the proposed pipeline for MILP instance generation are expected. 3. The evaluations are insufficient to fully validate the proposed framework. 3.1. There is a lack of ablation study to show that the masking scheme helps improve complex graph generation as claimed in lines 58 – 60. Though there are evaluations considering different masking ratios (0.01, 0.05, 0.1), they are insufficient to help understand the proposed masking scheme. Does the order of masking constraint vertices matter in the generation process? 3.2. What’s the reconstruction for each graph component (i.e., bias, degree, etc)? How the graph features affect the new instance generation (e.g., the density of the graph)? I guess the new instance generation will be harder if the original graph is dense and complex? 3.3. The downstream task evaluation is important to demonstrate the benefits of the proposed method. However, this evaluation is inadequate. What is the mask ratio for the downstream task evaluation (figure 2)? I guess the performance will decrease if the mask ratio is high? Can you report the std for performance improvement given different sets of 20 generated instances? What about the performance on larger datasets? To which extend (e.g., the scarcity of the original dataset), the generated instances help improve the performance? 4. The significance of the proposed method is unclear. Since the proposed method only mask constraint vertices, I think it is more like a graph generation pipeline. I am not fully convinced that we need to make this many efforts to generate new graphs. Furthermore, the benefits of new instances are not well demonstrated (as I question above). 5. Presentations can be improved. The position of Table 2 needs to be re-arranged. Notation wise, I think it is a bit confusing to use the same G for both the input and the output of the model. Typo: there are two ‘and’s in line 67.

Questions

I would like to adjust my rating if the authors can help clarify my confusions listed in the weakness section. Besides, I have other questions listed below: 1. Generating instances is not a new topic and G2SAT has explored this. Why it is non-trivial to adapt G2SAT to MILP instance generation? How does the consideration of the high-precision numerical prediction affect the design of the generative framework? 2. The generation of a new MILP instance is an iterative process. What is the computation cost for generating one MILP instance?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The limitations are discussed in the paper.

Summary

The paper proposed a deep generative framework G2MILP based on a masked variational autoencoder (VAE) for mixed-integer linear programs (MILP) instances. The proposed framework G2MILP corrupts and replaces constraints to generate new MILP instances while keeping the variables unchanged. Experiments show that G2MILP can produce instances that closely resemble real-world datasets in terms of both structures and computational hardness. Meanwhile, the generated instances from G2MILP can be used to augment the small training dataset to improve the prediction performance.

Strengths

1. The paper is well motivated by the limited data issue of MILP in the real world and the shortage of a flexible generative framework that can generate high-quality MILP instances. 2. The proposed decoder consisting of four predictive modules seems quite tailor-designed for the problem.

Weaknesses

1. The motivation of this work is similar to those Graph generation works and G2SAT, though targeting a different specific application domain. The main technique of masked VAE has already been well studied in the literature. So, this work is not that novel and interesting. 2. The proposed G2MILP can only modify the constraints of MILP beyond the training samples, which limits the contribution of this work. Although the authors claimed that their framework can be extended to change the variables of MILP, it is expected such flexibility can be achieved in this work. 3. Eq. (9) and Eq. (11) are inconsistent with Fig. 1. The logits/weights predictor shown in Fig. 1 is conditioned on $d_\tilde{v}$ but Eq. (9) and (11) are not. Moreover, from my understanding, the logits/weights prediction of $\delta_{\tilde{v}, u}$/$e_{u, \tilde{v}}$ should also be conditioned on $h_\tilde{v}$ and $z_{\tilde{v}}$. 4. The writing needs to be further improved. See the questions below.

Questions

1. How does G2MILP deal with different n and m? Different instances would have different n and m. 2. For the proposed normalization, would it be problematic when there is outlier in the dataset? 3. In Section 4.1, about structural distributional similarity, statistics that remain constant are excluded. Does it mean the similarity is only calculated in terms of the constraints? 4. For the Bowly baseline, can it change variables? If can, the similarity comparison may be unfair since the Bowly baseline introduces more diversity to the generated instances. 5. Good generation should introduce novelty compared to the training set, implying that the generated samples should differ from the training samples. So, it is tricky to use the structural distribution similarity to denote a good generation. I expect a discussion on this. t-SNE visualization for the baselines should be included.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors have discussed the limitations of their work, which however I think should be a part of this work (point 2 in the weakness).

Thank you. Increase score to Accept

I thank the authors for conducting additional experiments in a short duration of time.( Especiall the downstream task expt which shows the capability of the model). I am satisfied with the response to the question. I am increasing my score to accept. I hope the authors will release their code as promised( if the paper is accepted).

Thank you. Increasing my score.

I appreciate the authors' time and efforts in carefully responding to each of my questions. The significance of the proposed method is clarified. Lots of additional evaluations are conducted and they are helpful in further demonstrating the effectiveness of the proposed approach. Overall, I like the originality of this work as I stated in the Strengths section. Since my concerns and questions are all well addressed, I would love to increase my score.

Increasing score to accept

Thank you for your effort meticulously addressing other reviewers' comments and mine. After reading all the discussions above, I believe this work is significant and should be presented to the community. Hence raising the score to accept.

Concerns have not been fully resolved.

I appreciate authors’ efforts in addressing my concerns. However, they have not been fully resolved: 1. Beyond MAE developed in computer vision, I would more like to emphasize that masked auto-encoder has already explored widely in graphs, e.g., [1, 2, 3]. What I want to stress is that the mask idea for reconstruction/generation has been well explored in the community. In addition, there is also masked VAE in graphs [4]. While I acknowledge that there is some novelty in this work, a Taylor-designed masked VAE for a new specific application, I don't think the idea of the paper is that interesting or that new given the literature. 2. For weakness 3, I am confused what you explained. $p_\theta(\delta_{\hat{v}, u}|G, Z, d_\hat{v})$ in Fig. 1 describes the condition on $d_\hat{v}$, but Eq. (9) is not. 3. For question 1, how does G2MILP deal with different $n$ and $m$ of the inputs? For the output, from my understanding, G2MILP would need to deal with different $n$ and $m$ for different instances. If I am wrong, please correct me. 4. My question 3 indeed challenges the rationality of current structural similarity. Excluding the statistics of variables is unreasonable, as these statistics form a crucial part of MILP instances. This exclusion also leads to the inability to evaluate “v” models mentioned in Table 10. I think it is more reasonable to consider statistics of variables when calculating the structural similarity. References: [1] Hou, Z., Liu, X., Cen, Y., Dong, Y., Yang, H., Wang, C., & Tang, J. (2022, August). Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 594-604). [2] Tan, Q., Liu, N., Huang, X., Choi, S. H., Li, L., Chen, R., & Hu, X. (2023, February). S2GAE: Self-Supervised Graph Autoencoders are Generalizable Learners with Graph Masking. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining (pp. 787-795). [3] Tan, Q., Liu, N., Huang, X., Chen, R., Choi, S. H., & Hu, X. (2022). Mgae: Masked autoencoders for self-supervised learning on graphs. arXiv preprint arXiv:2201.02534. [4] Li, X., Ye, T., Shan, C., Li, D., & Gao, M. (2023, April). SeeGera: Self-supervised Semi-implicit Graph Variational Auto-encoders with Masking. In Proceedings of the ACM Web Conference 2023 (pp. 143-153).