A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability
Authors: Zijie Geng
Xijun Li
Jie Wang
Xiao Li
Yongdong Zhang
Feng Wu
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Learning to Optimize
Machine Learning for Combinatorial Optimization
Mixed-Integer Linear Programming
Graph Generation
TL;DR: We propose G2MILP, the first deep generative framework for mixed-integer linear program (MILP) instances, thus enhancing MILP solvers under limited data availability.

Abstract: In the past few years, there has been an explosive surge in the use of machine learning (ML) techniques to address combinatorial optimization (CO) problems, especially mixed-integer linear programs (MILPs). Despite the achievements, the limited availability of real-world instances often leads to sub-optimal decisions and biased solver assessments, which motivates a suite of synthetic MILP instance generation techniques. However, existing methods either rely heavily on expert-designed formulations or struggle to capture the rich features of real-world instances. To tackle this problem, we propose G2MILP, *the first* deep generative framework for MILP instances. Specifically, G2MILP represents MILP instances as bipartite graphs, and applies a masked variational autoencoder to iteratively corrupt and replace parts of the original graphs to generate new ones. The appealing feature of G2MILP is that it can learn to generate novel and realistic MILP instances without prior expert-designed formulations, while preserving the structures and computational hardness of real-world datasets, simultaneously. Thus the generated instances can facilitate downstream tasks for enhancing MILP solvers under limited data availability. We design a suite of benchmarks to evaluate the quality of the generated MILP instances. Experiments demonstrate that our method can produce instances that closely resemble real-world datasets in terms of both structures and computational hardness. The deliverables are released at [https://miralab-ustc.github.io/L2O-G2MILP](https://miralab-ustc.github.io/L2O-G2MILP).

A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability
Zijie Geng', Xijun Li!2, Jie Wang Xiao Li', Yongdong Zhang', Feng Wu Noah's 's Ark Lab, Huawei "Inttitute of Artificial Intelligence, Hefei Comprehensive National Science Center {ustegzj, lixi un, xiao 1il1111@mmall uste. edu. [jiewangx, zhyd73, fenggu) edu. cn
University of Science and Technology of China
Abstract
In the past few years, there has been explosive surge in the use of machine learning (ML) techniques to address combinatorial optimization (CO) problems, especially mixed-intege linear programs (MILPs). Despite the achievements, the limited availability of real-world instances often leads to sub-optimal deci- sions and biased solver assessments, which motivates suite of synthetic MILP instance generation techniques. However, existing methods either rely heavily on expert-designed formulations struggle capture the rich features of real-world instances. To tackle this problem, we propose G2MILP, the first deep generative framework for MILP instances. Specifically, G2MILP represents MILP instances as bipartite graphs, and applies a masked variational autoencoder to iteratively corrupt and replace parts of the original graphs generate new ones. The appeal- ing feature of G2MILP is that it can learn to generate novel and realistic MILP instances without prior tures and computational hardness of real-world datasets, simultaneously. Thus the generated instances can facilitate downstream tasks for enhancing MILP solvers under limited data availability. We design suite of benchmarks to evaluate the quality of the generated MILP instances. Experiments demonstrate that our method can produce instances that closely resemble real-world datasets in terms both structures and computational hardness. The deliverables are released https: http://mmaaaaaaaaaeeeeeae gi thub. 1o/:Lo--LLLLTTTE
formulations, while preserving the struc-
Introduction
Mixed-integer linear programming (MILP)-a powerful and versatile modeling technique for many real-world problems-lies at the core of combinatorial optimization (CO) research and widely adopted in various industrial optimization scenarios, such as scheduling [1]. planning [2], and portfolio [3]. While MILPs are Ahrhdard problems [4], machine learning (ML) techniques have recently emerged process [5, 6]. Notable successes include [7] for node selection, [8] for branching decision, and [9] for cut selection, etc.
powerful approach for either solving them directly assisting the solving
Despite the achievements, the limited availability real-world instances, due to labor-intensive data collection and proprietary issues, remains critical challenge to the research community [5, 10, 11]. Developing practical MILP solvers usually requires as many instances as possible to identify issues through white-box testing [12]. Moreover, machine learning methods for improving MILP solvers often suffer from sub-optimal decisions and biased assessments under limited data availability, thus
Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

compromising their generalization to unseen problems [13]. These challenges motivate suite of synthetic MILP instance generation techniques. which fall into two categories. Some methods rely heavily on expert-designed formulations for specific problems, such as Traveling Salesman Problems (TSPs) [14] or Set Covering problems [15]. However, these methods cannot cover real- world applications where domain-specific expertise or access to the combinatorial structures, due to proprietary issues, is limited. Other methods construct general MILP instances by sampling from an encoding space that controls few specific statistics [16]. However, these methods often struggle to capture the rich features and the underlying combinatorial structures, resulting in an unsatisfactory alignment with real-world instances.
Developing a deep learning (DL)-based MILP instance generator is a promising approach to address this challenge. Such a generator can actively learn from real-world instances and generate new ones without expert-designed formulations. The generated instances can simulate realistic scenarios, cover more cases, significantly enrich the datasets, and thereby enhance the development of MILP solvers at a relatively low cost. Moreover, this approach has promising technical prospects for understanding the problem space, searching for challenging cases, and learning representations, which we will discuss further in Section 5. While similar techniques have been widely studied for Boolean satisfiability (SAT) problems [17], the development of DL-based MILP instance generators remains a complete blank due to higher technical difficulties, i.e., it involves not only the intrinsic combinatorial structure preservation but also high-precision numerical prediction. This paper aims to lay the foundation for the development of such generators and further empower MILP solver development under limited data availability.
In this paper, we propose G2MILP, which is the first deep generative framework for MILP instances. We represent MILP instances as weighted bipartite graphs, where variables and constraints are vertices, and non-zero coefficients are edges. With this representation, we can use graph neural networks (GNNs) to effectively capture essential features of MILP instances [8, 18]. Using this representation, we recast the original task as graph generation problem. However, generating such complex graphs from scratch can be computationally expensive and may destroy the intrinsic combinatorial structures of the problems [19]. To address this issue, we propose a masked variational autoencoder (VAE) paradigm inspired by masked language models (MLM) [20, 21] and VAE theories [22-24]. The proposed paradigm iteratively corrppts and replaces parts of the original graphs using sampled latent vectors. This approach allows for controlling the degree to which we change the original instances, thus balancing the novelty and the preservation of structures and hardness of the generated instances. To implement the complicated generation steps, we design decoder consisting of four modules that work cooperatively to determine multiple components of new instances, involving both structure and numerical prediction tasks simultaneously.
We then design a suite of benchmarks to evaluate the quality of generated MILP instances. First, measure the structural distributional similarity between the generated samples and the input training instances using multiple structural statistics. Second, we solve the instances using the advanced solver Gurobi [12], and we report the solving time and the numbers of branching nodes of the instances, which directly indicate their computational hardness [19, 25). Our experiments demonstrate that G2MILP is the very first method capable of generating instances that closely resemble the training sets in terms of both structures and computational hardness. Furthermore, we show that G2MILP is able to adjust the trade-off between the novelty and the preservation of structures and hardness of the generated instances. Third, we conduct a downstream task, the optimal value prediction task, to demonstrate the potential of generated instances in enhancing MILP solvers. The results show that using the generated instances to enrich the training sets reduces the prediction error by over 20% on several datasets. The deliverables are released at https://miralab-uee ceiitt..ittu...... Cetchub.i//Lan 1o/L20 1t////220-2210 G2MILP.
Related Work
Machine Learning for MILP Machine learning (ML) techniques, due to its capability of capturing rich features from data, has shown impressive potential in addressing combinatorial optimization (CO) problems [26-28], especially MILP problems [5]. Some works apply ML models to directly predict the solutions for MILPss [29-31]. Others attempt to incorporate ML models into heuristic components in modern solvers [7, 9, 32, 33]. Gasse et al. [8] proposed to represent MIIP instances as bipartite graphs, and use graph neural networks (GNNs) to capture features for branching decisions. Our

---

proposed generative framework can produce novel instances to enrich the datasets, which promises to enhance the existing ML methods that require large amounts of i.id. training data.
MILP Instance Generation Many previous works have made efforts to generate synthetic MILP instances for developing and testing solvers. Existing methods fall into two categories. The first category focuses on using mathematical formulations to generate instances for specific combinatorial optimization problems such as TSP [14], set covering [15], and mixed-integer knapsack [34]. The second category aims to generate general MILP instances. Bowly [16] proposed a framework to generate feasible and bounded MILP instances by sampling from an encoding space that controls few specific statistics, c.g., density, node degrees, and coefficient mean. However, the aforementioned methods either rely heavily on expert-designed formulations or struggle to capture the rich features of real-world instances. G2MILP tackles these two issues simultaneously by employing deep learning techniques to actively generate instances that resemble real-world problems, and provides versatile solution to the data limitation challenge. In [35], we further extend G2MILP to learn to generate challenging MILP instance.
Deep Graph Generation A plethora of literature has investigated deep learning models for graph generation [36], including auto-regressive methods [37], varational autoencoders (VAEs) [23]. and generative diffusion models [38]. These models have been widely used in various fields [39] such as molecule design [21, 40, 41] and social network generation [42, 43]. G2SAT [17], the first deep learning method for SAT instance generation, has received much research attention [19, 44].
Nevertheless, non-trivial to adopt G2SAT to MILP instance generation (see Appendix C.1), as G2SAT does not consider the high-precision numerical prediction, which is one of the fundamental challenges MILP instance generation. In this paper, we propose G2MILP- first deep generative framework designed for general MILP instances- and we hope to open up new research direction for the research community.
3 Methodology
In this section, we present our G2MILP framework, First, in Section 3.1, we describe the approach to representing MILP instances bipartite graphs. Then, in Section 3.2, we derive the masked variational autoencoder (VAE) generative paradigm. In Section 3.3, we provide details on the implementation of the model framework. Finally, in Section 3.4, we explain the training and inference processes. The model overview is in Figure 1. More implementation details can be found in Appendix A. The code released at httpp//u///ttttt..//e otg.au....o//HRRRaaa--ot/////000
3.1 Data Representation
A mixed-linear programming (MILP) problem takes the form of:
min c xx ZER
s.t. Ax b, = 2
(I)
where R", A E Rmxn, RT, (R ( I C 21,2, ,n. includes those indices j where z, is constrained to an integer.
(R U {+x0))", and the index set
To represent each MILP instance, we construct weighted bipartite graph G = (V U W, as follows [18, 29].
The constraint vertex set V fv..... Um). where each e; corresponds to the ,th constraint in Equation 1. The vertex feature v; of es is described by the bias term, i.e., v; = (b,).
The variable vertex set W = {w),". ... wn), where each wj corresponds the ,hh vari- able in Equation 1. The vertex feature wy of wy is a 9-dimensional vector that contains information of the objective coefficient cj. the variable type, and the bounds L,, Un-
The edge set ع {eiz) ). where an edge eij connects constraint vertex ;; E V and a variable vertex W/ E W. The edge feature eij is described by the coefficient, i.e., Cij = (azy), and there is no edge between v; and wy if azy = 0.
As described above, each MILP instance is represented as a weighted bipartite graph, equipped with tuple of feature matrices (V, W, E), where V, W, E denote stacks of vertex features 2. w, and
3

---

(b) Encoder 9 (Z19)
Blas Predictor
W1
Zur
Po (boll
Ps
Fux
g
W2
G +
MLP
Zun
Mp
@ Degrce Predictor pa(dpl5.2)
Zuf
Σ
constraints
variables
Z
MLP
ho
Masking
P(119)
Process
constraints
variables
(c) Decoder Po(9IG.2) Z)
Logits Predictor Po Polopul do))
[nask]
[mask]
Paryy
MLP logits
8pn
@pam
g
W2
Pawyy
GNN
@ Weights Predictor Poleo Z. MLP MLPWelghtt
by
F'
Beyss {
Wm
Figure 1: Overview of G2MILP. (a) Masking Process G) Given a MILP instance, which is represented bipartite graph G. randomly label constraint vertex i as [mask] to obtain the masked graph G. (b) Encoder g [Z] The encoder is GNN followed by two networks, Hs and Eg. for resampling. During training, we use the encoder to obtain the latent vectors žv, and zuy for all vertices. (c) Decoder po (G Z). We use GNN to obtain the node features h3 and hw,, Then four modules work cooperatively to reconstruct the original graph G based on the node features and the latent vectors. They sequentially determine @ the bias terms, @ the degrees, @ the logits, and @ the weights. During inference, the model is decoder-only. and we draw the latent vectors from a standard Guassian distribution introduce randomness. We repeat the above mask-and-genas generate process several times so as to produce new instances.
edge features e,j. respectively. Such a representation contains all information of the original MILP instance [18]. We use the off-the-sheef observation function provided by Ecole [45] to build the bipartite graphs from MILP instances. We then apply graph neural network (GNN) to obtain the node representations hg, and h also denoted as h., and hw, for simplicity. More details on the data representation can be found in Appendix A.I.
3.2 Masked VAE Paradigm
We then introduce our proposed masked VAE paradigm. For the case of understanding, provide an intuitive explanation here, and delay the mathematical derivation to Appendix A.2.
Given a graph G drawn from a dataset D, we corrupt it through a masking process, denoted by Č ~ و g). We aim to build a parameterized generator pe (GIG) that can generate new instances ς from the corrupted graph G. We train the generator by maximizing the log- log-likel log pe (G)g) log Po Glğ) of reconstructing & given G. Therefore, the optimization objective is:
arg max Eg log (ggg))
(2)
To model the randomnesss in the generation process and produce diverse instances, we follow the standard VAE framework [22, 23] to introduce latent variable Z = (Zey.... Ze.. Zwy Zw, **. Zw., )
which contains the latent vectors for all vertices. During training. the latent vectors are sampled from posterior distribution given by parameterized encoder ds. while during inference, they are independently sampled from prior distribution such as a standard Gaussian distribution. The decoder Po the masked VAE framework generates new instances from the masked graph ğ together with the sampled latent variable Z.

---

The evidence lower bound (ELBO), also known as the variational lower bound, is a lower bound estimator of the oo-lieelihood, and is what we actually optimize during training, because it is more tractable. We can derive the ELBO as:
(9|g, 2)] - Dxr. 99 (2 Po (Z)], log Po (g 2 (Z(7) lo
(3)
where po po(Z) is the prior distribution of Z and is usually taken the standard Gaussian (0, I), and DRL| [|]]] denotes the KL. divergence. Therefore, we formulate the loss function as:
C C= BGG
Ez Ez (2|0)
log pe (G Z) +B DKL [g (Z9
(4)
Cyex
Lix
In the formula: (1) the first term Lie the reconstruction loss, which urges the decoder to rebuild the input data according to the masked data and the latent variables. (2) The second term Epeice is used to regularize the posterior distribution in the latent space to approach standard Gaussian distribution, so that we can sample Z from the distribution when inference. (3) 8 is hyperparameter to control the weight of regularization, which critical in training a VAE model [46].
3.3 Model Implementation
To implement Equation 4, we need to instantiate the masking process p(ğlg), the encoder 9s (Zl9). and the decoder po ( Z), respectively.
Masking Process For simplicity, we uniformly sample a constraint vertex UVV) and mask it and its adjacent edges, while keeping the variable vertices unchanged. Specifically, we label the vertex i with special [mask]] token, and add virtual edges that link with each variable vertex. The vertex Ö and the virtual edges are assigned special embeddings to distinguish them from the others. We further discuss on the masking scheme in Appendix C.2.
Encoder
The encoder (Z)))) is implemented as:
4s (Zg)==
II g (2) (s(zu19) = (HH exp Es Eh
(5)
=EVUW
where Jy is the node representation of obtained by GNN .V denotes the Gaussian distribution, and μ and E output the mean and the log variance, respectively.
Decoder The decode Po aims to reconstruct G during training. We apply a GNN, to obtain the node representations h denoted as h. for simplicity. To rebuild the masked constraint vertex 0, the decoder sequentially determines: @ the bias by (i.e., the right-hand side of the constraint), @ the degree da of ö (i.e., the number of variables involved in the constraint), @ the logits 85,. for all variable vertices to indicate whether they are connected with (i.e., whether the variables are in the constraint), and @ the weights e of the edges (i.e., the coefficients of the variables in the constraint). The decoder is then formulated as:
Po ( Z) = (p Z) po (d Z)
II ( Z NEW
II WE NEW:de..=1
po(er,.. (9, Z). (6)
Therefore, we implement the decoder as four cooperative modules: Bias Predictor, @ Degree Predictor, 3 Logits Predictor, and 4 Weights Predictor.
① Bias Predictor For effective prediction, we incorporate the prior of simple statistics of the dataset-the minimum b and the maximum 5 of the bias terms that occur in the dataset- into the predictor. Specifically, we normalize the bias ba to [o, 1] via b = (bg b) b). To predict by. use MLP that takes the node representation h and the latent vector 2; of inputs:
b a Diappiinhhhs =+l))=
where (r) is the sigmoid function used to restrict the outputs. We use the mean squared error (MSE) loss to train the predictor. At inference time, apply the inverse transformation to obtain the
predicted bias values: by b + (b 8g.!!
Notattion-win wise, & to denote the predicted variable in & that corresponds æ in
5

---

@ Degree Predictor We find that the constraint degrees are crucial to the graph structures and significantly affect the combinatorial properties. Therefore, we use the Degree Predictor determine coarse-grained degree structure, and then use the Logits Predictor to determine the fine-grained connection details. Similarly to Bias Predictor, we normalize the degree de to dū = (d; / - d). where d and d are the minimum and maximum degrees in the dataset, respectively. We use one MLP to predict d.
di = (MLP (he, (Ibe,z))) zel)).
We use MSE loss for training, and round the predicted degree to the nearest integer d; for inference.
@ Logits Predictor To predict the logits da,u indicating whether variable vertex E W is connected with i, we use one MLP that takes the representation hy and the latent vector 2y of u as inputs:
_,, = a (MLP ((h., (allz
We binary cross-entropy (BCE) loss train the logistical regression module. As positive samples (i.e., variables connected with a constraint) are often scarce, we use one negative sample for each positive sample during training. The loss function is:
Ligiis = - (E,,a) loog (6%..) (( [log (1
k/,
(10)
where Ppos and Pneg denote the distributions over positive and negative samples, respectively. At inference time, connect di variable vertices with the top logits ü., i.e.,
8, [ 1, u E arg TopK ( W),ds),
(11)
0, otherwise.
Weights Predictor Finally, we use one MLP to predict the normalized weights c for nodes that are connected with ē:
,, a (MLP ([hus =ull)
(12)
The training and inference procedures are similar to those of Bias Predictor.
3.4 Training and Inference
During training, we use the original graph G to provide supervision signals for the decoder, guiding to reconstruct G from the masked & and the encoded Z. As described above, the decoder involves four modules, each optimized by prediction task. The first term in Equation 4, i.c., the reconstruction loss, is written as
Lre
Σ a; ((..
(13)
where (0, (19.9) (1 1, 4) are loss functions for the four prediction tasks, respectively, and Og hyperparameters.
During inference, we discard the encoder and sample from a standard Gaussian distribution, which introduces randomness to enable the model to generate novel instances. We iteratively mask one constraint vertex in the bipartite graph and replace with a generated one. We define hyperparameter 17 to adjust the ratio of iterations to the number of constraints, i.c., Niters 17 [V]. Naturally, larger value of 1) results in instances that are more novel, while a smaller value of 1 yiclds instances that exhibit better similarity to the training set. For further details of training and inference procedures, please refer to Appendix A.3.
Experiments
4.1 Setup
We conduct extensive experiments to demonstrate the effectiveness of our model. More experimental details can be found in Appendix B. Additional results are in Appendix C.

---

Benchmarking To evaluate the quality of the generated MILP instances, we design three bench- marks so as to answer the following research questions. (1) How well can the generated instances preserve the graph structures of the training set? (2) How closely do the generated instances resemble the computational hardness of real-world instances? (3) How effectively do they facilitate downstream tasks to improve solver performance?
I. Structural Distributional Similarity We consider 11 classical statistics to represent features of the instances [17, 47], including coefficient density, node degrees, graph clustering, graph modularity, etc. In line with widely used graph generation benchmark [48], we compute the Jensen-Shannon (IS) divergence [49] for each statistic to measure the distributional similarity between the generated instances and the training set. We then standardize the metrics into similarity scores that range from 0 to 1. The computing details can be found in Appendix B.3.
II Computational Hardness The computational hardness is another critical metric to assess the quality of the generated instances. We draw an analogy from the SAT generation community, where though many progresses achieved, it is widely acknowledged that the generated SAT instances differs significantly from real-world ones in the computational hardness [25], and this issue remains inadequately addressed. In our work, make efforts mitigate this problem, even in the context of MILP generation, a more challenging task. To this end, we leverage the state-of-the-a solver Gurobi [12] to solve the instances, and report the solving time and the numhers of branching nodes during the solving process, which can directly reflect the computational hardness of instances [19].
III. Downstream Task We consider two downstream tasks to examine the the potential benefits of the generated instances in practical applications. We employ G2MILP to generate new instances and augment the original datasets, and then evaluate whether the enriched datasets can improve the performance of the downstream tasks. The considered tasks include predicting the optimal values of the MILP problem, as discussed in Chen et al. [18], and applying peedict-and-searee framework for solving MILPs, as proposed by Han et al. [31].
Datasets We consider four different datasets of various sizes. (1) Large datasets. We evaluate the model's capability of learning data distributions using two well-known synthetic MILP datasets: Maximum Independent Set (MIS) [50] and Set Covering [15]. We follow previous works [8, 9] to artificially generate 1000 instances for each of them. (2) Medium dataset. Mixed-integer Knapsack (MIK) is a widely used dataset [34], which consists of 80 training instances and 10 test instances. We use this dataset to evaluate the model's performance both on the distribution learning benchmarks and the downstream task. (3) Small dataset. We construct small subset of MIPLIB 2017 [10] by collecting a group of problems called Nurse Scheduling problems. This dataset comes from real-world scenarios and consists of only 4 instances, 2 for training and 2 for test, respectively. Since the statistics are meaningless for such an extremely small dataset, we use it only to demonstrate the effectiveness of generated instances in facilitating downstream tasks.
Baselines G2MILP is the first deep learning generative framework for MILP isntances, and thus, we do not have any learning- based models for comparison purpose. Therefore, we compare G2MILP with a heuristic MILP instance generator, namely Bowly [16]. Bowly can create feasible and bounded MILP instances while controlling some specific statistical features such as coefficient density and coefficient mean. We set all the controllable parameters to match the corresponding statistics of the training set, allowing Bowly to imitate the training set to some extent. We also consider useful baseline, namely Random, to demonstrate the effectiveness of deep neural networks in G2MILP. Random employs the same generation procedure as G2MILP, but replaces all neural networks in the decoder with random generators. We set the masking ratio v) for Random and G2MILP to 0.01, 0.05, and 0.1 to show how this hyperparameter helps balance the novelty and similarity.
4.2 Quantitative Results
Table 1:
Structural similarity scores be- tween each pair of datasets. Higher is better.
I. Structural Distributional Similarity We present the structural distributional similarity scores between each pair of datasets in Table 1. The results indicate that our designed metric is reasonable in the sense that datasets obtain high scores with themselves and low
MIS
SetCover
MIK
MIS SetCover MIK
0.998
0.182
0.042
1.000
0.128
0.997
7

---

Table 3: Average solving time (s) of instances solved by Gurobi (mean + std). is the masking ratio. Numbers in the parentheses are relative errors with respect to the training sets (lower better).
MIS
SetCover
MIK
Training Set
0.349 + 0.05
2.344 0.13
0.198 0.04
Bowly
0.007: 0.00 (97.9%)
0.048 0.00 (97.9%)
0.001 0.00 (99.8%)
Random
0.311 0.05 (10.8%)
2.044 0.19 (12.8%)
0.008 0.00 (96.19% 1%)
17 0.01
G2MILP
0.354:: 0.06 (1.5%)
2.360 0.18 (0.8%)
0.169:: 0.07 (14.7 %)
Random
0.569 0.09 (63.0%)
2.010 0.11 (14.3%)
0.004 0.00 (97.9%)
77 0.05
G2MILP
0.292 0.07 (16.3%) ))
2.533: 0.15 (811 %)
0.129 0.05 (35.1 %)
Random 2.367 0.35 (578.2%)
1.988 0.17 (15.2%)
0.005 0.00 (97.6%)
0.1
G2MILP
0.214 0.05 (38.7%)
2.108 0.21 (10.0%)
0.072:1 0.02 (63.9 %)
Table 4: Average numbers of branching nodes of instances solved by Gurobi. is the masking ratio. Numbers in the parentheses are relative errors with respect to the training sets (lower is better).
MIS
SetCover
MIK
Training Set
16.09
838.56
175.35
Bowly
0.00 (100.0%)
0.00 (100.0%)
0.00 (100.0%)
Random
20.60 (28.1%)
838.51 (0.0%)
0.81 (99.5%)
17 = 0.01
G2MILP
15.03 (6.6%)
876.09 (4.4%)
262.25 (14.7 %)
Random
76.22 (373.7%)
765.30 (8.7%)
0.00 (100%)
17 0.05
G2MILP
10.58 (34.2%) %)
874.46 (4.3%)
235.35 (34.2%) %)
Random
484.47 (291 (2911.2%)
731.14 (12.8%)
0.00 (100%)
1) = 0.1
G2MILP
4.61 (71.3 ))
876.92 (4.6%) 140.06 (20.1 1))
scores with different domains. Table 2 shows the similarity scores between generated instances and the corresponding training sets. We gener- ate 1000 instances for each dataset to compute the similarity scores. The results suggest that G2MILP closely fits the data distribution, while Bowly, which relies on heuristic rules to control the statistical features, falls short of our expec- tations. Furthermore, we observe that G2MILP outperforms Random, indicating that deep learn- ing contributes the model's 's performance. As expected, a higher masking ratio results in gen- erating more novel instances but reduces their similarity to the training sets.
Table 2: Structural distributional similarity scores between the generated instances with the training datasets. Higher is better. rj is the masking ratio. We do not report the results of Bowly on MIK because Ecole [45] and SCIP [51] fail to read the generated instances due to large numerical values.
MIS
SetCover
MIK
Bowly
0.184
0.197
Random
0.651
0.735
0.969
0.01
G2MILP 0.997
0.835
0.991
Random 0.580
0.613
0.840
" 0.05
G2MILP 0.940
0.782
0.953
Random
0.512
0.556
0.700
II. Computational Hardness We report the average solving time and numbers of branching nodes in Table 3 and Table 4, respectively. The results indicate that instances generated by Bowly are relatively easy, and the hardness of those generated by Random is inconclusive. In contrast, G2MILP is capable of preserving the computational hardness of the original training sets. Notably, even without imposing rules to guarantee the feasibility and boundedness of generated instances, G2MILP automatically learns from the data and produces feasible and bounded instances.
17 = 0.1
G2MILP
0.895
0.782
0.918
III. Downstream Task First, we follow Chen et al. [18] to construct GNN model for predicting the optimal values of MILP problems. We train a predictive GNN model on the training set. After that, we employ 20 generated instances to augment the training data, and then train another predictive
8

---

MIK
Nurse Scheduling
1007
100%
1.0
80%
5006
0.8
0.8
Delative MSE
600%
Relative MSB
600
Improvvmeen
0.6
0.6
-00%
40%
0.4
20%
20%
0%%
0.2
0%
0.0 Training Ses
Rondlom
C2MILP
-20%
0.0
Training Set
Rowly
G2MILP
-20%
Figure 2: Results of the optimal value prediction task. Bars indicate the relative MSE the model trained on the original training sets, and lines represent the relative performance improvement.
Trining
O2MILP (p 0.01)
0.1)
Thaising Ses GZMILP
Figure 3: The t-SNE visualization of MILP instance representations for MIK. Each point represents an instance. Red points are from the training set and blue points are instances generated by G2MILP.
model using the enriched dataset. We use the prediction mean squared error (MSE) to assess the resulting models, and we present the MSE relative the default model trained on the original training sets in Figure 2. For the MIK dataset, instances generated by Bowly introduce numerical issues so that Ecole and SCIP fail to read them. For the Nurse Scheduling dataset, Random fails to generate feasible instances. Notably, G2MILP the only method that demonstrates performance improvement on both datasets, reducing the MSE by 73.7% and 24.3%, respectively. The detailed results in Table 8 in Appendix B.4. Then, we conduct experiments on the neural solver, i.e., the predict-and-seare framework proposed by Han al. [31], which employs model predict solution and then solvers to search for the optimal solutions in trust region. The results are in Table 9 in Appendix B.4.
4.3 Analysis
Masking Process We conduct extensive comparative experiments on different implementations of the masking process. First, implement different versions of G2MILP, which enable us mask and modify either constraints, variables, or both. Second, we investigate different orders masking constraints, including uniformly sampling and sampling according to the vertex indices. Third, analyze the effect of the masking ratio on similarity scores and downstream task performance improvements. The experimental results are in Appendix C.2.
Size of Dataset We conduct experiments on different sizes of the original datasets and different ratio of generated instances to original ones on MIS. Results are in Table 15 in Appendix C.4. The results show that G2MILP yields performance improvements across datasets of varying sizes.
Visualization We visualize the instance representations for MIK in Figure Specifically, we use the G2MILP encoder to obtain the instance representations, and then apply t-SNE dimensionality reduction [52] for visualization. We observe that the generated instances, while closely resembling the training set, contribute to broader and more continuous exploration of the problem space, thereby enhancing model robustness and generalization. Additionally, by increasing the masking ratio ?/. we can effectively explore a wider problem space beyond the confines of the training sets. For comparison with the baseline, we present the visualization of instances generated by Random in Figure in Appendix C.5.

---

Limitations, Future Avenues, and Conclusions
Limitations In this paper, we develop G2MILP by iteratively corrupting and replacing the con- straints vertices. We also investigate different implementations of the masking process. However, more versatile masking schemes should be explored. Moreover, employing more sophisticated designs would enable to control critical properties such feasibility of the instances. We intend to develop a more versatile and powerful generator in our future work.
Future Avenues We open up new avenues for research on DL-based MILP instance generative models. In addition to producing new instances to enrich the datasets, this research has many other promising technical implications [35]. (1) Such a generator will assist researchers to gain insights into different data domains and the explored space of MILP instances. (2) Based on generative model, we can establish an adversarial framework, where the generator aims to identify challenging cases for the solver, thus automatically enhancing the solver's ability handle complex scenarios. (3) Training generative model involves learning the data distribution and deriving representations through unsupervised learning. Consequently, it is possible to develop pre-trained model based generative model, which can benefit downstream tasks across various domains. We believe that this paper serves an entrance for the aforementioned routes, and we expect further efforts in this field.
Conclusions In this paper, propose G2MILP, which to the best of our knowledge is the first deep generative framework for MILP instances. It can learn to generate MILP instances without prior expert-designed formulations, while preserving the structures and computational hardness, simultaneously. Thus the generated instances can enhance MILP solvers under limited data availability, This work opens up new avenues for research DL-based MILP instance generative models.
Acknowledgements
The authors would like to thank all the anonymous reviewers for their insightful comments. This work was supported in part by National Key R&D Program of China under contract 20227D01 19801, National Nature Science Foundations of China grants U19B2026, U19B2044, 61836011, 62021001, and 61836006.
References
[1] John A Muckstadt and Richard Wilson. An application mixed-integer programming duality to scheduling thermal generating systems. IEEE Transactions Power Apparatus and Systems, (12), 1968.
[2] Yves Pochet and Laurence A Wolsey. Production planning by mixed integer programming. volume 149. Springer. 2006.
[3] Rodrigo Moreno, Roberto Moreira, and Goran Strbac. A milp model for optimising multi- service portfolios of distributed energy storage. Applied Energy, 137:554-566, 2015.
[4] Robert E Bixby, Mary Fenelon, Zonghao Gu, Ed Rothberg, and Roland Wunderling. Mixed- integer programming: A progress report. The sharpest cut: the impact of Manfred Padberg and his work, pages 309-325. SIAM, 2004.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2):45544) 421, 2021.
[6] Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. survey for solving mixed integer programming via machine learning. Neurocomputing, 519: 205-217, 2023.
[7] He He, Hal Daume III and Jason M Eisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
10

---

[8] Maxime Gasse. Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances neural information processing systems, 32, 2019.
[9] Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. In The Eleventh International Conference on Learning Representations, 2023,
[10] Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarek, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data-driven compilation the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):4434490, 2021.
[11] Jun Sakuma and Shigenobu Kobayashi. A genetic algorithm for privacy preserving com- binatorial optimization. In Annual Conference on Genetic and Evolutionary Computation, 2007.
[12] LLC Gurobi Optimization. Gurobi optimizer. URL http://www. gurobi. com, 2021.
[13] Han Lu, Zenan Li, Runzhong Wang, Qibing Ren, Xijun Li, Mingxuan Yuan, Jia Zeng, Xiaokang Yang, and Junchi Yan. Roco: general framework for evaluating robustness of combinato- rial optimization solvers on graphs. In The Eleventh International Conference on Learning Representations, 2023.
[14] Russ J Vander Wiel and Nikolaos V Sahinidis. Heuristic bounds and test problem generation for the time-dependent traveling salesman problem. Transportation Science, 29(2):167-183, 1995.
[15] Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study, pages 37-60. Springer Berlin Heidelberg, Berlin, Heidelberg, 1980. ISBN 978-3-666 -72-3-642-00802-3
doi: 10.0007/ URL
attps://doi: 10g/10.1r 1007 /BF2012086886.
[16] Simon Andrew Bowly. Stress testing mixed integer programming solvers through new test instance generation methods. PhD thesis, School Mathematical Sciences, Monash University, 2019.
[17] Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec. G2sat: learning to generate sat formulas. Advances in neural information processing systems, 2019.
[18] Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing mixed-integer linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.
[19] Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and strong structure-hardness. aware baseline. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
[20] Jacob Devlin, Ming-Wey Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04800 2018.
[21] Omar Mahmood, Elman Mansimov, Richard Bonneau, and Kyunghyun Cho. Masked graph modeling for molecule generation. Nature communications, 12(1))3156, 2021.
[22] Diederik P Kingma and Max Welling, Auto-encoding variational bayes. arXiv preprint arXiv:1312.61 14, 2013.
[23] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint drXiv:1611.07308, 2016.
[24] Rafael G6mez-Bomband Jennifer Wei, David Duvenaud, José Miguel Hemáánezz-Lobato Benjamín Sánchez-Lengeling Dennis Sheberla, Jorge Aguilera-lparraguiire, Timothy D Hirzel, Ryan Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, (2):268-2266 2018.
11

---

[25] Tomáš Balyo, Nils Froleyks, Marijn JH Heule, Markus Iser. Matti Järvisalo, and Martin Suda. Proceedings of sat competition 2020: Solver and benchmark descriptions. 2020.
[26] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[27] Xijun Li, Qingyu Qu, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, and Jie Wang. Accelerating linear programming solving by exploiting the performance variability via reinforcement learning. 2023.
[28] Yufei Kuang, Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng. Houqiang Li, Yongdong Zhang, and Feng Wu. Accelerate presolve in large-scale linear programming via reinforcement learning. arXiv preprint arXiv:2310.11845 2023.
[29] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprini (.Ki::2012.1334999 2020.
[30] Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10219-10227, 2022.
[31] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear programming. arXiv preprint arXiv:2302.05636. 2023.
[32] Radu Caltean-Luugjjat Pierre Bonami, Ruth Misener, and Andrea Tramontani. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. preprint: http:///ww.
optimization-oni aptimizaatinn-nninee online org/DB_ HTML/201//1/6943, html, 2019.
[33] Qingyu Qu, Xijun Li, Yunfan Zhou, Jia Zeng. Mingxuan Yuan, Jie Wang, Jinhu Lv, Kexin Liu, and Kun Mao. An improved reinforcement learning algorithm for learning to branch. arXiv preprint arXiv:2201.06211 2022.
[34] Alper Atamtürk. On the facets of the mixed-integer knapsack polyhedron. Mathematical Programming, 98(1-3):145-175 2003.
[35] Jie Wang. Zijie Geng, Xijun Li, Jianye Hao, Yongdong Zhang, and Feng Wu. G2milp: Learning to generate mixed-integer linear programming instances for milp solvers. nov 2023. doi: 10. 3627/techmxxv2456655vv1 URL http://dx doi. 0rg/10.3622) http://00..227//ccrriit/// http/ritchxciieeeeee 24566554. v1.
[36] Xiaojie Guo and Liang Zhao. A systematic survey on deep generative models for graph generation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[37] Rocío Mercado, Tobias Rastemo, Edvard Lindelöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Esben Jannik Bjerrum. Graph networks for molecular design. Machine Learning: Science and Technology, 2(2):025023, 2021.
[38] Wenqi Fan, Chengyi Liu, Yunqing Liu, Jiatong Li, Hang Li, Hui Liu, Jiliang Tang, and Qing Li. Generative diffusion models on graphs: Methods and applications. arXiv preprint ar2.v.2302.02551, 2023.
[39] Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. A survey on deep graph generation: Methods and applications. arXiv preprint 2rXiv:2203.0671 2022.
[40] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pages 2323-2332. PMLR, 2018.
[41] Zijie Geng, Shufang Xie, Yingce Xia, Lijun Wu, Tao Qin, Jie Wang, Yongdong Zhang, Feng Wu, and Tie-Yan Liu. De novo molecular generation via connection-awand motif mining. In The Eleventh International Conference on Learning Representations, 2023.
12

---

[42] Duncan J Watts and Steven H Strogatz. Collective dynamics of "small-worid networks. nature, 393(6684):440-4444 1998.
[43] Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahra- mani. Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research, 11(2), 2010.
[44] Iván Garzón, Pablo Mesejo, and Jesús Giráldez-Cru. On the performance of deep generative models of realistic sat instances. In 25th International Conference Theory and Applications of Satisfiability Testing (SAT 2022). Schloss Dagsuhl--Leinnizzzeentuu für Informatik, 2022.
[45] Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning combinatorial optimization solvers. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. URL https: //openreview
[46] Samuel R Bowman, Luke Vilnis, Oriol Vinyals, Andrew M Dai, Rafal Jozefowicz, and Samy Bengio. Generating sentences from a continuous space. arXiv preprint arXiv:1571.06345 2015.
[47] Frank Hutter. Lin Xu, Holger H Hoos, and Kevin Leyton- Brooon Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence, 206:79-111, 2014.
[48] Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: bench- marking models for de novo molecular design. Journal of chemical information and modeling, 1193):0096-108, 2019.
[49] Jianhua Lin. Divergence measures based on the shannon entropy. IEEE Transactions on Information theory, 37(1):15--151 1991.
[50] David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker. Decision diagrams for optimization, volume Springer, 2016.
[51] Tobias Achterberg. Scip: solving constraint integer programs. Mathematical Programming Computation, 1:1-41, 2009.
[52] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(1)), 2008.
13

---

A Implementation Details
A.1 Data Representation
As described in the main paper, we represent each MILP instance as a weighted bipartite graph (V),,E) where represents the constraint vertex set, W represents the variable vertex set, and & represents the edge set, respectively. The graph is equipped with a tuple of feature matrices (V, W, E), and the description of these features be found in Table 5.
Table 5: Description of the constraint, variable, and edge features in our bipartite graph representation.
Tensor
Feature
Description
bias
The bias value b;.
type
Variable type (binary, continuous, integer, implicit integer) 4-dimensional one-hot encoding.
objective
Objective coefficient ej.
W
cass_loer__aee bound
Lower bound indicator.
has_ mus__pper_boot bound
Upper bound indicator.
lower_bound
Lower bound value 7
upper_bound bound
Upper bound value dy.
coef
Constraint coefficient aij.
To ensure consistency, we standardize each instance to the form of Equation 1. However, we do not perform data normalization in order preserve the potential information related to the problem domain the original formulation. When extracting the bipartite graph, we utilize the readily available observation function provided by Ecole. For additional details the observation function, readers can consult the following link: https /doc. ecole. ai ai/py/ epy/e//et observations. htm1#ecoll observation. MilpBipartite.
A.2 The Derivation of Masked Variational Auto-Encoder
We consider variable with distribution p(æ). We draw samples from this distribution and apply masking process to transform each sample æ into E through given probability p( x). Our objective data based on the the masked data
construct parameterized generator pe ()) to produce
ã. We assume that the generation process involves an unobserved continuous random variable z that independent of I, i..., 1 æ. Consequently, obtain the following equation:
Po (= Φ) pe (2) 2 (2) pe (x z, ())
(14)
pe p=(2|x, Φ)
We introduce probabilistic encoder q (=|x) for approximating the intractable latent variable distribution. We can then derive the follows:
log pe (xc ( =Ezagol (=|m)
[log pe [T]
log Po (x) x, á pz( (=(2)x)) qo (2(())
E Ezngo(=(a)
p0 xx, #) 46 (x)x))
Po z, (z)
Tes (2((2))) pe ( x at)
=Egrng(z(a)
log
+ Eznos())))
log
L(O, o x) + DKI. (2 (= a)]
2 L(0, 2(0.6/z. #).
(15)
14

---

In the formula, the term - C(0 Φ| à)) à)) is referred to as the evidence lower bound (ELBO), or the variational lower bound. It can be expressed as:
po( z, ())
L( Φ1 Φ) =E Bx
log
9 (
log gø x+)
E ( [log ar 2 a)] Ex to (z)()
po
= =Bzngo(=)a) [log (z)z, æ)] DKL (2(22))))p)
(16)
Consequently, the loss function can be formulated as follows:
L(O, Φ) = En-DEe [2(0, <b2, a)]
(17)
where
L(O, 000, x)- = =B Rengolala) Po (zrl2, + DKL. les( (z (a)) (lpo
(18)
Cycie
In the formula, the first term Liee is referred as the reconstruction loss, as urges the decoder to reconstruct the input data æ. The second term Cprio is referred to as the prior loss, as it regularizes the posterior distribution (5{2|z)) x>) of the latent variable to approximate the prior distribution po =). In practice the prior distribution po(z) is commonly taken as (00, I), and a hyperparameter is often introduced as the coefficient for the prior loss. Consequently, the loss function can be expressed as;
C(O, +) En-DE Em-pBe [C(0, 21 R)],
(19)
where
[(O, 6 x x) Lee ( δ|.; x) + 3. (olior())z)) Lree (0, Φ x) (x Po #) Cpeir (Ø)=) DKL
(20)
In G2MILP, the loss function is instantiated as:
[( Φ) Eg (10
(21)
where
C(O, g19.9) Cree @ () 3. Cprio (Ø1
( 269 9) Ez~ (Z)0)
po po 9)
(22)
Cprir ( DRL. la (Z n))
A.3
G2MILP Implementation
A.3.1 Encoder
The encoder implements g (Z))) Equation 22. Given a bipartite graph g = (VUW,&) E) equipped
with the feature metrices (V, W, E), we employ GNN structure with parameters Φ to extract the representations. Specifically, we utilize MLPs as embedding layers to obtain the initial embeddings h hwy and hey given by:
(.) MLP
h (0) = MLP hery MLP
(23)
Next, we perform K graph convolution layers, with each layer the form of two interleaved half-convolutions. The convolution layer is defined as follows:
h (k+1) MLP +
h (k) h
Σ
MLP (n!!) hery (A))
h
JieEEEE
h
(k+1) hws
MLP +
h (k)
Σ
MLP (he,
(k+1) hear k!
(24)
Steey EE
15

---

The convolution layer is followed by two GraphNorm layers, one for constraint vertices and the other for variable vertices. We employ concatenation Jumping Knowledge layer aggregate information from all K layers and obtain the node representations:
CONCAT k=
(n!!. (b!))) hww M
(CONCAT (b())) k= K
h &LP
(25)
The obtained representations contain information about the instances. Subsequently, we use two MLPs to output the mean and log variance, and then sample the latent vectors for each vertex from Gussian distribution as follows:
Z11 N (MLP& (hw;) exp MLP (trv))s
wwy ~ N (MLP (hw,) exp MLP (Rw,))
(26)
A.3.2 Decoder
The decoder implements ( 9) in Equation 22. It utilizes GNN structure obtain the representations, which has the same structure as the encoder GNN, but is with parameters instead of Φ. To encode the masked graph, we assign special [mask] token to the masked vertex ë. Its initial embedding h is initialized as a special embedding [mask] We mask all edges between and the variable vertices and add virtual edges. In each convolution layer, we apply special update rule for Ú:
(1++1) MI.Po ( (K) MEAN
(n(b5t2)))
h (k++1)
MLP, (h(btt1) h 1
(27)
ByEW
This updating is performed after each convolution layer, allowing e to aggregate and propagate the information from the entire graph.
The obtained representations are used for the four networks Bias Predictor, Degree Predictor, Logits Predictor, and Weights Predictor-to determine the generated graph. The details of these networks have been described in the main paper. Here we provide the losses for the four prediction tasks. In the following context, the node features, e.g., hg, refer to those from & obtained by the decoder GNN.
Bias Prediction Loss:
L (0, (0. 9) MSE (a (MLPhins ([hs, za])) bb)
(28)
Degree Prediction Loss:
C2 MSE (a (MLP ([ho, (hh.:zll) .d:)
(29)
Logits Prediction Loss:
Ls 0g 9) (aa [Log (8h
-E (a log (1 8brm)
8 (MLplogin (1hu zul))
(30)
Weights Prediction Loss:
(. MSE (MLL (hhus zul)) Aba
(31)
With these four prediction tasks, the reconstruction loss in Equation 22 instantiated as:
Liee 0, $ a: (.,0
(32)
A.3.3 Training and Inference
We describe the training and inference procedures in Algorithm 1 and Algorithm 2, respectively.
16

---

Algorithm 1: Train G2MILP
Input: Dataset D, number of training steps N, batch size B.
Output: Trained G2MILP, dataset statistics b, b. d, e, E. Calculate the statisties b, b, d, d, e, over D;
2 for 71 1, do
B +-+ 0:
for
b 1,... do
G~ D,Ü~ vo:
< G.MaskNode(t):
<- (B 9)};
Compute byg d2. oi,u
Compute C(O, Φ blG 9) in Equation 22; C(e, Φ) B Eigg)e C( ΦlG.9);
10
11
Update 0, Φ to minimize ().
Algorithm 2: Generate a MILP instance
Input: Dataset D, trained G2MILP, dataset statistics b, b, d. d, g, E, masking ratio r).
Output: A novel instance G.
D, Niters + 7) 119), 9 f 9;
for 1, Nutea do
V9,
Compute 8g. be + b + (b b) bg. G.ü.bias +- ba;
Compute di. do + d + (d d) d;:
for E w do Compute bg for E arg Topk Iu E Compute , és t + (e - g) E..
do
G.AddEdge(i, u):
10
11
B.er...eiight +- Êz,ui
G G:
13 Output J.
B Experimental Details
B.1 Dataset
The three commonly used datasets, namely MIS, SetCover, and MIK, are the same those used in [9]. Nurse Scheduling contains a group of 4 instances from MI- PLIB 2017: weweechhddmmdiuudde and sarrsesched-sprint--ne mursesched-sprinte and aursesched-sprint--aaee for test. Table 6 summarizes some statistics of these datasets.
for training, and
Table 6: Statistics of datasets. Size means the number of instances in the training set. |V] and [W] are the numbers of constraints and variables, respectively.
Dataset
MIS
SetCover
MIK
Nurse Scheduling
Size
1000
1000
80
2
Mean |V]
1953
500
346
8707
Mean [W]
500
1000
413
20659

---

B.2 Hyperparameters
We report some important hyperparameters in this section. Further details can be found in our code once the paper is accepted to be published.
We model dimension are set to 16. The depth of the GNNs is Each MLP has one hidden layer and uses ReLU() the activation function.
single GeForce RTX 3090 GPU. The hidden dimension and the embedding
In this work, we simply set all a; to 1. We find that the choice of 3 significantly impacts the model performance, For MIS, we set 33 to 0.00045. For SetCover, MIK and Nurse Scheduling, we apply sigmoid schedule [46] to let 3 to reach 0.0005, 0.001, and 0.001, respectively. We employ the Adam optimizer, train the model for 20, 000 steps, and choose the best checkpoint based on the average error in solving time and the number of branching nodes. The learning rate is initialized to 0.001 and decays exponentially. For MIS. SetCover, and MIK, set the batch size to 30. Specifically, to provide more challenging prediction tasks in each batch, we sample 15 graphs and use each graph to derive 2 masked ones for training. For Nurse Scheduling, set the batch size as 1 due to the large size of each graph.
B.3 Structural Distributional Similarity
Table 7:
Description of statisties used for measuring the structural distributional similarity. These statistics are calculated on the bipartite graph extracted by Ecole.
Feature
Description
coef dees_
Fraction of non-zero entries in A, i.e. |8)/(IV) (W]).
gons_derree_ment
Mean degree of constraint vertices in V.
cons_degree_stee std
Std of degrees of constraint vertices in V.
var var_degree_ment mean
Mcan degree variable vertices W.
var_degree_std
Std of degrees of variance vertices in W.
ths_meea
Mean of non-zero entries in A.
lbs_std
Std of non-zero entries in A.
rhs mean
Mean of b.
rhs std
Std of
clustering_cooe
Clustering coefficient of the graph.
modularity
Modularity of the graph.
Table 7 presents the statistics that we use to measure the structural distributional similarity. First, we calculate the statistics for each instance. We then compute the JS divergence Dis.; between the generated samples and the training set for each descriptor i E {1, 11]. We estimate the distributions using the histogram function in numpy and the cross entropy using the entropy function in scipy. The JS divergence falls in the range (0, log 2], so we standardize it to a score s; via:
1
(log 2 DJs.;).
(33)
log
Then we compute the mean of the 11 scores for the descriptors obtain the final score s:
(34)
Hence the final score ranges from to 1, with a higher score indicating better similarity.
We use the training set to train G2MILP model for each dataset and generate 1000 instances to compute the similarity scores. For MIK, which has only 80 training instances, we estimated the score using buc-back sampling.
18

---

Table 8: Results on the optimal value prediction task (meandistd). On each dataset and for each method, we sample 5 different sets of 20 instances for augmentation.
MIK
Nurse Scheduling
MSE
Improvement
MSE
Improvement
Dataset
0.0236
0.0%
679.75
0.0%
Bowly
663.52 (+:95.33)
2.3% (+14.0%)
Random 0.0104 (=10. (+..0003)
55.9%
(+9.7%)
G2MILP
0.0073 (+0.0014) 69.1% (15.9%)
548.70 (#44.68)
19.3% (16.6%)
Table 9:
Results the predict-and-search framework MIS. The training set contains 100 instances, and we generate 100 new instances. For Random and G2MILP, masking ratio 0.01. Time means the time for Gurobi to find the optimal solution with augmenting data generated by different models. Bowly leads to the framework failing to find optimal solutions in the trust region.
Method
Training Set
Bowly
Random
G2MILP
0.041
0.037
0.032
Time
17/100 fail
(+00006
(#000033
(=0.004)
Notice that for a fair comparison, we exclude statistics that remain constant in our approach, such as problem size and objective coefficients. We implement another version of metric that involves more statistics, and the results are in Appendix C.3.
B.4 Downstream Tasks
The generated instances have the potential to enrich dataset in any downstream task. In this work, demonstrate this potential through two application scenarios, i.c., the optimal value prediction task and the predict-and-search framework.
Two datasets, MIK and Nurse Scheduling, are considered, with medium and extremely small sizes, respectively. Following [18], we employ GNN predictive model. The GNN structure similar to the GNNs in G2MIL. We obtain the graph representation using mean pooling over all vertices, followed by two-layer MLP to predict the optimal values of the instances.
Optimal Value Prediction
For each dataset, we train GNN predictive model on the training set. Specifically, for MIK, we use 80% of instances for training, 20% of instances for validating, and train for 1000 epochs to select the best checkpoint based on validation MSE. For Nurse Scheduling, we use both instances to train the model for 80 epochs. We use the generative models, Bowly, Random, and G2MILP, to generate 20 instances similar to the training sets. For Random and G2MILP, we mix together the instances generated by setting the masking ratio 1) to 0.01 and 0.05, respectively. Next, we use the generated instances to enrich the original training sets, and use the enriched data to train another predictive model. We test all the trained model on previously unseen test data. Table 8 presents the predictive MSE on the test sets of the models trained on different training sets. As the absolute values of MSE less meaningful than the relative values, report the performance improvements brought by different generative technique. The improvement of Modelz relative to Model, is calculate as follows:
MSE; MSE₁
Improvement,
(35)
MSE,
On MIK, Bowly results in numerical issues as some generated coefficients are excessively large. G2MILP significant improves the performance and outperforms Random. On Nurse Scheduling, Random fails to generate feasible instances, and Bowly yields minor improvement. Notably, G2MILP allows for the training the model with even minimal data.
Predict-and-Search We conduct experiments on neural solver, i.e., the predict-and seddict-ndd-seacc frame- work proposed by Han et al. [31] Specifically, they propose framework that first predicts solution and then uses solvers to search for the optimal solutions in a trust region. We consider using generated instances to enhance the predictive model. We first train the predictive model on 100 MIS instances, and then use the generative models to generate 100 new instances augment the dataset. The results
19

---

are in Table 9. Bowly generates low-quality data that disturbs the model training, so that there is no optimal solution the trust region around the predicted solution. Though both Random and G2MILP can enhance the solving framework to reduce solving time, we can see G2MILP significantly outperforms Random.
Discussions
These two downstream tasks, despite their simplicity, possess characteristics that make them representative problems that could benefit from generative models. Specifically, we identify the following features.
1. More is better. We want as many data instances as possible. This condition is satisfied when we can obtain precise labels using existing methods, e.g., prediction- baseedd neural solvers [31], or when unlabeled data is required for RL model training, e.g., RL for cut selection [9].
2. More similar is better. We want independent identically distributed (i.i.d.) data instances for training. Thus
3. More diverse is better. We want the data to be diverse, despite being i.i.d., so that the trained model can generalize better.
Our experimental results demonstrate the potential of G2MILP in facilitating downstream tasks with these characteristics, thus enhancing the MILP solvers. We intend to explore additional application scenarios in future research.
C
Additional Results
C.1
Comparison with G2SAT
Table 10: Results of G2SAT MIS. In the table, "sim" denotes similarity score (higher is better), "time" denotes solving time, and "#branch" denotes the number of branching nodes, respectively. Numbers in brackets denote relative errors (lower is better).
sim
time (s)
#branch
Training Set
0.998
0.349
16.09
G2SAT
0.572
0.014 (96.0%)
2.11 (86.9%)
G2MILP (1) 0.01)
0.997
0.354 (1.5%)
15.03 (6.6%)
G2MILP (1) = 0.1)
0.895
0.214 (38.7%)
4.61 (71.3%)
We conduct an additional experiment that transfers G2SAT to a special MILP dataset, MIS, which all coefficients are 1.0 and thus the instances can be modeled as homogeneous bipartite graphs. We apply G2SAT to learn to generate new graphs and convert them to MILPs. Results are in Table 10. The results show that G2MILP significantly outperforms G2SAT on the special cases.
C.2 Masking Process
Masking Variables In the mainbody, for simplicity, we define the masking process of uniformly sampling constraint vertex e W((V to mask, while keeping the variable vertices unchanged. We implement different versions of G2MILP that allow masking and modifying either constraints, variables, both. The results in Table 11.
Ablation on Masking Ratio We have conduct ablation studies on the effect of the masking ratio on MIK. The results are Figure The experimental settings are the same with those in Table and Figure 2. From the results we have the following conclusions. (1) though empirically smaller leads to relatively better performance, G2MILP maintains a high similarity performance even when v is large. (2) The downstream task performance does not drops significantly. This makes sense because smaller 7) leads to more similar instances, while larger 7) leads to more diverse (but still similar) instances, both of which can benefit downstream tasks. (3) G2MILP always outperforms Random,
20

---

Table 11: Results of different implementations of G2MILP on MIK. In the table, 17 denotes mask ratio, "v" denotes only modifying variables (objective coefficients and variable types), "c" denotes only modifying constraints, and "vc" denotes first modifying variables and then modifying constraints. We do not report the similarity scores for "v" models because the current similarity metrics exclude statistics that measure only variables.
sim
time (s)
#branch
Training Set
0.997
0.198
175.35
0.183 (7.5%)
136.68 (22.0%)
G2MILP
(1) = 0.01)
0.989
0.169 (17.1 %)
167.44 (4.5%)
vC
0.986
0.186 (6.1%)
155.40 (11.4%)
0.176 (11.1%) %)
136.68 (22.0%)
G2MILP
( 0.05)
0.964
0.148 (25.3%)
150.90 (13.9%)
0.964
0.147 (25.3%)
142.70 (18.6%)
0.172 (13.1%% 16
136.67 (22.1 1%)
G2MILP
(1) = 0.1)
0.905
0.117 (40.9%)
169.63 (3.3%)
vc
0.908
0.115 (41.9%)
112.29 (35.9%)
1.0
1.0
0.8
Smallarty Store
0.8
0.6
Rolative
11.4
0.4
G2MILP
G2MILP
0.2
0.0
0.8
Mack Ratio
Mask Ration
(a) Distributional Similarity
(b) Relative MSE
Figure 4: (a) Distributional similarity score (higher is better) and (b) Relative MSE (lower is better) v.s. masking ratio 1/.
which demonstrates that the learning paradigm helps maintain the performance. (4) Bowly fails on this dataset because its generated instances lead to numerical issues and cannot be read by Gurobi or SCIP. Moreover, in real applications, it is reasonable and flexible to adjust the hyperparameter to achieve good performances different scenarios.
Orders of Masked Constraints We also investigate different orders of masking constraint vertices, including uniformly sampling and sampling according the vertex indices. Results are in Table 12. We find that uniformly sampling achieves the best performance. Sampling according to indices leads performance decrease, maybe because near constraints are relevant and lead error accumulation. We think these results are interesting, and will study it in the future work.
C.3 Structural Distributional Similarity
In the mainbody, for fair comparison, we exclude statistics that remain constant in our approach, such as problem size and objective coefficients. However, these statistics are also important features for MILPs. In this section, we incorporate three additional statistics in the computing of similarity scores: (1) mean of objective coefficients c, (2) std of objective coefficients and (3) the ratio of continuous variables. With these additional metrics, we recompute the structural similarity scores and updated the results in both Table 2 and Table 11. The new results are in Table 13 and Table 14,
21

---

Table 12: Results of different implementations of generation orders on MIK dataset. In the table, "Uni" denotes uniformly sampling from constraints. "Idx / and "Idx" Y denote sampling constraints according to indices in ascending order and descending order, respectively.
order
model
sim
time (s)
#branch
G2MILP
0.953
0.129 (35.1%) 1%)
235.35 (34.2%)
Uni
Random
0.840
0.004 (97.9%)
0.00 (100%)
G2MILP
0.892
0.054 (72.7%)
108.30 (38.2%)
Idx
Random
0.773
0.002 (98.9%)
0.00 (100%)
G2MILP
0.925
0.027 (86.2%)
31.53 (82.0%)
Idx
Random 0.827
0.003 (98.6%)
0.00 (100%)
respectively. From the results, we can still conclude that G2MILP outperforms all baselines, further supporting the effectiveness of our proposed method.
Table 13: (Table recomputed.) Structural distributional similarity scores between the generated instances with the training datasets. Higher is better. the masking ratio. We do not report the results of Bowly on MIK because Ecole [45] and SCIP [51] fail to read the generated instances due large numerical values.
MIS
SetCover
MIK
Bowly
0.144
0.150
Random
0.722
0.791
0.971
17 0.01
G2MILP 0.997
0.874
0.994
Random 0.670
0.704
0.878
7) 0.05
G2MILP 0.951
0.833
0.969
Random 0.618
0.648
0.768
0.1
G2MILP
0.921
0.834
0.930
Table 14: (Table 11 recomputed.) Results of different implementations of G2MILP on MIK. In the table, 7 denotes mask ratio, "v" denotes only modifying variables (objective coefficients and variable types), "c" denotes only modifying constraints, and "vc" denotes first modifying variables and then modifying constraints.
G2MILP (7) = 0.01)
0.998
0.988
0.985
G2MILP 0.05)
0.996
0.968
0.967
G2MILP (1 = 0.1)
0.996
0.928
0.912
C.4 Sizes of Datasets
We conduct experiments on different sizes of the original datasets, well the ratio of generated instances to original ones, on MIS. The results are in Table 15. The results show that G2MILP can bring performance improvements on varying sizes of datasets.
C.5 Visualization
The t-SNE visualization for baselines are in Figure 5. G2MILP generates diverse instances around the training set, while instances generated by Random are more biased from the realistic ones.
22

---

Table 15: Results on the optimal value prediction task on MIS with different dataset sizes. In the table, "#MILPs" denotes the number of instances in the training sets, and "Augment%"" denotes the ratio of generated instances to training instances.
#MILPs
Augment%
MSE
Improvement
0
1.318
50
25%
1.014
23.1%
50%
0.998
24.3%
100%
0.982
25.5%
0
0.798
100
25%
0.786
1.5%
50%
0.752
5.8%
100%
0.561
23.7%
0
0.294
0
200
25%
0.283
19.0%
50%
0.243
17.3%
100%
0,202
31.3%
0
0.188
500
25%
0. 0.168
10.6%
50%
0.175
6.9%
100%
0.170
9.6%
G2MILP = 0.01)
G2MILP (1 = 0.05)
G2MILP (y= 0.1)
Randomi (y 0.01)
Random (γ 0.05)
Random (y 0.1)
Triining See. Random
Figure 5: The t-SNE visualization of MIL.P instance representations MIK. Each point represents an instance. Red points are from the training set, blue points are instances generated by G2MILP, and green points are instances generated by Random.
23


Reviews:
[{"review_id": "aciS71SWK1", "reviewer": "Reviewer_K4a3", "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.", "questions": "1. How does G2MILP deal with different n and m?  Different instances would have different n and m.\n2. For the proposed normalization, would it be problematic when there is outlier in the dataset?\n3. 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?\n4. 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.\n5. 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.", "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).", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n2. 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. \n2. 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. \n3. 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}}$.\n4. The writing needs to be further improved. See the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving the work.\n\n**Weakness 1.**\n\n- We state the novelty of our work in respect of both task setting and technique in **Global Response 1**. Due to space limitation, we summarize the statement here.\n\n  - Generating MILPs is much harder than generating SATs because it involves precise numerical prediction. G2SAT can hardly transfer to MILP generation.\n\n  - We assume that you refer to masked auto-encoder (MAE) developed in computer vision. If not, please kindly provide the literature citation. However, they are different because MAE is an auto-regressive method which aims to reconstruct given samples, while our masked VAE framework aims to generate new instances from masked ones.\n\n**Weakness 2.**\n\n- Thanks for your suggestion! **We have implemented a new version of G2MILP that supports modifying variables.** Results are in **Table 10** in the newly submitted PDF. Due to space limitation, you can refer to **Global Response 4** for more details. \n\n**Weakness 3.**\n\n> Eq. (9) and Eq. (11) are inconsistent with Fig. 1.\n\n- Thanks for your comment! **Fig 1 shows the inference process while Eq. (9) and Eq. (11) details the network implementation.** As shown in Fig. 1, the logits and weights prediction are conditioned on the degree. As for the detailed implementation, we use a NN to predict $\\hat{d}_{\\tilde{v}}$.\nWe use another NN to predict the ${\\hat{\\delta}} _{\\tilde{v},u}$ for each variable vertex $u$, and this NN is not conditioned on  $\\hat{d} _{\\tilde{v}}$ . Then the connected vertices are the $\\hat{d} _{\\tilde{v}}$ variable vertices with top $\\hat{\\delta} _{\\tilde{v},u}$, and so the connected vertices are conditioned on both  $\\hat{d} _{\\tilde{v}}$  and  $\\hat{\\delta} _{\\tilde{v},u}$ . We will improve the presentation in a revised version to avoid inconsistency.\n\n> The logits/weights prediction should be conditioned on $ℎ_{\\tilde{v}}$ and $z_{\\tilde{v}} $.\n\n- Thanks for the insightful question! As we add virtual edges between $\\tilde{v}$ and all variable nodes (Line 167), there should be message passing between $\\tilde{v}$ and the variable nodes, and thus the information of $\\tilde{v}$ has been encoded into other node representations. Therefore, we do not explicitly use $h_{\\tilde{v}}$ and $z_{\\tilde{v}}$ as inputs for logits/weights prediction. Actually we have tried such implementation before, but found that it introduced additional parameters while the impact on performance was limited.\n\n**Weakness 4.**\n\n- We respond to your questions as below, and we will polish our writing in a revised version to make the questions clear in our paper.\n\n**Questions 1.**\n\n- For the **inputs**, G2MILP allows any $n$ and $m$ because the model does not depends on instance size. For the **outputs**, current implementation of G2MILP does not change $n$ and $m$ of input instances. \n\n- It is possible that G2MILP outputs instances with slightly different $n$ and $m$. For example, we can add a virtual constraint, mask it and generate a new one to obtain an instance with one more constraint. Generating MILP instances with different scales but similar semantic information and similar difficulty is an interesting topic, and we plan to study it in our future work.\n\n**Question 2.**\n\n> For the proposed normalization, would it be problematic when there is outlier in the dataset?\n\n- In real applications, instances in the training set are from real-world scenarios. Thus covering all such cases is meaningful.\n- Every model might be impacted by outlier data. However, the normalization makes the model more robust to outlier cases, because it maps all values to $[0,1]$, which makes it easier for the model to learn.\n- Empirically, we do not find obvious outliers in several datasets.\n\n**Question 3.**\n\n- **We consider comprehensive metrics including coefficient density, constraint and variable degrees, coefficient means, et al.** We excluded statistics such as problem sizes, numbers of  integer variables, et al. For descriptions of the considered statistics, readers can refer to Table 7 in Appendix B.3.\n\n**Question 4.**\n\n- **Bowly  generates instances from scratch by randomly sampling the coefficients.** It was not designed for learning datasets to generate realistic instances, and we can only contral simple statistics like problem sizes and coefficient means. For a fair comparison, we set all controllable parameters  the same as the training sets.\n- **We do not aim to show that G2MILP is better than Bowly in every metrics, because the two methods are for different tasks.** Our results show that instances generated by Bowly are unlikely to be realistic. In other word, it cannot learn to generate data that is iid. with existing data. Therefore, we can hardly use it in low-resource MILP solver development, which is also verified by downstream task experiments.\n\n**Question 5.**\n\n> Good generation should introduce novelty compared to the training set. \n>\n> It is tricky to use the structural distribution similarity to denote a good generation. \n\n- We state the rationality of our evaluation metrics in **Global Response 2**. Due to space limitation, we summarize the response as follows. \n  - The used similarity benchmark is based on many previous works. \n  - Beyond these similarity metrics, we also access the downstream task performance.\n  - Currently no strong enough metrics have been developed.\n\n> t-SNE visualization for the baselines should be included.\n\n- The t-SNE visualization for baselines are in **Figure 5** in the newly submitted PDF. G2MILP generates diverse instances around the training set, while instances generated by Random are more biased from the realistic ones."}, {"review_id": "mk2z0fhEN0", "reviewer": "Reviewer_sAxU", "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). ", "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:\n\n1. 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?\n\n2. The generation of a new MILP instance is an iterative process. What is the computation cost for generating one MILP instance?\n\n", "limitations": "The limitations are discussed in the paper. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "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. \n\nThe 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. \n\n2. \n\nThe 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. \n\n2.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? \n\n2.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. \n\n3.\t\n\nThe evaluations are insufficient to fully validate the proposed framework.\n\n3.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?  \n\n3.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? \n\n\n3.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?\n\n4.\t\n\nThe 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). \n\n5.\t\n\nPresentations 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and constructive comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**Weakness 1.**\n\nDue to space limitation, we state the contribution of our work in respect of both task setting and technique in **Global Response 1**.\n\n**Weakness 2.**\n\n> 2.1. generate the masked graph \n\n- Yes,  $\\tilde{p}(\\tilde{G}|G)$ is like a uniform distribution. Specifically, we generate $\\tilde{G}$ by sampling a constraint vertex $\\tilde{v}$ from all constraint vertices $\\mathcal{V}$ following a uniform distribution over these vertices, i.e., $\\tilde{v}\\sim U(\\mathcal{V})$. Then we mask $\\tilde{v}$ to generate $\\tilde{G}$.\n\n> 2.2. difference with MAE. \n\n- We assume that you refer to masked auto-encoder (MAE) in computer vision. If not, please kindly provide the literature citation. Due to space limitation, the differences are in **Global Response 1**.\n\n**Weakness 3.**\n\n> 3.1. Masking scheme.\n\n- We conduct ablation studies on more different masking ratios, from 0.01 to 1.0, which may help understand the masking scheme. The results are in **Figure 4** in the newly submitted PDF.\n- We test different orders of masking constraint vertices, including uniformly sampling and sampling according to the vertex indices. Results are in **Table 11**. We find that **uniformly sampling achieves the best performance**. Sampling according to indices leads to a performance decrease, maybe because constraints that are indexed closely are relevant and lead to error accumulation. We think these results are interesting, and will study it in the future work.\n\n> 3.2. Generation\n\n- We are not sure whether we understand the question correctly. The generation process is determined by (i) the masked graph and (ii) the latent variables. During training, the latent variables encode the information of original graphs (graph features), so the decoder learns to reconstruct the original graph from the masked graph according to the latent variables. During inference, the model is decoder-only and the latent variables are randomly sampled. Different latent variables lead to different generated samples, so the decoder can randomly generate new diverse instances.\n- Dense and complex original graphs may lead to harder generation because graph representation learning is more challenging.\n\n> 3.3. Downstream task evaluation.\n\n- For the results in Figure 2, we use a mixture of $10$ instances from $\\eta=0.01$ and $10$ instances from $\\eta=0.05$ together (see Line 572 in Appendix B.4), because we find the mixture brings a slight performance improvement.\n- We conduct ablation studies on masking ratio. Results are in **Figure 4(b)**. According to the results, though empirically a small masking ratio brings better performance, the performance does not decrease quickly with an increasing masking ratio.\n- We report the standard error for performance improvement in **Table 12**.\n- We conduct experiments on different sizes of the original datasets, as well as the ratio of generated instances to original ones, on MIS. The results are in **Table 13**. The results show that G2MILP can bring performance improvements on varying sizes of datasets.\n\n**Weakness 4.**\n\n- In real applications, low data availability is often a key bottleneck for solver development. Generating realistic instances is orthogonal to previous methods that directly focus on solver development, and can be applied in many different real-world scenarios. It does not take many efforts but can bring additional performance improvements.\n- G2SAT has attracted much attention since its publication, which implies that the graph generation pipeline for instance generation task is a proper topic for research community.\n- To further demonstrate the benefits of generated instances, we conduct an additional downstream task of a predict-and-search framework. Results are in **Table 14** and details are in **Global Response 3**.\n\n**Weakness 5.**\n\n- Thanks for your suggestions! We will re-arrange Table 2 and fix typos in a revised version. Notation wise, we will use $\\hat{G}$ to denote the outputs for clarity.\n\n**Question 1.**\n\n- **G2SAT cannot determine numerical values of the coefficients in MILPs.** Specifically, SAT instances can be modeled as homogeneous bipartite graph (i.e., graphs without edge weights or node features), and G2SAT splits the graphs into fragments and then merges the fragments together to form new ones. This method can generate new topological structures of bipartite graphs, but when merging the fragments together, it is nontrivial how to determine the edge weights, i.e., the coefficient values.\n- **Even without numerical coefficients, G2SAT can hardly preserve reality of instances.** To see this, we conduct **an additional experiment** that transfers G2SAT to a special MILP dataset, MIS, in which all coefficients are 1.0 and thus the instances can be modeled as homogeneous bipartite graphs. We apply G2SAT to learn to generate new graphs and convert them to MILPs. Results are in **Table 9** in the newly submitted PDF. The results show that G2MILP significantly outperforms G2SAT on the special cases.\n\n**Question 2.**\n\n- We generate $1000$ instances using G2MILP with $100$ iterations for each instances. **The average time costs for generating one instance for MIS, SetCover, and MIK are 0.45s, 0.97s and 0.85s respectively.** The time cost is linearly related to the number of iterations. Though being an iterative process, G2MILP is fast because each iteration is very fast. As a comparison, our experiments on MIS (mentioned in response to **Question 1**) show that G2SAT takes about 47s to generate one instance."}, {"review_id": "81EPnmqx7J", "reviewer": "Reviewer_qq1T", "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.\n\nThe 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.\n\nThe 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.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. This is the first deep generative model for MILP instance generation based on the well known variant-constraint bipartite representation.\n\n2. 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.\n\n3. 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.\n\n2. The effectiveness seems to drop quickly with higher ratio of variable/constraint alternations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.\n\n**Weakness 1.**\n\n> I have the feeling that the problem similarity metric is too privileged for the proposed method, as it essentially modifies existing problem instances.\n\n- **The used similarity benchmark is based on many previous works.** The considered statistics and features are commonly used in SAT generation [1] and MILP studies [2]. Measuring similarity by computing the distributional divergences is a common practice in benchmarking graph generation models [3]. \n- **Beyond these similarity metrics, we also access the downstream task performance.** The results demonstrate that instances generated by G2MILP are not only realistic, but can also benefit real-world applications.\n- **Measuring MILP instance quality is a hard task. Currently no strong enough metrics have been developed, and we may open up the direction.** We believe that with the development of MILP generation techniques, studies on benchmarking MILP instances will follow up, and exploring MILP space will become possible. This is in line with the development law of generative model research.\n- **Modifying existing problem instances is not a trivial task, and G2MILP works well.** See the comparison with the Random baseline. Random also modifies existing instances, but generated instances are specious and unlikely to be realistic.\n\n- **Because our aim is data augmentation, it is unnecessary to generate instances from scratch.** As an analogy, G2SAT generates SAT instances by splitting existing SAT graphs into templates and then learning to merge them to form new formulas. This technique then develops as a standard manner in SAT generation area. We believe modifying existing instances will become an important line in developing better MILP generators.\n\n[1] Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec. G2sat: learning to generate sat formulas. Advances in neural information processing systems, 32, 2019.\n\n[2] Frank Hutter, Lin Xu, Holger H Hoos, and Kevin Leyton-Brown. Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence, 206:79–111, 2014.\n\n[3] Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: benchmarking models for de novo molecular design. Journal of chemical information and modeling, 59(3):1096–1108, 2019.\n\n**Weakness 2.**\n\n> The effectiveness seems to drop quickly with higher ratio of variable/constraint alternations.\n\n**We have conduct ablation studies on the effect of the masking ratio $\\eta$ on MIK.** The results are in **Figure 4** in the newly submitted PDF. The experimental settings are the same with those in Table 2 and Figure 2. From the figure we have the following conclusions.\n\n- Though empirically a smaller $\\eta$ leads to a relatively better performance, G2MILP maintains a high similarity performance even when $\\eta$ is large.\n- The downstream task performance does not drops significantly. This makes sense because smaller $\\eta$ leads to more similar instances, while larger $\\eta$ leads to more diverse (but still similar) instances, both of which can benefit downstream tasks.\n- G2MILP always outperforms Random, which demonstrates that the learning paradigm helps maintain the performance.\n- Bowly fails on this dataset because its generated instances lead to numerical issues and cannot be read by Gurobi or SCIP.\n\nMoreover, in real applications, it is reasonable and flexible to adjust the hyperparameter $\\eta$ to achieve good performances in different scenarios."}, {"review_id": "UZdujB9UjM", "reviewer": "Reviewer_GoAh", "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. ", "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. \n\n1.\tWhy 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.\n", "limitations": "As far as I could understand, the generator could only output the instances with the same problem scale.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The task is highly valuable.\nThe 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.\nExperiment 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score and your confidence. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**Questions**\n\n> 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.\n>\n> 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.\n\n- Thanks for your suggestion! **We have conduct ablation studies on the effect of $\\eta$ on MIK.** The results are in **Figure 4** in the newly submitted PDF. The experimental settings are the same with those in Table 2 and Figure 2. From the figure we have the following conclusions.\n  - Though empirically a smaller $\\eta$ leads to a relatively better performance, G2MILP maintains a high similarity performance even when $\\eta$ is large.\n  - The downstream task performance does not drops significantly. This makes sense because smaller $\\eta$ leads to more similar instances, while larger $\\eta$ leads to more diverse (but still similar) instances, both of which can bnefit downstream tasks.\n  - G2MILP always outperforms Random, which demonstrates that the learning paradigm helps maintain the performance.\n  - Bowly fails on this dataset because its generated instances lead to numerical issues and cannot be read by Gurobi or SCIP.\n\n- Though Bowly generates instance from scratch, our results show that instances generated by Bowly are specious and unlikely to be realistic. This is because previous methods, including Bowly, are designed for research instead of developing solvers in real-world applications. Therefore, we can hardly use those methods in real-world scenarios. G2MILP, to the best of our knowledge, is the first method that can learn to generate realistic instances.\n- **Because our aim is data augmentation, it is unnecessary to generate instances from scratch.** As an analogy, G2SAT generates SAT instances by splitting existing SAT graphs into templates and then learning to merge them to form new formulas. This technique then develops as a standard manner in SAT generation area. We believe modifying existing instances will become an important line in developing better MILP generators.\n\n**Limitations**\n\n> The generator could only output the instances with the same problem scale.\n\n- Good point! **It is possible that G2MILP outputs instance with slightly different scales.** For example, we can add a virtual constraint, mask it and generate a new one to obtain an instance with one more constraint. Similarly, we can delete two constraints and generate a new one to obtain an instance with one less constraint. However, this method might seem trivial and unnecessary, because current implementation of G2MILP has brought good performance, and this method can hardly bring additional improvements.\n- **Generating MILP instances with different scales but similar semantic information and similar difficulty is a hard task.** Even in the community of SAT generation it has not been well solved. We recognize it as a valuable research direction and plan to study it in our future work."}, {"review_id": "LtbVpuYKJd", "reviewer": "Reviewer_Vxmz", "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. \n\nThe problem is relevant and interesting. The experiments show that the proposed approach obtains significantly better results than existing methods.", "questions": "Request the authors to answer the questions in weakness section. \n1. Downstream task: Augmenting neural mip solvers with generated data. ( Especially under low data availability).\n\n2. Presentation clarification( Fig 2 and Table 8).", "limitations": "The authors have addressed it nicely.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.  Important problem to tackle. The work has applications.\n\n2. Paper is easy to understand.\n\n3. The authors motivate different components of encoder decoder architecture nicely in the methodology section.\n\n4. The experimental section consists of Structural similarity metrics, hardness comparison of generated MILP instances, application on downstream task.\n\n5. Comparison on variety of datasets( MIS, Set cover, MIK(knapsack), including standard deviation, multiple runs.\n\n6. Visualization of generated instances( through TSNE plots).\n\n", "weaknesses": "1.  Downstream Task( learning to solve MIP)- learning to branch etc. :\n\nRecently 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.\n\nI 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.\n\n\n2. Presentation :\nTable 8 and Fig 2 not clear.\n\n 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).. \n\nAlso is there any difference between Table 8 and Fig 2?\n\n\n3. Code is not provided by authors.\n\n\n\n[A] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact354\ncombinatorial optimization with graph convolutional neural networks. Advances in neural355\ninformation processing systems, 32, 2019", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score and your confidence. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.\n\n**Weakness 1 & Question 1.**\n\n> 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.\n>\n> 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.\n\n- Thanks for your suggestion! **We conduct an additional downstream task for a neural solver, i.e., the predict-and-search framework proposed in [B].** This paper proposes a framework that first predicts a solution and then uses solvers to search for the optimal solutions in a trust region. We consider using generated instances to enhance the predictive model. We first train the predictive model on 100 MIS instances, and then use the generative models to generate 100 new instances to augment the dataset. The results are in **Table 14**. For your convenience, we quote Table14 here.\n\n  **Table 14: Results on the predict-and-search framework on MIS. The training set contains 100 instances, and we generate 100 new instances. For Random and G2MILP, masking ratio is 0.01. Time means the time for Gurobi to find the optimal solution with augmenting data generated by different models. Bowly leads to the framework failing to find optimal solutions in the trust region.**\n\n  | Method |    Training Set     |    Bowly    |       Random        |       G2MILP        |\n  | :----: | :-----------------: | :---------: | :-----------------: | :-----------------: |\n  |  Time  | 0.041 ($\\pm$ 0.006) | 17/100 fail | 0.037 ($\\pm$ 0.003) | 0.032 ($\\pm$ 0.004) |\n\n- The results show that Bowly generates low-quality data that disturbs the model training, so that there is no optimal solution in the trust region around the predicted solution. Though both Random and G2MILP can enhance the solving framework to reduce solving time, we can see G2MILP significantly outperforms Random, demonstrating its effectiveness.\n- We consider the predict-and-search task because it is a typical predictive task that requires large amounts of instances for training. Gasse et al.[A], however, leverages each branching decision, instead of each instance, as one data sample, so it may not be a typical application scenario of instance generative techniques.\n\n[A] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019\n\n[B] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, 410 and Xiaodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear 411 programming. ICLR, 2302.\n\n**Weakness 2 & Question 2.**\n\n> Presentation clarification( Fig 2 and Table 8).\n>\n> Presentation : Table 8 and Fig 2 not clear.\n>\n> 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)..\n>\n> Also is there any difference between Table 8 and Fig 2?\n\n- Thanks for your suggestion! The results with std in Table 8 are in **Table 12** in the newly submitted PDF. For your convenience, we quote Table 12 here (better viewed in the  submitted PDF).\n\n  **Table 12: Results on the optimal value prediction task (mean±std). On each dataset and for each method, we sample 5 different sets of 20 instances for augmentation.**\n\n  |         |          MIK          |          MIK           |   Nurse Scheduling   |  Nurse Scheduling   |\n  | :-----: | :-------------------: | :--------------------: | :------------------: | :-----------------: |\n  |         |          MSE          |      Improvement       |         MSE          |     Improvement     |\n  | Dataset |        0.0236         |          0.0%          |        679.75        |        0.0%         |\n  |  Bowly  |           -           |           -            | 663.52($\\pm 95.33$)  | 2.3% ($\\pm 14.0\\%$) |\n  | Random  | 0.0104 ($\\pm 0.0023$) |  55.9\\% ($\\pm 9.7\\%$)  |          -           |          -          |\n  | G2MILP  | 0.0073 ($\\pm 0.0014$) | 69.1$\\%$ ($\\pm 5.9\\%$) | 548.70 ($\\pm 44.68$) | 19.3% ($\\pm 6.6\\%$) |\n\n- **Table 8 and Figure 2 show the same results.** We are sorry for the typo. The \"Bowly\" in the left figure in Figure 2 should be \"Random\". As we state in Section 4.2 III., on MIK,  instances generated by Bowly introduce numerical issues so that Ecole and SCIP fail to read them. We will correct the typo in a revised version.\n\n**Weakness 3.**\n\n> Code is not provided by authors.\n\nWe will release our code once the paper is accepted to be published. We expect more studies on the topic of MILP instance generation, and our released code will be an important resource.\n\n"}, {"review_id": "ZVaKDTWWef", "reviewer": "Reviewer_sm9N", "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.", "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.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper takes a traditionally hard problem and proposes a novel solution to it.\n2. Experiment results seem very compellingly, however the lack of good baseline makes hard to judge how good it actually is.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score and your confidence. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.\n\n**Weakness.**\n\n> 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.\n\n- Thanks for your comment! **We want to emphasize that G2MILP, to the best of our knowledge, is the first learning based method to generate realistic MILP instances**. We open up a new research direction while previous methods cannot deal with such a task. Therefore, we can hardly find strong existing baselines.\n\n- **Nonetheless, we have delicately designed two baselines, i.e., Bowly and Random, for a fair comparison.**\n\n  - **Bowly** is a traditional rule-based MILP instance generation technique. It generates instances from scratch by randomly sampling the coefficients. It was not designed for learning datasets to generate realistic instances, and we can only tune simple statistics such as problem sizes and coefficient means. For a fair comparison, we keep all controllable parameters  the same as the training sets. Unsurprisingly, it does not work well on the new task.\n  - We design the **Random** baseline as a comparison to demonstrate the advantage of G2MILP, especially the deep learning modules. The comparison with this baseline demonstrates that modifying MILPs while reserving both graph semantic structure and difficulty is nontrivial, and our proposed deep learning framework is able to achieve that.\n\n- **For a better comparison, we add an additional experiment to compare G2MILP with G2SAT.**  Specifically, we adapt G2SAT to a special MILP dataset, MIS, in which all coefficients are 1.0 and thus the instances can be modeled as homogeneous bipartite graphs. Notice that G2SAT can only be applied on homogenous bipartite graphs, and so it only works on such special MILP data. We apply G2SAT to learn to generate new graphs and convert them to MILPs. Results are in **Table 9** in the newly submitted PDF. The results show that G2MILP significantly outperforms G2SAT on the special cases. For your convenience, we quote Table 9 here.\n\n\n  **Table 9: Results of G2SAT on MIS. In the table, ''sim'' denotes similarity score (higher is better), ''time'' denotes solving time, and ''\\#branch'' denotes the number of branching nodes, respectively. Numbers in brackets denote relative errors (lower is better).**\n\n  |                      | sim   | time (s)      | #branch      |\n  | -------------------- | ----- | ------------- | ------------ |\n  | Training Set         | 0.998 | 0.349         | 16.09        |\n  | G2SAT                | 0.572 | 0.014 (96.0%) | 2.11 (86.9%) |\n  | G2MILP ($\\eta=0.01$) | 0.997 | 0.354 (1.5%)  | 15.03 (6.6%) |\n  | G2MILP ($\\eta=0.1$)  | 0.895 | 0.214 (38.7%) | 4.61 (71.3%) |\n\n**Question.**\n\n> Is it possible to provide some \"fair\" comparisons on downstream proxy tasks with other popular methods?\n\n- Thanks for your suggestion! Previous popular methods include **instance generation methods** and **MILP solving methods**. For the former, though they are not designed for the  learning to generate task, we have designed the baselines and conduct comprehensive comparisons. For the latter, notice that G2MILP is orthogonal to them and can be used to enhance them. We also consider the downstream task (optimal value prediction) to demonstrate the effectiveness of G2MILP.\n\n- **For further demonstration, we conduct an additional downstream task, i.e., the predict-and-search framework proposed in [1].** This paper proposes a framework that first predicts a solution and then uses solvers to search for the optimal solutions in a trust region. We consider using generated instances to enhance the predictive model. We first train the predictive model on 100 MIS instances, and then use the generative models to generate 100 new instances to augment the dataset. The results are in **Table 14**. The results show that G2MILP can effectively enhance previous popular methods. For your convenience, we quote Table14 here.\n\n  **Table 14: Results on the predict-and-search framework on MIS. The training set contains 100 instances, and we generate 100 new instances. For Random and G2MILP, masking ratio is 0.01. Time means the time for Gurobi to find the optimal solution with augmenting data generated by different models. Bowly leads to the framework failing to find optimal solutions in the trust region.**\n\n  | Method |    Training Set     |    Bowly    |       Random        |       G2MILP        |\n  | :----: | :-----------------: | :---------: | :-----------------: | :-----------------: |\n  |  Time  | 0.041 ($\\pm$ 0.006) | 17/100 fail | 0.037 ($\\pm$ 0.003) | 0.032 ($\\pm$ 0.004) |\n\n[1] Han Q, Yang L, Chen Q, et al. A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming. ICLR, 2023."}]

Author rebuttal:
Dear reviewers,

We sincerely thank all reviewers' insightful and constructive comments, which helped to significantly improve our work. We respond to the comments given by each reviewer in detail, and in this global response,  we answer several key issues raised by multiple reviewers.

**1. Contribution & Novelty**

- **Task setting.** 

  **MILP generation is much harder than SAT generation because it involves not only topological structure prediction, but also precise numerical prediction.** Specifically, SAT instances can be modeled as homogeneous bipartite graph (i.e., graphs without edge or node features), so current SAT generation techniques merge graph templates together to form new ones. These methods can hardly adapt to MILP generation tasks because they cannot determine the coefficients. 

  Nonetheless, we conduct **an additional experiment** that transfers G2SAT to a special MILP dataset, MIS, in which all coefficients are 1.0 and thus the instances can be modeled as homogeneous bipartite graphs. We apply G2SAT to learn to generate new graphs and convert them to MILPs. Results are in **Table 9** in the newly submitted PDF. The results show that G2MILP significantly outperforms G2SAT on the special cases.

- **Technique.** 

  **Our proposed masked VAE is novel and different from previous masked auto-encoder (MAE) in computer vision.** 

  - **Motivation:** MAE is an **auto-regression** method that learns to reconstruct the masked images for **representation learning**. Masked VAE, in contrast, is a **VAE** based **generative model** that aims to generate new diverse instances---instead of reconstructing the original instances---from a masked one. 
  - **Model Structure:** Masked VAE has a resample layer (Eq. 5) as well as a prior loss (Eq. 4) when training, and works in a decoder-only manner when inference. For decoder-only generation, masked VAE takes masked graphs as inputs of the decoder instead of the encoder, which is also different from MAE.
  - **Theory:** Moreover, we theoretically derive the evidence lower bound (ELOB) to incorporate the mask process (Eq. 14), which is an extension of VAE theory.

**2. Evaluation Metrics.**

- **The used similarity benchmark is based on many previous works.** The considered statistics and features are commonly used in SAT generation [1] and MILP studies [2]. Measuring similarity by computing the distributional divergences is a common practice in benchmarking graph generation models [3].
- **Beyond these similarity metrics, we also access the downstream task performance.** The results demonstrate that instances generated by G2MILP are not only realistic, but can also benefit real-world applications. Novelty and diversity are also metrics that measure generative model performance. However, these two metrics are never easy to define for MILP instances. The downstream task performance improvements imply that instances generated by MILP have sufficient novelty and diversity for real applications.
- **Measuring MILP instance quality is a hard task. Currently no strong enough metrics have been developed, and we may open up the direction.** We believe that with the development of MILP generation techniques, studies on benchmarking MILP instances will follow up, and exploring MILP space will become possible. This is in line with the development law of generative model research.

**3. We conduct an additional downstream task for a neural solver, i.e., the predict-and-search framework proposed in [4].** Specifically, [4] proposes a framework that first predicts a solution and then uses solvers to search for the optimal solutions in a trust region. We consider using generated instances to enhance the predictive model. We first train the predictive model on 100 MIS instances, and then use the generative models to generate 100 new instances to augment the dataset. The results are in **Table 14**. Bowly generates low-quality data that disturbs the model training, so that there is no optimal solution in the trust region around the predicted solution. Though both Random and G2MILP can enhance the solving framework to reduce solving time, we can see G2MILP significantly outperforms Random.

**4.  We implement a new version of G2MILP that supports modifying variables.** Specifically, in each iteration, we randomly mask a variable and use new modules to generate the objective coefficient and the variable type. We fine-tune the previous model trained on MIK to obtain a new model with a variable generation module, and test its performance on MIK. We conduct experiments with different implementations, and the results are in **Table 10** in the newly submitted PDF. In future work, we plan to implement more kinds of modifying operators to generated more diverse MILP instances.

**5. We conduct extensive experimental analysis.** 

- Different orders of masking constraints. Results are in **Table 11**.
- Performance improvements on different sizes of datasets and ratio of generated instances. Results are in **Table 13**.
- Impact of masking ratio $\eta$ on similarity scores and downstream task performance improvements. Results are in **Figure 4**.
- t-SNE visualization for baselines. See **Figure 5**.



[1] Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec. G2sat: learning to generate sat formulas. Advances in neural information processing systems, 32, 2019.

[2] Frank Hutter, Lin Xu, Holger H Hoos, and Kevin Leyton-Brown. Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence, 206:79–111, 2014.

[3] Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: benchmarking models for de novo molecular design. Journal of chemical information and modeling, 59(3):1096–1108, 2019.

[4] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, 410 and Xiaodong Luo. A gnn-guided predict-and-search framework for mixed-integer linear 411 programming. ICLR, 2023.

Meta-review: The paper proposes a deep generative model for MILP instances. The reviews agree that this novel and exciting use of generative models. Some concern was raised about the technical novelty in the underlying technology; the use of Autoencoders on graphs. However, in this case, the application domain can be argued to provide sufficient novelty. After the rebuttal, where an additional baseline and task are added, and analysis conducted, the paper received unanimous accept recommendations across 6 reviewers. This is an exciting direction for machine learning, and I am happy to recommend acceptance.
Decision: Accept (spotlight)