DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming with Feasibility Guarantee
Authors: Haoyu Peter Wang
Jialin Liu
Xiaohan Chen
Xinshang Wang
Pan Li
Wotao Yin
Venue: Accepted by TMLR ()

Abstract: Mixed-integer linear programming (MILP) stands as a notable NP-hard problem pivotal to numerous crucial industrial applications. The development of effective algorithms, the tuning of solvers, and the training of machine learning models for MILP resolution all hinge on access to extensive, diverse, and representative data. Yet compared to the abundant naturally occurring data in image and text realms, MILP is markedly data deficient, underscoring the vital role of synthetic MILP generation. We present DIG-MILP, a deep generative framework adept at extracting deep-level structural features from highly limited MILP data and producing instances that closely mirror the target data. Notably, by leveraging the MILP duality, DIG-MILP guarantees a correct and complete generation space as well as ensures the boundedness and feasibility of the generated instances. Our empirical study highlights the novelty and quality of the instances generated by DIG-MILP through two distinct downstream tasks: (S1) Data sharing, where solver solution times correlate highly positive between original and DIG-MILP-generated instances, allowing data sharing for solver tuning without publishing the original data; (S2) Data Augmentation, wherein the DIG-MILP-generated instances bolster the generalization performance of machine learning models tasked with resolving MILP problems.

Published in Transactions on Machine Learning Research (07/2024)
DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming with Feasibility Guarantee
Haoyu Wang Georgia Tech
haoyu.wang wwwteeg edu
Jialin Liu
jialin. www.aaabbbbbbn.cccoo
Damo Academy, Akābaba US
Xiaohan Chen
Damo Academy, Alibaba US
Xinshang Wang
winshang www.saaa--n...cboooooom
Damo Academy, Alibaba US
Pan Li
ponki edu
Georgia Tech
Wotao Yin
wotao, yin waliiaba-inc......mom
Damo Academy, Alibaba US
Reviewed on OpenReview: https: // openreview. net/ formm? id= BaFFR
Abstract
Mixed-integer linear programming (MILP) stands notable NP-hard problem pivotal to numerous crucial industrial applications. The development of effective algorithms, the tuning of solvers, and the training of machine learning models for MILP resolution all hinge on access to extensive, diverse, and representative data. Yet compared to the abundant naturally occurring data in image and text realms, MILP markedly data deficient, under- scoring the vital role of synthetic MILP generation. We present DIG-MILP, a deep genera- live framework adept al extracting deep-level structural features from highly limited MILP data and producing instances that closely mirror the target data. Notably, by leveraging the MILP duality, DIG-MILP guarantees correct and complete generation space as well as ensures the boundedness and feasibility of the generated instances. Our empirical study highlights the novelty and quality of the instances generated by DIG-MILP through two dis- tinct downstream tasks: (S1) We identify Data Sharing, which involves MILP solver tuning without directly sharing the original data. Experiments show that solver solution time on instances generated by Dig-MILL correlate highly positively with the original data, offering potential solution direction.; (S2) Data Augmentation, wherein the DIG-MILP-gen --geeeraeee instances bolster the generalization performance of machine learning models tasked with resolving MILP problems.
1 Introduction
Mixed integer lincar programming (MILP) is prominent problem central to operations rescarch (OR) (Achterberg & Wunderling] 2013 Wolsey 2020). It forms the basis for modeling numerous crucial industrial applications, including but not limited to supply chain management (Hugos) 2018), production scheduling (Branke al. (2015), financial portfolio optimization (Mansini et al. 2015 and network de- sign Falahy & Alani| 2017 Radosavovic et al. (2200). This article aims to answer the question: How produce series of high-qualily MILP inslances? The motivation behind this inquiry is illustrated

---

Published in Transactions on Machine Learning Research (07/2024)
through the subsequent scenarios, where the definition of "high-quality" varies based on the specific require- ments of each context.
(Scenario 1). In industry, clients from real-world business seek specialized companies to develop or fine- tune intricate solver systems (Cplex 2009; Bestuzheya et al. 2021 Gurobi 2023) for solving MILP problems. The empirical success of the systems heavily depends on well-tuned hypper-parameters for the solvers, which demands ample and representative testing cases that accurately reflect the actual cases. However, real data is often scarce during the early stages of a business. In addition, clients are typically reluctant to publish data that might encompass some specific information (e.g., schedules or contract stipulations for flight arrangement (Richards & How| 2002 Roling et al.) 2008), platform costs or audience data for ad placements /Rodríguez et al. (016)). In this scenario, the goal is to generate new instances randomly, without sensitive information, but with similar solution times across different settings. By sharing these synthetic instances with solver developers, they can refine algorithms or configurations based on these instances, thereby gaining valuable insights and potentially applying these improvements directly to real-world cascs.
(Scenario II). Beyond the development and testing of MILP algorithms by domain experts (Lawler & Wood 1966 Gamrath et al. 2015), recent efforts have explored machine learning (ML) to derive heuristic
algorithms directly from data (Khalil et al.) 2016 2017 Nair et al. 2020). The effectiveness of ML-driven methods heavily relies on the availability of extensive and representative training data (Lu et al. 2022). Given the scarcity of MILP instances compared to other data types like images or texts, there arises a necessity for instance generation. In this scenario, the objective is to augment the training data to improve the generalization performance of ML models on MILP tasks.
Both scenarios underscore the motivation to synthetically generate novel instances that resemble the limited existing MILP data. Compared with some existing methods tailored to specific problems (e.g., knapsack (Hill lt al. 2011) and quadratic assignment (Drugan 2013)), our approach focuses on a more general framework for MILP generation. We aim for our proposed method to be capable of generating instances for a varicty of problems, as long as they can be formulated as MILPs. This general-purpose MILP generator potentially has wider applications compared to more specialized solutions.
A major challenge in synthetic MILP generation is ensuring representativeness. This demands that the generated instances should closely mirror the original data in terms of scale, modeling logic (the structure of the objective and constraints), and key mathematical properties such as feasibility and boundedness.
In this paper, we are particularly interested in generating feasible and bounded MILP instances. In many applications, practitioners are required to formulate feasible and bounded MILPs; otherwise, adjustments to the formulas or numerical values are necessary. Take, for instance, the Unit Commitment problem in power grid systems. The goal is determine which power generation units should be turned on or off to meet energy demands at the lowest cost, adhering to operational constraints like minimum downtime and startup times. The problem must be feasible to ensure there is always enough generation capacity online to meet demand. An infeasible solution mcans that there is no possible combination of on/off statuses for generation units that meet the required demand. Unfortunately, a randomly generated MILP with naive approaches is likely to be infeasible or unbounded. T Given that determining the feasibility of an MILP is NP- Complete (Conforti et al. 2014 Hartmanis 1982). methods that simply generate and then discard infeasible instances are inefficient. Thus, there is clear need for generating MILPs with guarantced fcasibility and boundedness.
Existing methods for MILP generation fall short of fulfilling the criteria above. Some approaches generate new instances in an embedding space with handeraft statistics (Smith-Miles & Bowly 2015 Bowly 2019).
These methods model MILPss coefficients with simple distributions such as Gaussian, generating instances with very limited structural characters that may not be representative enough. A concurrent paper (Geng et al. 2024) with our work learn the MILP distribution over instance space with neural networks (NNs). The generated instances from Geng et al. (2024) do not enjoy cussibllity-buuddddee guarantee. By em- ploying deep neural networks (NNs) to extract the in-depth structural information, our proposed method DIG-MILP generates "representative" data that resembles the original samples without expert knowledge.
1 As noted in Section 4.1 of (Bowly al. 2020 only 37.5% of the LP instances generated by naive methods feasible and bounded, and this proportion decreases further when integer constraints are involved.
2

---

Published in Transactions on Machine Learning Research (07/)024)
Additionally, DIG-MILP leverages the MILP duality theories to ensure the feasibility and boundedness of each generated instance by controlling its primal format and the dual format of its linear relaxation having at least a feasible solution, which achieves the "feasibilty-bbouddddi of the generated data. Morcover, any Ceasible-boundee MILP is inside the generalion space of DIG-MILP, meeting the demand for "generality". An illustration of DIG-MILP's generation strategy is shown in Figure. D Recog- nizing the limited original data along with the re- quirements on scalability and numerical precision in MILP generation, instead of generating from scratch, DIG-MILP iteratively modifies parts of ex- isting MILPs, allowing control on the degree of structural similarity towards the original data.
A.b,c) Des
x,y, solutton space A cocfiicient matrix
95
Ht' : feusiblo-bounded MILP
F. generation space of DIG-MILP
H. MILP
We conduct two rownstream lasks to validate the in-
Figure 1: DIG-MILP generates feasible-bounded in-
quality and novelty of DIG-MILP- stances, corresponding to the motivation of data generation in industry and in academia respectively. The first task is to measure whether the examples generated by DIG-MILP show a positive correlation in terms of the time required to solve them on the solver with the same hyper-parameetrss, compared to the original examples. Across four problems, the solution time of solver SCIP [Bsttuzhvaa et al., 2021 exhibits highly positive correlation between the DIG-MILP-generalee instances and the original data w.r.l. different apper-prrameter sets. The experiments can be viewed as a preliminary attempt to address the issue from (scenario I) using deep generative models and provide a potentially promising research direction. To completely solve the problem would require further research effort. The other task is envisioned as data augmentation, where the generated instances are used to enhance the performance of an important proxy task for exploring how neural networks (NN) solve MILP problems. Specifically, it helps assist in training NNs to predict the optimal objective values for MILP problems (Chen et al.] 2023). Models trained on datasets augmented with DIG-MILP-genee
stances that resemble the target MILP data from dis- tribution Dzy by learning to sample the coefficient ma- trix along with set of feasible solutions for both the primal format and dual format of the linear relaxation from the corresponding distribution 9z. See detailed explanations in Section.
instances demonstrate enhanced generalization capabilities.
2 Related Work
In the following, we discuss works on MILP generation and works on generative models.
In light of Hooker's proposals (Hooker
1994 1995 research on MILP generation diverges into two paths.
The first. focuses on leveraging expert domain knowledge to create generators for specific problems such as set covering (Balas & Ho 1980), traveling sales person (Pilcher & Rardin 1992 Vander Wiel & Sahinidis, 1995), graph colouring [Culberson| 2002). knapsack (Hill et al. 2011], and quadratic assignment (Drugan 2013 This specificity causes poor generalization across different problems and thus fails to meet the generality criterion. In contrast, the second path aims at generating general MIL.ss. Asahiro et al. (1996) propose to generate completely random instances, which is inadequate for producing instances with specific distributional features (Hill & Reilly) 2000). [Bolly (2019); Bowly et al. (2020) attempt to sample feasible instances similar to target data by manually controlling distributions an embedding space. Its manual fcature extraction and statistic control by simple distributions leads to instances with limited structural characteristics. A concurrent work Geng al. (2024) adopts NNs to further improve the expressive capability of the instance generator in Bowlyy (2019) and thus achieves more similar instances, yet the framework does not produce instances with generates instances from the solution space and uses DNNs to dig out more details, aiming to delineate the structural attributes more precisely and generate feasible-bounded instances.
guarantees. Inspired by Boolly 2019)) DIG-MILP
Recent years have witnessod the fast development of generative models, such as GAN Creswell et al. (2018) VAE Kipf & Welling (2016), and diffusion models Ho al. (2020): Song & Ermon (2019). Considering the training complexity, and the strongly-structtueed MTLP instances, we adopt VAE as the generative backbone
3

---

Published in Transactions on Machine Learning Research (07/2024)
in this paper, and we leave the utilization of more advanced generative models with potentially higher training computational cost as feature direction to explore.
3 Methodology
We start by providing a preliminary background on MILP generation. Subsequently, we discuss the theo- retical foundation based on which DIG-MILP's generation strategy ensures the feasibility and boundedness of its generated instances. Finally, we delve into the training and inference process DIG-MILP along with neural network architecture.
3.1 Preliminaries
Given a triplet of coefficient matrix A E R=xx, right-hand side constant b E R", and objective cocfficient C R", an MILP is defined as:
MILP(A,b,C): max e n, s.t. A A b, E E
(1)
To solve MILP is to identify set of non-negative integer variables that maximize the objective function while satisfying series of linear constraints, which is NP-hard (Bulut & Ralphs 2021). Within the entire MILP space H = {[A.b b, c) A E Rm b Rm E R" many of MILP problems are infeasible (no æ satisfies all the constraints in (1b) or unbounded (the value of c x can grow indefinitely while still satisfying all the constraints). However, In real-world scenarios, MILPs derived from practical issues are often either naturally or modified to be feasible, bounded, and yield on optimal solution ? as discussed in Section Therefore, we are particularly interested in generating reasible-bundded MILPs from the space Ht' as follows:
H' = [[A.b,d)
Qmxx , CQ,.CE Q and MILP(A, b, c) is feasible and bounded.).
It's important to note that merely telling the feasibility of such a problem is NP-Complete (Conforti et al. 2014 Hartmanis 1982), and its special case (the binary case) is listed in one of the Karp's 21 problems (Karp) 2010 Thus, the task of reliably generating MILPs from H' is far from trivial.
Suppose a target MILP dataset that models a particular business scenario is sampled from a distribution Dr (A, b, e) defined H', the task of MILP instance generation to approximate the distribution Di and sample novel MILP instances from it.
3.2 DIG-MILP with Feasibility Guarantee
An intuitive idea for MILP generation is to directly sample [A, b, cl from Die, which practically hard to implement as it's hard to guarantec the generated instance be bounde.
According to MILP duality theories, we observe that as long DIG-MIT.P ensure that generated instance's primal format MILP(A, b, c) and the dual format of its linear relaxation DualLP b, c) (as defined in Equation. both have at least one set of feasible solutions, then the newly generated instance will be guaranteed to be bruuddle-bouded (as proved in Proposition.
DualLP(A.b,c)) min D y, s.t. A 2 0,
(2)
To guarantee the existence of feasible solutions to both problems, inspired by (Bowly 2019 sample the instances from another space F, where
propose to
F aA y 8, A @mxn x
2 y E Q E 2n E QTh .
Definitions of boundedness, feasibility, and optimal solution of MILP in Definition. 12 in the appendix. Narrowing from the real domain to the rational domain is common in MILP studies to avoid cases where an MILP is feasible and bounded but lacks an optimal solution Schrijver) (1998). For example, min v32i s.t. /301-1 2 0, 2 1, 6 72 No feasible solution has objective equal zero, but there feasible solutions with objective arbitrarily close zero.
4

---

Published in Transactions on Machine Learning Research (07 (07/2024)
1
-x+r=
b2
4
by
04
object
feature
constraint nodes:
y // .... Vm
C= (cm
r [11 ...,
21 Y1
+
+
Y4
variable nodes:
2 .1,.... In
y2
+
Ny-s=c
V= {'
8 y 8n
edge
non-zery weights in A
Figure 2: An example of bipartite graph representa- tion with 4 nodes in set C and 3 nodes in set V.
Table 1: Nodes and edges' attributes in G.
F defines an alternative space to represent feasible-bounded MILPs, with each element. [A, æ. y, 8, r consist- ing of the coefficient matrix along with a set of feasible solutions æ, y to MILP(A, b, c) and DualLP b, c), respectively, where b, are determined by the corresponding slacks 8, r via the equalities defined in Equa- tion. [ By leveraging this idea, DIG-MILP aims to learn distribution GF over the space of ,F to sample [A, ær, y, 8, r), which can be further transformed into [A, b, that defines an MIL. problem based on Equa-
tion. !
Slack Variables: Ar r y - = where 2 S Q
(4)
Such a generation strategy offers theoretical guarantees on the boundedness and feasibility of the gener- ated instances, ensuring the bombbitttybbuumddneessss of the produced data. Moreover, all the feasible and bounded MILPs in H' correspond to at least a tuple [A, æ, y, s. In other words, generating tuples in the form of a, y, s, r) instead of generating [A, b, cl directly is general approach for producing feasible and bounded instances. This is formally stated in Proposition. [ See detailed proof in A.1 in the appendix.
Proposition 1 (Boundedness and Feasibility Guarantee of DIG-MILP). Denole H" the DIG- MIL.P-generating space:
H = [A Ax + T A
It holds that this generating space exactly equal to H': H" = H'.
3.3 Generation Process and Architecture
Having shown the equívalence between spaces F and H', we then present how DIG-MILP learns a distribution GF to sample [A, x. y, r) from. The key concept is follows: We first conceptualize [A, x. y. r] as bipartite graph, thus transforming the generation of these elements into graph generation problem. To train a model capable of generating such graphs, we employ an autoregressive method: iteratively removing a node from the graph, and then using a neural network to predict and restore the removed node's edges and attributes. During inference, we randomly select and remove a node from the current graph, and then use the trained neural network reconstruct it. This process is repeated to generate a new graph.
Graph Representation. Here, we detail the representation of [A, σ. y, s, r| variable-constraint (VC) framework, denoted graph G(V,C,)) Inspired by [Gasse et al., 2019), we treat cach MILP variable as node in V, labeled uy, where j= 1, -.. .n. The j-th element in x and 8, Ij and 8j. are altributes associated with node vy. Similarly, each MILP constraint is represented as a node in C, denoted by G₁ with = 1,2,.... ... m. The elements y and r, are attributes linked to node c, An edge ei in & connects a variable node "2 V to a constraint node a; C if the coefficient a, in the matrix A is non-zero, indicating that the j-th variable contributes to the i-th constraint of the system Ax < b in MILP 1. Therefore, A can be considered as the adjacency matrix of graph G. Figure illustrates this graph
bipartite graph within
5

---

Published in Transactions on Machine Learning Research (07/2024)
Encoder 4áb
decoder Po
Training
reconstructed G
p(G']G)
incomplete G'
V-C bipartite graph G
samphing
Z
decoder Po
standard Gaussian
Inference
repeat ( times
new instance G
The training and inference pipeline of DIG-MILP. In each training step, DIG-MILP removes a random constraint node, its connected edges, along with the solution and slack features on all the nodes, resulting an incomplete graph G'. The training objective of DIG-MILPP is reconstruct G from G' and sampled by the encoder qá- As to inference, DIG-MILP employs an auto-regressive approach, generating new instances by iteralively modifying the existing MILPs.
Figure 3:
representation with a 4 example. The attributes of nodes and edges are detailed in Table. [ With this graph representation, transform the MILP generation problem into graph generation task.
Generation pipeline. We display the training and inference pipeline in Figure. As illustrated in Algorithm. L on each training step of DIG-MILP, we randomly select and remove constraint node G (corresponding to the i-th constraint) from the bipartite graph, along with all its connected edges (c)) Concurrently, we erase the features of the solution space æ, y, 8, r on all the nodes, resulting in an incomplete graph G' (C(C V= (c)() The training objective is learn DIG-MILP to reconstruct G from the given G' by maximizing the log likelihood:
arg max EG Eo log 0 0,6
(5)
where G(G' denotes the aforementioned process of randomly removing node and it's connected edges to obtain the incomplete graph. We adhere to standard VAEs (Kingma & Welling 2013 Kipf & Welling, 2016) and introduce latent variable j.,, with the assumption that independent with G" Ctilizing ELBO, we endcavor to maximize the training objective through the optimization the following loss function:
( min Le.s EG-DEer [aBr Pog po =)] + (xxlla(H(G)))M(0 8.0
(6)
where the decoder p adeptly reconstructs graph G based on z and the incomplete graph G'; the encoder y to depict the posterior distribution of z. The hyper-parameter a functions as a balancing factor. See detailed derivation in A.2 in the appendix. During training, DIG-MILP modifies one constraint of an instance at time. During inference, the graph rebuilt after removing constraint can be fed back input, allowing iterative modifications to the original data. The number of iterations controls the degree of structural similarity to the original problem. The inference procedure is shown in Algorithm. 2 where 7/C denotes the number of iterations to remove constraint.
Neural Network Architecture For both the encoder and decoder, we employ the same bipartite graph neural networks (GNN) as the backbone. The encoder as follows:
(z II go (z.
9o(2.| NNus (.
RECUV
where zu is conditionally independent with each other on G, h GG) denotes the node embeddings of G outputted by the encoder backbone, p& and Eg are two MLP layers that produce the mean and variance

---

Published in Transactions on Machine Learning Research (07/2024)
for the distribution of z. The decoder connects seven parts conditionally independent the latent variable and node representations, with detailed structure as follows:
po (o 2) po( lh zc:: II
(o(e(c,
zv)
II uEVio(G,,u=1
polweilhy zv)
NEV
(8)
po yuu he =c) zc)po 3 zc) wEC
II
po ( u 2zy)po ny zv), wEV
II
where ze, hg denotes the latent variable and node representations on side C, while zy, h signifies those side V; de; predicts the degree of the deleted node qū e(c,,) denotes the probability of edge between G and node on side V: We, is the edge weights connected with c;: y, S,T are value of the solution and slacks. We use separate MLPs to model each part's prediction as a regression task. We optimize each part of the decoder with the Huber Loss (Huber 1992). See Section. B.2 in the appendix for more details.
Algorithm DIG-MILP Training
Algorithm 2 DIG-MILP Inference
Require: dataset D, epoch N, batch size B
Require: dataset D, batch size B, constraint re-
Solve MILPs for {- y, s, r|} over D
place rate
2: Encode MILPs into graphs
C())
1: Solve MILPs for ((r, v, s. over D
3: for epoch=1.....N do
2: Encode MILPs into graphs (G(V,,,8)
4: Allocate empty batch B 3
3: Allocate empty batch B B+0
5: for idx=I,..,,B do
4: for id= do
G~ G' "p>p(GG'( B B B+BU((GGG")
5: G~ D
6: for (-1 1-1,,..,7(C do
Encode (2
G' C'mp(G''
9:
Decode G ~ pa (G
8:
2 ~~0(0111
10: Calculate Lo (G, G')
Decode G ~ Go G+G
9:
11: end for
10:
12: Co.s f 1 LiGGGyEB Lo (o G*)
11:
end for
13: Update Φ, by minimizing La.
12:
B BUG
14:
end for
13:
end for
15:
return 0,6
return new instance batch B
4 Numerical Evaluations
In this section, we first delineate the experimental setup. Then we calculate the structural statistical simi- larity between generated and original instances. Subsequently, we evaluate DIG-MILP with two downstream tasks: (i) MILP data sharing for solver tuning and (tt) MILP data augmentation for ML model training.
4.1
Settings
Datasets: We perform DIG-MILP on four MILP datasets, encompassing scenarios involving simple and com- plex instances, a mix of small and large problem scales, varying instance quantities, and generation/colle collection from both synthetic and real-world sources. Specifically, we include two manually generated datasets, namely the set covering (SC) and the combinatorial auctions (CA), following the generation methodologies outlined in (Gasse et al. 2019). The remaining two datasets, namely CVS and ITS, are from the MIPL.BB0017 benchmark (Gleixner et al. 2021 which comprises challenging instances from a large pool of problem- solving contexts. CVS pertains to the capacitated vertex separator problem on hypergraphs, while IIS mirrors real-world scenarios and resemblles the set covering problems. Details are elaborated in Table. 2 It's worth emphasizing that for CVS and IIS, we exclusively employ the 'training' data during the training of DIG-MILP and all downstream models. The 'testing' data used only for downstream task evaluation.
We devise two downstream applications, tailored to address distinct motivations. One motivation pertains to generating and sharing data that can substitute target instances. The other motivation involves data augmentation for better training ML models.
Downstream Tasks:
https://mmpp.sb. zib. de/tad. wtt..d////a...eeccaar.....t benchnark.html

---

Published in Transactions on Machine Learning Research (07/2024)
Table 2:
Datasets Meta-data. For CVS and 11s, 'training' (non-bold) instances are for DIG-MILP or downstream model training, 'testing' (bold) instances are used in downstream testing only.
SC
CA
CVS
ITS
training
testing
training
testing
data 1000
1000
0vs08r139-94
cvs16r70-62
evs 16r89-660
cvs16r106-72
cvs16r128-89
fis-glass-cov
iis-he-cov
variable
300
1864
2112
2384
2848
3472
214
297
constraint
200
~10"2
2398
3278
3068
3608
4633
5375
9727
difficulty
easy
easy
hard
hard
(S1): Generating New Data for Solver Configuration Tuming Through this part of experiment, we offer clients a potential approach and feasible research direction for attempting to utilize deep generative models to generate new instances and hand them over to companies specializing in MILP solver tuning, In particular, we calculate the Pearson positive correlation of the solution times required by the SCIP (Bestuzheva et al. 2021) solver between the generated examples and the original testing data across various configurations. Should the solution time consistently demonstrate positive correlation between the original and generated problems across varied parameter settings, it implies consistent level of the elfectiveness on the original and new instances under the same parameter configuration, which facilitates sharing data. for parameter tuning.
(S2): Oplimal Value Prediction via ML We train GNNs to express the optimum of the objective function in an MILP (Chen et al., 2023 2024), which serves as an important proxy task to test NN's ability in solving MILP instances. We follow exactly the experiment settings of Chen et al. 22023 2024). The only difference is that instead of picking synthetic MILP problems as in Chen et al. (2023),
formulate more
complicated and challenging datasets into MIL.P problems. We use the instances generated by DIG-MILPPas
data augmentation. For more detailed implementation, see B.6 in the appendix.
We use the open source solver SCIP (Bestuzheva et al. 2021 with its Python interface, namely PySCIPOpt (Maher et al.] 2016b) for all the experiments. We consider two approaches as our baselines. The first, named 'Bowly', aligns with [Bwlly (2019) that generates MILP instances from scratch by sampling in an embedding space based on manually designed distributions, which to the best of our knowledge, is the only existing methods that work for generating novel MILP instances. The second bascline 'random' randomizes the network's ' outputs, further validating the importance and efficacy of model training. For more implementation details of the baselines, please refer to B.3 in the appendix.
Solvers and Baselines:
4.2 Results and Analysis
It's shown that the instances generated by DIG-MILP share higher similarity with the original instance structures compared to baselines, for the statistical structural evaluation between the generated instances and the original instances, please refer to Appendix. B.4 for implementation details and C.T for results.
4.2.1 downstream task #1: Generating New Data for Solver Configuration Tuning
We conduct experiments across all the four datasets. SCIP boasts an extensive array of parameters, rendering a tuning across the entire range impractical. Therefore, we adopt the reduced parameter space consistent
with mainstream research on SCIP solver tuning (Hutter et al. 2011 Lindauer & Hutter 2018 Lindauer let al. (022). See Table. 11 in the appendix for detailed parameter space selection. We employ random seed 0 44 to generate 45 distinct parameter configurations. To validate the impact of randomness on SCIP, we initiate two independent trials on the same original testing data and compare the Pearson score of solution time. As illustrated in the diagonal of Table. 3 it clearly demonstrates very high positive correlation for two independent trials on the same data. For subsequent experiments, each is run three times independently, with results averaged to miligate randomness effects. We then compare the correlation of solution time on the original data, across different datasets, as presented in the upper triangle of Table, 3 We observe a certain degree of positive correlation between synthetic datasots SC and CA, as well as between MIPLIB datasets CVS and IIS, which reveals that the effectiveness of parameters may naturally exhibit some degree of generalization across similar problems. However, the correlation between synthetic and MIPL.BB datasets
8

---

Published in Transactions on Machine Learning Research (07 (07/2024) /024)
(a) two trials
(b) random
(7 = 0.1)
(c) random (7 0.2)
(d) random (7 = 0.3)
Bowly
ours (7 0.1)
(g) ours (7 0.2)
(h) ours (7 0.3)
Figure 4: The solution time (second) of SCIP on CVS with 45 different hyper-parameter sets.
Table 3: The Pcarson correlation cocfficient ('r) and the significance value ('D') of the SCIP solution time
under 45 different hyper-parameters on dataset-pairs.
SC
CA
CVS
IIS
SC
0.732
0.599 1.351c-5
0.115
0.088 0.561
1.058c-8
0.449
0.952
0.021
0.092
CA
p
0. 0.762e-24
0.890
0.545
0.997
0.550
CVS
p
4. 4.723e-53
9.033e-5
0.988
11S
:
p
1.563e-36
tends to be much lower, underscoring the necessity of generating new instances for solver tuning specific problems. Finally, we compare the positive correlation of solution time between the generated instances and the original testing instances of the same datasets, as shown in Table. 4 Across all four datasets, the DIG- AlLL--generate instances, exhibit the highest correlation with the testing data compared to the baselines, with the lowest p-value of significance. The correlation between solution times for real and synthetic instances was lower for the CVS and IIS datascts compared to CA and SC. This difference primarily stems from the availability of training data: CA and SC each had substantial training data, with 1000 instances for each task, while CVS and 11S, which derived from MIPLIB, had significantly fewer instances (CVS had only 3 and IIS had just 1 for training). Generating synthetic instances from the given data requires capturing the underlying distribution information, which is typically more challenging when working with limited samples. We visualize the correlation of solution time between the original testing data and the generated data on the CVS in Figure.
| More detailed implementation and the visualization of the other datasets can found in B.5 and Figure. the appendix.
4.2.2 downstream task #2: Optimal Value Prediction via machine learning
We conduct experiments for the second downstream task on all four datasets. It is important to note that the dataset used to train the DIG-MILP model for generating new samples is the same dataset used to train the neural network for optimal value prediction without data augmentation. This ensures that the DIG-MILP model not exposed to any additional data beyond what the neural network receives, thereby maintaining the fairness of the experiment.

---

Published in Transactions on Machine Learning Research (07/2024)
Table 4: The Pearson correlation coefficient ('r') and the significance value ('D) of the SCIP solution time on the SC, CA,
between generated data and the original testing data under 45 different CVS, and ITS problems.
CA
CVS
1IS
-0.018
01688
-0.158
0.292
Bowly
0.751
2. 2.295e-7
0,298
0.051
ratio
0.30
0.20
0.30
0.10
0.20
0.30
0.10
0.20
0.30
0.10
0.20
0.30
0.723
0.563
0.615
0.542
0.508
0.009
-0.065
-0.337
40:201
0.114
0.182
0.149
random
p
1.971=8
5.522e-5
2.942e-4
1.174e44
4.535e-5
9.028e-6
0.021
0.184
0.452
0.228
0.527
0.728
0.771
0.780
0.747
0.717
0.665
0.609
0.590
0.607
0.542
0.300
0.561
1.446c-8
5.371c-10
2.544c-10
3.648c-9
2.908c-8
6.353e-7
8.834c-6
1.986c-5
9.581c-6
1.187c-4
0.044
8.497e-5
Table 5:
The relative mean square error (MSE) of the optimal objective value task on the set covering (SC) #14 are identical.
problem. The 500 original instances in training dataset #2
out-of-ditrrbutioon
in-distribution
datasct
#original
#generated
replace ratio
0.03
0.04
0.05
0.10
0.15
0.20
0.25
0.30
0.35
1000
0.792
0.640
0.488
0.022
0.009
0.009
0.010
0.011
0.015
500
500
(Bowly)
3.498
17.671
43.795
81.408
0.037
0.052
0.052
0.065
0.045
500
500 (random)
0.10
0.449
4.176
12.624
86,592
0.048
0.064
0.053
0.069
0.045
500
500 (DIG- MILP)
0.01
0.505
0.280
0.142
0.032
0.032
0.040
0.044
0.044
0.040
500
500
DDGG-MILP
0.05
0.575
0.329
0.155
0.080
0.036
0.044
0.046
0.056
0.056
500
500
(DIG-MILP)
0.10
0.362
0.141
0.045
0.065
0.017
0.012
0.012
0.010
0.015
500
500
(DIG-MILP)
0.20
0.625
0.418
0.265
0.034
0.059
0.083
0.077
0.099
0,069
500
500
(DIG-MILP)
0.50
0,884
0,822
0.769
0.285
0.017
0.025
0.033
0.047
0.032
9
500
0,868
0.758
0.637
0.072
0.016
0.014
0.014
0.017
0.027
10
500
50 (DIG-MILP)
0.10
0,693
0,497
0.327
0.031
0.035
0.039
0.046
0.039
0.052
500
100 (DIG-MILP)
0.10
0,603
0,361
0.179
0.096
0.031
0.033
0.038
0.042
0.038
12
500
200 (DIG-MILP)
0.10
0.628
0.396
0.215
0.086
0.038
0.035
0.039
0.043
0.039
13
500
500 DDG-MILP
0.10
0.362
0.141
0.045
0.065
0.017
0.012
0.012
0.010
0.015
14
500
1000 (DIG-MILP)
0.10
0.473
0.211
0.063
0.339
0.013
0.014
0.014
0.014
0.024
Set Covering (SC) We select 'density' as a metric of the SC instance distribution, which represents the number of sets to be covered within a constraint. We only include densities ranging from 0.15 to 0.35 in the training set (for both DIG-MILP and the downstream predictor). We present in-distribution test set (0.15 to 0.35) as well as dustof-disttibuution test sets with densitics falling within the uncxplored range of 0.03 to 0.10, to reflect the predictor's is ability to generalize across distribution shift. The relative mean squared error (MSE) values of the models' predictions are presented in Table. 5 In the upper rows (Datasets # #-8#8), we fix the size of training set as 1000. Dataset #1 consist of 1000 original data, dataset #2 consists 500 original with 500 instances generated via the 'Bowly', #3 uses the 'random' baseline. Datasets #4-#8 comprise a combination of 500 original instances and 500
MML.--geeerteeed instances, with various constraint node replacement ratios y ranging from 0.01 to 0.50. Models trained exclusively on in-distribution data exhibit superior fitting and predictive accuracy within the in-distribution lest. sets. However, models trained on a combination of original and DIG-MILP --g-era-geeerrtted instances display significantly enhanced prediction accuracy on out-of- distribution testing data. We attribute this phenomenon to the increased structural and label diversity in the newly generated instances, mitigating over-fitting on in-distribution data and consequently bolstering the model's cross-distribution capabilities. It's worth noting that 'Bowly' or 'random' neither enhances the model's in-distribution nor out-of-distributtin performance. We believe this is due to the less precise representation of the target distribution by the mamnally-desiguee 'Bowly' baseline and the excessively high randomness 'random', causing the generated instances to deviate substantially from the original problems in both solution space and structure. In the lower rows (Datascts #9-#14), we investigate the impact of progressively incorporating DIG-MILP-generalee original instances. We observe a consistent improvement in model performance with the gradual inclusion of additional newly generated instances, with peak performance achieved when augmenting the dataset with 500 newly generated instances.
instances into the dataset, initially starting with 500
Combinatorial Auctions (CA) We set the number of bid/item pairs that determines the quantity of variables and constraints as the parameter for distribution shift. Our training set only comprises examples with bid/item values ranging from 40/200 to 80/400, our testing set also introduces instances with bid/ values ranging from 40/200 to 160/800. The relative mean squared error (MSE) of the model's predictions
10

---

Published in Transactions on Machine Learning Research (07/2024)
Table 6: The relative mean square error (MSE) of the optimal objective value task on the combinatorial auction (CA) problem. The 500 original instances in training datasct #2 # are identical.
in-distribution
ont-of-distrlbmtion
dataset
#original
#generated
replace ratio
40/20
60/300
80/ 80/400
100/500
120/ 660
140/700
160/800
1000
0.246
0.003
0.060
0.155
0.239
0.312
0.379
500
500
(Bowly)
0.202
0.004
0,080
0.183
0.272
0.346
0.410
500
500 (random)
0.10
0.242
0.006
0.077
0.179
0.269
0.347
0.409
500
500
EDIG-MIL.R
0.01
0.346
0.008
0.043
0.131
0.219
0.292
0.359
500
500
(DIG-MILP)
0.05
0.345
0.009
0.041
0.125
0.211
0.284
0.352
500
500
(DIG-MILP)
0.10
0.385
0.015
0.036
0.118
0.201
0.276
0.340
500
500
(DIG-MILP)
0.20
0.428
0.019
0.035
0.116
0.203
0.275
0.344
(DIG-MILP)
0.381
0.012
0.040
0.126
0.289
0.356
500 (DIG-MILP)
0.014
0.035
0.117
0.276
0.344
10
500
0.216
0.004
0.068
0.165
0.249
0.324
0.388
11
500
50 (DIG-MILP))
0.10
0.382
0.006
0.040
0.130
0.218
0.293
0.361
12
500
100 (DIG-MILP)
0.10
0.446
0.014
0.031
0.116
0.201
0.275
0.344
13 500
500 (DIG-MILP)
0.10
0.385
0.015
0.036
0.118
0.201
0.276
0.340
14
500
1000 (DIG-MILP)
0.10
0.359
0.009
0.039
0.126
0.212
0.285
0.351
is provided in Table. The experiments are also divided into two parts. The upper rows (Datasets #1-#8) yields similar conclusions, where models trained solely on original data excel in fitting within in-distribution test sets, models trained on a mixture of half original and half DIG-MILP- --g-rrr-ggeee instances perform better on test sets at scales never encountered during training (bid/ilem ranging from 100/500 to 160/800) This observation is attributed to the diversity introduced by the generated instances, in terms of both the problem structure and optimal objective labels, that prevents the models from over-fitting and thereby enhance their generalization across scales. Consistent with the SC, the second part demonstrates the impact of gradually increasing the new instances as training data and also achieves the peak performance with 500 newly generated instances.
CVS and IIS Experiments on CVS and IIS show similar insights, see Appendix.
C.2 for details.
5
Conclusion
This paper introduces DIG-MILP, a deep generative framework for MILP. Contrasting with conventional MILP generation tochniques, DIG-MILP does not rely on domain-specific expertisc. Instead, it employs DNNs to extract profound structural information from limited MILP data, generating "representative" in- stances. Notably, DIG-MILP guarantees the feasibility and boundedness of generated data, ensuring the data's "autheticity". The generation space of DIG-MILP encompasses any feasible-bounded MILP, making it general framework for generating beunddle-bounedd MILPs. Experiment evaluations highlights DIG- MIL.P's potential in (S1) MILP data sharing for solver hyper-parameter tuning without. publishing the original data and (S2) data augmentation to enhance the generalization capacity of ML models tasked with solving MILPs. As infeasible or unbounded problems are also important, particularly in testing the robust- ness of MILP solvers. Therefore, exploring the generation of these types of instances represents a promising direction for future rescarch.
References
Tobias Achterberg and Roland Wunderling. Mixed integer programming: Analyzing 12 years of progress. Facets of combinatorial optimization: Festschrift for martin grötschel, pp. 449 481. Springer, 2013.
Naser Al-Falahy and Omar Y Alani. Technologies for 5g networks: Challenges and opportunities. It Profes- sional, 19(1):12 20, 2017.
Yuihci Asahiro, Kazuo Iwama, and Eiji Miyano. Random generation of test. instances with controlled at- tributes. Cliques, Coloring, and Satisfibbility, pp. 377-393, 1996.
Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient opti- mization: compulational study. Springer, 1980.
11

---

Published in Transactions on Machine Learning Research (07/2024)
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. orXiv preprint arXiv:1308.3432. 2013.
Dimitris Bertsimas and John Tsitsiklis. Introduction to linear oplimization, volume Athena scientific Belmont, MA, 1997.
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalon, Lcon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, et al. The scip optimization suite 8.0. arx preprint urXiv:211.00887, 2021.
Simon Bowly, Kate Smith-Miles, Davaatseren Baatar, and Hans Mittelmann. Generation techniques for linear programming instances with controllable properties. Mathemalical Programming Compulalion, 12 (3):389 415, 2020.
Simon Andrew Bowly. Stress testing mixed integer programming solvers through new test instance generation methods. PhD thesis, School of Mathematical Sciences, Monash University, 2019.
Juergen Branke, Su Nguyen, Christoph W Pickardt, and Mengjie Zhang. Automated design of production scheduling heuristics: review. IEEE Transactions on Evolutionary Compulation, 20(1):110 124, 2015.
Aykut Bulut and Ted K Ralphs. On the complexity of inverse mixed integer linear optimization. SIAM Journal on Oplimizalion, (14):30014 3004-3033, 2021.
Richard H Byrd, Alan J Goldman, and Miriam Heller. Recognizing unbounded integer programs. Operalions Research, 35(1):140 142, 1987.
Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear programs by graph neural networks. International Conference on Learning Representations, 2023.
Ziang Chen, Jialin Liu, Xiaohan Chen, Xinshang Wang, and Wotao Yin. Rethinking the capacity of graph neural networks for branching strategy. arXiv preprint arXiv:2402. 07099, 2024.
Michele Conforti, Gérard Cormuéjols, Giacomo Zambelli, Michele Conforti, Gérard Cormuéjols, and Giacomo Zambelli. Integer programming models. Springer, 2014.
IBM ILOG Cplex. V12. 1: User's manual for cplex. International Business Machines Corporation, 46(53): 157, 2009.
Antonia Creswell, Tom White, Vincent Dumoulin, Kai Arulkumaran, Biswa Sengupta, and Anil A Bharath. Generative adversarial networks: An overview. IEFE signal processing magazine, 35(1):53 65, 2018.
Culberson. A graph generator for various classes of k-colorable graphs. URL http://weebdocs. es. walberta. ca/" joe/jee/eoo
html, 2002.
Mädälina M Drugan. Instance generator for the quadratic assignment problem with additively decomposable cost function. In 2013 IEEE Congress Evolutionary Compulation, pp. 2086 2093. IEEE, 2013.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint ar Xtx::1900.00 024228 2019.
Gerald Gamrath, Thorsten Koch, Alexander Martin, Matthias Miltenberger, and Dieter Weninger. Progress in presolving for mixed integer programming. Mathematical Programming Compulation, 7:367-398, -98,, 2015.
Maxime Gasse, Didier Chételat, Nicola. Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in newral information processing systems, 32, 2019.
Zijie Geng, Xijun Li, Jie Wang, Xiao Li, Yongdong Zhang, and Feng Wu. A deep instance generative framework for milp solvers under limited data availability. Advances in Neural Information Processing Systems, 36, 2024.
12

---

Published in Transactions on Machine Learning Research (07/2024)
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data-driven com- pilation of the 6th mixed-integer programming library. Mathematical Programmingg Computation, 13(3):
443-490, 2021.
Gurobi. Gurobi Optimizer Reference Manual, 2023. URL attps://www.gnt com
Juris Hartmanis. Computers and intractability: guide to the theory of np-completeness (michacl r. garey and david s. johnson). Siam Review, 24(1), 1982.
R Hill, JT Moore, C Hiremath, and YK Cho. Test problem generation of binary knapsack problem variants and the implications of their use. Int. J. Oper. Quant. Manag, 18(2):105 128, 2011.
Raymond R Hill and Charles H Reilly. The effects of coefficient. correlation structure in two-dimensional knapsack problems on solution procedure performance. Management Science, 46(2):302 317, 2000.
Jonathan Ho, Ajay Jain, and Picter Abbecl. Denoising diffusion probabilistic models. Advances in neural
information processing systems, 33:6840 6851, 2020.
John N Hooker. Needed: An empirical science of algorithms. Operations research, 42(2):201-212, 1994.
John N Hooker. Testing heuristics: We have all wrong. Journal of heuristics, 1:33-42, 42, 1995.
Peter J Huber. Robust estimation of location parameter. In Breakthroughs in statistics: Methodology and Springer, 1992.
distribution, pp.
Michael H Hugos. Essentials of supply chain management. John Wiley & Sons, 2018.
Frank Hutter, Holger Hoos, and Kevin Leyton-Brown. Sequential model-based optimization for general algorithm configuration. In Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5, pp. 507 523. Springer, 2011.
Eric Jang, Shixiang Gu, and Bon Poolc. Categorical reparamctcrization with gumbel-softmax. arXiv preprint arXiv:1611.0114. 2016.
Richard M Karp. Reducibilily among combinatorial problems. Springer, 2010.
Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 30, 2016.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1412. 6980, 2014.
arXiv preprint
Diederik P Kingma and Max Welling. Auto-cncoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
Thomas N Kipf and Max Welling, Variational graph auto-encoders, arXiv preprint arXiv: 2016.
Eugene Lawler and David Wood. Branch-and-bound methods: A survey. Operalions research, 14(4): 699 199-719, 1966.
Marius Lindauer and Frank Hutter. Warmstarting of model-based algorithm configuration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp. Difan Deng, Carolin Ben- jamins, Tim Ruhkopf, René Sass, and Frank Hutter. Smac3: A versatile bayesian optimization package for hyperparameter optimization. The Journal of Machine Learning Research, (3(1):2475 22652,243,-- 2022.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Han Lu, Zenan Li, Runzhong Wang, Qibing Ren, Xijun Li, Mingxuan Yuan, Jia Zeng, Xiaokang Yang, and Junchi Yan. Roco: A general framework for evaluating robustnesss of combinatorial optimization solvers on graphs. In The Eleventh International Conference on Learning Representations, 2022.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint ar 11::11611.0001,, 2016.
Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Fe- lipe Serrano. PySCIPOpt: Mathematical programming in python with the SCIP optimization suite. In Mathematical Software- ICMS 2016, pp. 301-307. Springer International Publishing, 2016a. doi: 10.1007 01000779977-333194244222 37.
Stephen Maher, Matthias Miltenberger, João Pedro Pedroso, Daniel Rehfeldt, Robert Schwarz, and Felipe Serrano. Pyscipopt: Mathematical programming in python with the scip optimization suite. In Mathemat- tcal Software ICMS 2016: 5th International Conference, Berlin, Germany,, July 11-14, 2016, Proceedings 5, pp. 301- 1071-07.0000 Springer, 2016b.
Renata Mansini, odzimierz Ogryczak WL, M Grazia Speranza, and EURO: The Association of European Op- erational Research Societies. Linear and mixed inleger programming for portfolio oplimization, volume 21. Springer, 2015.
Robert R Meyer. On the existence of optimal solutions to integer and mixed-integer programming problems. Mathematical Programming, 7:223 235, 1974.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 19349, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances neural information processing systems, 32, 2019.
Martha G Pilcher and Ronald L Rardin. Partial polyhedral description and generation of discrete optimiza- tion problems with known optima. Naval Research Logistics (NRL), 39(6):839-88) 858, 1992.
Ilija Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár. Designing network design spaces. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 10428 10436, 2020.
Arthur Richards and Jonathan P How. Aircraft trajectory planning with collision avoidance using mixed integer linear programming. In Proceedings of the 2002 American Control Conference (IEEF Cal. No. CH37301), volume 3, pp. 1936 1941. IEEE, 2002.
Tsmael Rodríguez, Fernando Rubio, and Pablo Rabanal. Automatic media planning: optimal advertisement placement problems. In 2016 IEEE Congress Evolutionary Computation (CEC), pp. 5170 5177. IEEE 2016.
Paul C Roling, Hendrikus G Visser, et al. Optimal airport surface traffic planning using mixed-integer linear programming. International Journal of Aerospace Engineering. 2008, 2008.
Alexander Schrijver. Theory of linear and integer programming. John Wiley Sons, 1998.
Kate Smith-Miles and Simon Bowly. Generating new test instances by evolving in instance space. Computers & Operations Research, 63:102 113, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in newral informalion processing systems, 32, 2019.
Russ Vander Wiel and Nikolaos Sahinidis. Heuristic bounds and test problem generation for the time- dependent traveling salesman problem. Transportation Science, 29(2):167-188)) 1995.
14

---

Published in Transactions on Machine Learning Research (07 (27/2024)
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Ev- geni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, Îlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261 272, 2020. doi: 10. 10.1038 10.1038/s41592- L0L-3///-11592019--006666 019-0686-2.
Laurence A Wolsey. Inleger progrumeming. John Wiley & Sons, 2020.
15

---

Published in Transactions on Machine Learning Research (07/2024)
A supplementary theoretical results
A.1 Proof of Proposition
To validate Proposition we follow the methodology outlined in Bowly 2019). Before the proof of Proposi-
tion [ we first give the definition of boundedness, leasibility and optimal solutions of MILP, then we discuss the existence optimal solutions of LP and MILP.
Definition (Feasibility of MILP). An MILP(A,b,CC c) is feasiile if there evists an a such that all the constraints are satisfied: a E Z2-- Ax - b. Such an a named a feasible solution.
Definition 2 (Boundedness of MILP). An MILP b, is bounded there's an upper bound on c across all feasible solutions.
Definition 3 (Optimal Solution for MILP). A vector xt recognized as an optimal solution if it's feasible solution and it is worse than all other feasible solutions: c cTx' x=' cJ given is feasible.
All LPs must fall into one of the following cases Bertsimas & Tsitsiklis 11997
Infeasible.
Feasible but unbounded.
Feasible and bounded. Only this case, the LP yields an optimal solution.
However, general MILP will be much more complicated. Consider simple example: min v/z1 22, s.t. 3
2 0, 2 1 E Øz0- No feasible solution has objective equal to zero, but there are feasible solutions with objective arbitrarily close to zero. In other words, an MILP might be bounded but with no optimal solutions. Such pathological phenomenon is caused by the irrational number v3 in the coefficient. Therefore, only consider MILP with rational data:
A E Q b QT C Q
Such an assumption regularly adopted the rescarch of MILP.
Without requiring to be integral, equation will be relaxed LP, named its LP relaralion:
b.( max x, A x b, x 0. 0.
The feasibility, boundedness, and existence of optimal solutions, along with the relationship with its LP relaxation, are summarized in the following lemma.
Lemma 1. Given Quaxn QTm "e Q"T, holds that
LF is infeasible, MILP(A,b,c) e) must be infeasible.
(IT) LP((A b, c) is feasible but unbounded, then MILP(A, c) must be either infeasible bounded.
(III) If LP(A,b, e) feasible and bounded, MILP(A, b, c) might be infeasible or feasible. If we further assume MILP(A, c) is feasible, it must yield an optimal solution.
Proof. Conclusion (I) is trivial. Conclusion (II) is exactly (Byrd et al. 1987 Thcorem 1). Conclusion (IIT) is corollary of (Meyer 1974 Theorem 2.1). To obtain (III), we first write MILP(A, into the following
form:
max c x. s.t. Ax + r b, 2 0. 0, æ is integral
Then the condition (v) in Meyer 1974 Theorem 2.1) can be directly applied. Therefore, the feasibility and boundedness of MTTPP(A, (A, b. c) imply the existence of optimal solutions, which concludes the proof. L
16

---

Published in Transactions on Machine Learning Research (07/2024)
With Lemma we could prove Proposition | now.
Proof of Proposition At the beginning, we define the space of [A, b, cl generated based on F as H" for simplicity.
H. [1A, c) : Ax c A y 8,
Then it's enough to show that H' c H" and H" H'-
We first show H" C H': For any [A, b, c] E H", it holds that [A, cj H'. In another word, we have to show MILP(A,b, b, c) to be feasible and bounded for all [A, cl H!" The feasibility can be easily verified. The boundedness can be proved by "weak duality." For the sake of completeness, we provide a detailed proof here. Define the Lagrangian as
C(x, y) = x y Ax)
c
Inequalities Ax < b and y 2 imply
((x,y) c.w
Inequalities A y 2 and imply
[(x, y) <by
Since Q and y Q%0 it holds that
< x S b < +x
which concludes the boundedness of MILP(A,,bc)
We then show Ht C 7²: For any MALP b, c) that is feasible and bounded, there must be u, F such that
b = Ax + r, c A y 8.
(9)
(10)
The existence æ, along with equation 9 is a direct conclusion of the feasibility of MILP b, c). Now
let's prove the existence of rational vectors y, 8, along with equation 10. Since MILP c) feasible and
bounded, according to Lemma L. LP(A, b, c) must be feasible and bounded. Thanks the weak duality discussed above, we conclude that DualLP(A, b, c) must be feasible and bounded. As long as DualLP(A, b c) has an optimal solution y that is rational, one can obtain equation 10 by regarding [y" A ATy c] as [ 8). Therefore, it's enough to show DualLP(A. b, e) has a rational optimal solution.
Define:
A' = = -1 y' yy=lyT, SJ
=b=(b.o77 _
Then DualLP can be written as standard-form LP:
min(b')T of s.t. A'y' c, 3 20 y'
(11)
As long as an LP has an optimal solution, must have a basic optimal solution Bertsimas & Tsitsiklis 1997) Specifically, we can split A' in column-based fashion A' IB', N' and split y' as y [3), vx] where
yN 0. Such y is termed basic optimal solution to the LP presented in equation 11 Therefore,
N' A'y' B'yg + N' UN B'ys= = yB (B')-'c
Since B' is a sub-matrix of A', B' is rational. Therefore, (B')-1 and ye are rational, which implics y' is rational. This concludes the existence of rational optimal solutions of DualLP, which finishes the entire proof.
17

---

Published in Transactions on Machine Learning Research (07 (024))
A.2 Derivation of the loss function
Here we show the derivation from the training objective in Equation. towards the loss function in Equa- tion.
0
log IP(G)G'; Ex log 8(
Do
[z(
-o log
(=(=
G(z|G)
po 2))G',2))(22
+ E EE Bog l (0(2
(12)
E log
(o(z]G)
p(z|G)
Ex c) log Pa
> Eg Exwgo (= G) log pa (G x)] [
and thus we have
E paora log ((G(''' Lo,s
(13)
B supplementary implementation details
B.1 Hardware, Software and Platforms
At the hardware level, we employ an Intel Xeon Gold 6248R CPU and a Nvidia quadro RTX 6000 GPU, For tasks that exclusively run on the CPU, we utilize a single corc, for tasks that run on the GPU, we set the upper limit to 10 cores. On the software side, we utilize PyTorch version 2.0.0+cu117 (Paszke et al. 2019) and PyTorch Geometric version 2.0.3 (Fey & Lenssen 2019). We utilize PYSCTPOpt solver version 3.5.0 [Maher et al., 2016a) for optimization purposes with default configurations.
B.2
Implementation of DIG-MILP
For both the encoder and the decoder, we adopt the bipartite GNN exactly the same as that Gasse et al. 2019 as their backbones, the original codes for the backbone publicly available
Encoder To obtain the latent variable samples, we feed the encoder with G encoded as per the method in Table. 1 then incorporate two distinct multi-layer perceptron (MLP) layers following the backbone to output the mean and log variance of the latent variable z. During the training process, use the re- parametrization trick (Bengio et al.] 2013 Maddison et al. 2016 Jang et al. 2016) to render the process of sampling from the mean and variance differentiable. During inference, we directly sample z ~ (0,
Decoder We feed the backbone of the decoder with the in- complete graph G' to obtain the latent node representations he' ( h The backbone is then followed by seven distinct heads conditionally independent on h and z, each cor- responding to the prediction of: 1) the degree of the removed node de,, 2) the edges e(c,, u) between the constraint node and the nodes in the other side, 3) the edge weights We, and 4) 7) the value of x, y. r, of the new graph G. Each head is composed of layers of MLP, and takes different combinations G G as inputs, which is illustrated in Table. 7 We perform min-max normalization on all the variables to predict according to their maximum and minimum value occurred in the training dataset. Each part is modeled as regression task, where we use the Huber Loss Huber 19922)
Table 7: The last layer design of decoder. prediction embbediing d, e, x, h Zu, U E V h Zo, C CCC
y. 8
the criterion for each part and add them together as the total loss for decoder.
For the case of binary MILP problems, their primal, dual and slack variables could be written in the form as Equation.
14 15
16
18

---

Published in Transactions on Machine Learning Research (07 (07/2024) /024)
Primal (Binary)
Dual (Binary)
Slack (Binary)
(Lincar Relaxation)
max c x
a
A + r = b
s.t. An v
(14)
[b 11
(15)
(16)
A fly = c
a S
s.t.
[ T
r 2 0
y 2 0
8 2 0
Considering the inherent structure of binary MILP, can further decompose the dual solution y into two parts: y1 (corresponding to regular constraints Ax S b) and y/2 (corresponding to constraints a: S 1). The encoding of binary MILP problem into a bipartite VC graph is illustrated in Table. S And the decoder
could be models as Equation. 17
Pe(G) z) = po(dd, lhg ( #c.) II pole(c, u)lh zv)
II
Po(we, Ih zvv
NEV
ue vEVre(eta)=1
(17)
II MEC
(o hi =c)po(r 1h zc) II po (z (h py)po ny ;2z) 1h .v),
WEV
where the decoder of DIG-MILPP specifically designed for binary MILP partitions the predicted dual solution y into two segments yı y/2 and predict each segment separately.
Table V-C encoding binary MILP.
object
feature
constraint
all 0's
node
91 = -y-1.. 9im
C= cm
$m
all I's
variable
x {1 En
node
8 Tr....
V = {VI...,.
3/2
Y211.. ... 32n
edge non-zero weights in A
Hyper-parameters Across the four datasets, set the same learning rate for DIG-MILP le - 3. We use the Adam optimizer [Kingma & Ba 2014). For the SC, we set the a in Le.s as 5, for the CA, the CVS, and the IIS, we set a as 150. We use the random seed as 123 for DIG-MILP training across all the four datasots.
B.3 Implementation of baseline
'Bowly" Here we show the implementation of generating instances from scratch with the baseline Bowly (Bowly) 2019 The generation of matrix A is illustrated the algorithm. 3 With the generated adjacency matrix A, where we manipulate the hyper-parameten during the generation process ensure that the statistical properties of A align as closely as possible with the original dataset. Specifically, we keep the size of graph (m, n) the same the original dataset and uniformly sample p.. Pe from [0, for all the four datasets. For the other hyper-parameter settings, see Tables. 9
Then we uniformly sample the solution space æ, r with intervals defined by their corresponding maximum and minimum from the training dataset. Then we deduce b, e to get the new MILP instances.
'Random' We use exactly the same network architccture and generation process as DIG-MILP. The key difference is that instead of utilizing the trained NN, we uniformly sample the variables dey e(G,, u), Wey YI, 8, n, r, y2 required for decoder prediction within intervals delineated by the maximum
19

---

Published in Transactions on Machine Learning Research (07 (07/202) /024)
Algorithm 3 Bowly generation of matrix A
Require: n [1, 20), E (1, (0, 1..po [0, Pe Pe E [0, 1]. E (-o0, oo). aл E (0,
Ensure: Constraint matrixA E Qmxx
1: Set target variable degree d(u,) = for randomly selected i,0 for all others
Set target constraint degree d(u;) for randomly selected i,0 for all others
e e+1
while pmn do
s draw values from (0, 1)
6: f draw m values from U(,
Increment the degree of variable node i with maximum Pv d(u:) 84
a(r;) + tj
Increment the degree of constraint node j with maximum Pe e+c+11
10: end while
11: for i= l...., n do
12:
for = L,..,, m
13:
t draw from U(0, 1) if <<< d(u.)d(e,) then
14:
15:
Add edge (i.j) to VC
16: end if
17: end for
18: end for
19: while min((d(u), d(v;)) 0 do
20: Choose i from {ild(u:) = 0}, randomly if all d(u:) > 0
21: Choose j from [jld(zy) = 0}, randomly if all d(u;) > 0
22: Add edge (i,j) to VC
23: end while
24: for (i.j) E(VC) do
25: Oij N(HA,
26: end for
27: return A
20

---

Published in Transactions on Machine Learning Research (07/2024)
Table The aoper-parameter selection of the Bowly baseline.
density
PA
A
SC
((0.15, 0.20, 0.25, 0.30, 0.35)
-1
0
CA
0.05
(1001,
CVS
0.0013
0.2739 -1 0
0.961
IIS 0.0488
and minimum values of each variable from the training set, simulating the random parameters of an untrained
neural network.
B.4 Implementation of the structural statistical characteristics
The explanation of various statistical metrics used for comparing the structural similarity of MILP problem instances is detailed as shown in Table. 10 Specifie numerical values for different metrics for the SC and CA problems can be found in Table. 13 and Table. respectively.
Table 10: Explanation of the statistic metrics of the MILP instances
name
explanation
density mean
the average number of non zero values the constraint matrix
cons degree mean
the average number of constraint node degree the standard variance of constraint node degree the average number of variable node degree the standard variance of variable node degree
cons degree std
var degree mean var degree std mean std c mcan std
the average b value the standard variance of b value the average value of the standard variance of value
For each statistic metric shown in Table. 10 we begin by collecting lists the values from four data sources: the original dataset, the data generated by the 'Bowly' baseline, the data generated by the 'random' baseline, and data generated by DIG-MILP. Each data source contains 1000 instances. We then employ the lists from the four data sources approximate four categorical distributions. Utilizing the numpy.histogram function, set the number of bins to the default value of 10, with the min and max values derived from the collective minimum and maximum of given metric across the four data sources, respectively. Next, employ Jensen-Shannn (JS) divergence Dj. via the function scipy.spotiol. iiistance.jensnsshame 2020) to quantify the divergence between the original samples and the rest three data sources, resulting in score; for each statistical metric.
(Virtanen et al,
score; = (max (max))(mxxx( - min(D;.))
(18)
where max(D).), min(D)s are the maximum and minimum of JS divergence across all the metrics.
Then we average the score for each statistic metric to obtain the final similarity score, as is shown in Table. 12
score,.
(19)
B.5 Implementation of Data Sharing for Solver Configuration Tuning
Below are the that we randomly sample to test the positive-corrclation of different dataset pairs. We adhere to the configuration established in mainstream solver tuning literature to select the pa-
21

---

Published in Transactions on Machine Learning Research (07/2024)
rameters requiring adjustment Hutter et al. 2011 Lindauer & Hutter (2018 Lindauer et al. (0022) For
detailed explanation of each parameter, please refer to the SCIP documentation
Table 11: The selected SCIP hyper-parameters and the range to randomly select from.
params
whole range/choice default.
our range/choice
branching/scoreffng
8, P: q
P. 9
branching/ scorefac
[0, 1]
0.167
[0, I]
branching/ pprene/bbrrfferryyy
True, False [0,0.5] [0,1]
False
True, False
branching/ claamp
0.2
[0,0.5]
branching/ma middlll
0.75
[0.1]
branching/ nuddpullreddoommrigg
[0.1]
0.5
[0.1]
branching /pggainnormalize
d, s
1p/ pricing
1, P, 9. d [1,2147483647] (1,2147483647] d, u, p, I, 1, h [0,1]
1, a, p, 8, q. d
1p/ colagelimit
10
[0,100]
1p/ rowwageelimtt
10
[0,100]
nodeselection childsel
h
d u, I, r, h
separating/mmiorttoo
0.9
[0.1]
[0,1]
0.9
[0.1]
separating/maxcuts
separating/ maxcuts
0,2147483647
100
[0,1000]
separating/ maxcutsroot
0021147483647
2000
[0,10000]
separating/ ceeratinnncuttgeliiiig cutagelimit
(-121144483647
80
[0,200]
separating/ shaaratin/ppoofreeg poolfreq
[1,665534
10
[0,100]
B.6 Implementation of Optimal Value Prediction via ML
Neural Network Architecture In this downstream task, We also the bipartite GNN backbone which is exactly the same that in Gasse et al. (0019). We use MLP layer and global mean pooling to produce the optimal objective value prediction. The learning rate is set as le - 3.
C Supplementary Experiment Results
C.1 statistical characteristics of the generated instances
Table 12: The similarity score t between the original and generated data
constraint replace rates
0.01
0.05
0.10
0.20
0.50
Bowly random
0.337
SC
0.701
0.604
0.498
0.380
0.337
ours
0.856
0.839
0.773
0.652
0.570
Bowly
0.386
CA
random
0.630
0.566
0.508
0.432
0.306
ours
0.775
0.775
0.768
0.733
0.630
We compare the statistical metrics wetween the generated instances and the original instances on the SC and CA datasets. We do not calculate the statistics on the CVS and IIS due to their limited size that prevents mcaningful statistical comparisons. We count nine statistic metrics in total, see Table. B.4 in the appendix for details. The similarity score derived from the Jensen-Shannon (JS) divergence (the lower the better) between each metric of the generated and original data, as shown in Table. 12 'Bowly' shows the least similarity. As the the constraint replacement ratio y increases from 0.01 to 0.50, the table shows decreasing similarity between new and original instances for both DIG-MILP and 'random', aligning with our expectation of controlling structural similarity by adjusting the number of constraint nodes to replace, Instances generated by DIG-MILP more closely mirror the target data in structural statistical metrics across all For detailed calculations of the similarity score and the specific values of each statistic
22

---

Published in Transactions on Machine Learning Research (07/2024)
Table 13: Statistic value comparison across the original dataset and the generated datasets with different constraints replacement rates on the set covering (SC) problem. 'resolving time' calculates under default configuration of pySCIPopt. 'density' represents the ratio of non zero entries in the constraint matrix. 'cons
degree' denotes the degree of constraint nodes, 'var degrec' stands for the degree of variable nodes. b denotes
the right hand side vector of the MILP, and is the objective coefficient vector.
resolving
density
cons degree
cous degree
var degree
var degree
replace ratio
time (s)
mean
mean
mean
std
mean
b std
mean
std
original
0.821
0.251
100.700
8.447
50.350
6.854
-1.0
0.0
50.490
28.814
Bowly
0.205
82.312
35.131
41.305
21.628
1.484
3.504
403,208
198.571
random
0.01
127.723
0.251
100.774
9.853
50.357
6,841
1.294
3.045
422.65
65.078
random
0.05
143.
0.253
101.099
14.070
50.519
6.787
1.218
3.123
431.422
66.082
random
0.10
858
0.253
101.357
17.706
50.678
6.727
1.164
3.210
441.696
67.250
random
0.20
304.216
0.255
101.900 .900
22.808
60.950
6,607
1.062
3.351
160.696
69.379
random
0.50
1312.595
0.258
103.348
31.305
51.674
6.375
0.664
3.629
509.331
74.864
ours
0.01
83.681
0,251
100.700
8.876
50.350
7,431
-0.515
1.351
44.803
0.939
ours
0.05
70.476
0.251
100.712
10.202
50.356
9.977
-0.456
1.386
44.958
0.984
ours
0.10
54.650
0.251
100.738
11.365
50 10.369
13.354
-0.413
1.441
45 55.057
1.032
murs
0.20
54.830
0.251
100.754
12.872
50.377
19.992
-0.388
1.576
45.112
1.071
ours
0.50
22.462
0.252
100.830
14.433
5U-415
37.017
-0.005
44.967
1.872
Table 14: Statistic value comparison across the original dataset and the generated datasets with different constraints replacement. rates the combinatorial auction (CA) problem. 'resolving time' calculates under default configuration of pySCIPopt. 'density' reprosents the ratio of non zero entries in the constraint matrix.
'cons degree' denotes the degree of constraint nodes, 'var degree' stands for the degree of variable nodes. b denotes the right hand side vector of the MILP, and c is the objective coefficient vector.
resolvig
density
cons degren
cons degree var degme
var degree
replace ratio
time (s)
mean
std
mean
mean
std
e mean
c std
original
1.360
0.050
14.538
13.834
5.578
3.253
1.0
330.999
234.444
Bowly
0,281
0.048
14.115
13.633
5,544
7.262
1.668
1.617
510.211
1101.065.
random
0.01
0.116
0.051
14.641
13,970
5,634
3,240
1.718
1.602
524.961
563.436
random
0.05
0.502
0.054
15.225
14.531
5,878
3.201
1.792
1.647
500.309
561.074
random
0.10
0.555
0.056
15.877
15.088
6.152
3.161
1.855
1.706
598.047
555,956
random
0.20
0.821
0.061
17.098
15.953
6.658
3.106
1.966
1.797
669.168
552.853
random
0.30
1.056
0.065
18.186
16.527
7.105
3.070
2.053
1.850
735.284
548.606
random
0.50
2.353
0.072
19.959
17.222
7,837
3.006
2.267
1.972
$41.971
515.471
0.01
0.361
0.050
14.490
13.776
5,565
3.253
L.645
1.348
361.711
264. 798
ours
0,05
0.360
0,050
14.361
13.609
5,535
3,286
1.609
1.325
351.417
261. 927
ours
0.10
01301
0.050
14,205
13.401
5.500
3.366
1.589
1.329
342.702
261 .313
ours
0.20
0.217
0.049
13.819
12.854
5.412
3,586
1.525
1.315
324.282
260.848
ours
0.30
0.140
0.017
13.454
12,330
5.344
3.847
L.454
1.280
304,911
260.941
ouTS
0.50
0.055
0.045
12,869
11.379
5.254
4.282
1.350
1.233
271.474
255.315
metric, see www.aipppi......i.. zib. www.d//ag.ollletio.....ooo html
B,4 and C.1 in the appendix. The detailed dynamic ranges of CA and SC could be found in
sttps://mipl11
C.2 Data Sharing for Solver configuration Tuning
CVS and IS There are five total instances in CVS, comprising three for training DIG-MILP and the downstream predictor and two for testing. The IIS has two instances, one for training and one for testing (with allocation based on alphabetical order). Please refer to Table. 15 for the model's performance. 'ground truth' corresponds to the true values of the optimal objectives for each problem. Models trained exclusively on the 'original' training set exhibit superior fitting and more accurate predictions on the training set itself. However, models trained on the datasets where introduce 20 additional newly generated instances by DIG-MILP with varying constraint replacement ratio Y not only demonstrate minimal gap in prediction the training set towards the models trained solely on the original data compared with the basclines, but also showcase improved predictive performance on previously unseen test sets. This underscores the notion that the DIG-MILP --geerreed data can indeed increase structural and solution label diversity to a certain extent, thereby enhancing the generalization capability and overall performance of the models. Again, similar the previous two experiments, 'Bowly' degrades the predictive performance of the model, 'random' results in marginal improvement in out-of-distribution prediction accuracy.
23

---

Published in Transactions on Machine Learning Research (07/2024)
Table 15: The predicted value and relative mean square error (MSE) of the optimal objective value on the CVS and the IIS problem. In the CVS, 'cvs08r139-94 'cvs16r70-62", cvv16619-600 are used as training data, 'cvs16r106-72', wcwws6rr12--1. are used testing data. In the π1S, 'iis dis-glass-col cov' is used as the training data, 'iis-hcccov' is used as the testing data. 'original' shows the performance of the model trained merely the three (CVS) single (IIS) original training instances.
in distributionn
out-of-distributt
in di-dittibution
cut-of-distriburs
cvsl18r1
cvs16:70-62
cvs16689-00
106-67
lie-ghae-cov
fis-he-cov
valtie
mure
mure
mase
mosee
value
mate
mure
mnsre
ground truth
116
0
97
-17
0
-21
0
original
115.994
2e-9
41.998
1e-9
64.997
1e-9
77.491
0.001
89.258
0.006
-20.999
Se-10
-94,451
20.756
Bowly
66.
0.187
$2.353
0.923
86.898
Se-G
61.501
0.057
66.045
0.101
-88.756
17.816
-88.750
17.816
mandom
0.01
136.450
0.037
45.312
0.006
67.875
0.001
58.754
0.075
68.192
0.088
-2 263
3o-4
-80.146
15.139
0.031
0.089
14.753
random
116.821
Se-3
2163.
random
0.20
144.962
0.002
79.840
0.812
99.352
0.252
71.821
0.0128
99.898
8o-4
678
0.001
-227-610
103.482
random
0.50
159.807
0.142
49.364
0.030
65.213
1e-6
103.990
0.080
122.321
0.008
633
9e-3
-100-224
23.966
DIG-MILP
0.01
116.981
7e-5
42.197
2e-5
64.876
3e-6
78.646
86-4
96.881
3e-6
-20 933
1e-5
-90.556
18.721
DIG-MILP
0.05
161 5G8
0.164
26.181
0.141
23-139
0.408
66.119
0.033
76.119
0.016
-21.108 108
2e-5
-61.217
6.765
DIG-MILP
0.10
118.600
5o-4
45.461
0.006
67.216
0.001
80.706
1e-5
96.745
1o-4
-20.976
1c-6
-65.385
8,101
DIG-MILP
0.20
111.622
le-1
12,933
1c-1
02:627
0.001
83.379
8e-1
120.611
0.0591
-20.159
0.001
-55.926
5.213
DIG-MILP
0.50
120.361
0.001
11.472
0.003
69:267
0.001
84.870
0.0012
104.333
0.005
-21.009
2--7
-90.427
18.655
combuarettal settion oniginal
(V05 enggenni
125 orighnll
(a) CA SC
(b) CVS CA
(c) 11S CA
CVS
280
300
100
600
100
200
363
607
500
100
160
160
250
250
372
300
amgaaut
CVS orqueal
(d) CVS
(e) ITS SC
(f) CVS SC
Figure The solution time of SCIP with different parameter sets across different original datascts.
We present the visual results for CA, SC, and IIS datasets, Fig.
6
24

---

Published in Transactions on Machine Learning Research (07 (07/2022 2024)
(a) two trials
(b) random (7 0.1)
(c) random ( = 0.2)
(d) random (y = 0.3)
Figure 6: The solution time of SCIP on the CA with 45 different (h) ours (7 = 0.3)
(6) Bowly
(I) ours (7 = 0.1)
(g) ours (7 0.2)
sets.
(a) two trials
(b) random (y=0) 0.1)
(c) random (> 0.2)
(d) random (y 0.3)
120 120
Lo
25
10
20 12 14
(0) Bowly
(I) ours (7 = 0.1)
(g)
ours (7 0.2)
(h) ours (7 0.3)
Figure The solution time of SCIP on the SC with 45 different typer-paramest sets.
25

---

Published in Transactions on Machine Learning Research (07/202) /024)
(a) two trials
(b) random (7 = 0.1)
(c) random (y = 0.2)
(d) random (v = 0.3)
(e) Bowly
(7 0.1)
ours (y 0.2)
ours (7 0.3)
Figure 8: The solution time of SCIP the IIS with 45 different hyper-paramcter sets.
26


Reviews:
[{"review_id": "ZXU2jcMYjG", "reviewer": "Reviewer_r2iK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The work is well-motivated.\n* The presented method is creative, leveraging MILPs' duality structure to transform the \"feasible MILP generation problem\" into a coefficient generation problem, and leveraging graph generation techniques to sample the coefficients.\n* Results (solver configuration tuning): DIG-MILP demonstrates better solve time correlation between the original and synthetic instances compared to baseline methods, and the correlation is reasonably strong for some of the datasets (CA, SC).\n\nWeaknesses:\n* Clarity: The clarity of Section 3.3 could be significantly improved. I was not able to fully understand the relationship between the graph structure and the procedure in Section 3.2.\n* Results (solver configuration tuning): While better than baselines', the Pearson correlation coefficient between the solve times for the real and synthetic instances is somewhat low for some of the datasets (CVS, IIS). There should be some analysis of why the correlation is stronger for some datasets than others.\n* Results (optimal value prediction via ML): It is not clear to me how fair the comparisons are. In particular, the non-synthetic training data is restricted in its distribution, but it is not clear that the DIG-MILP-generated training data is similarly restricted. As such, the notion of \"out of distribution\" generalization may be a bit artificial if the DIG-MILP training data is also \"out of distribution.\" More clarity on the distribution of the DIG-MILP training data and its relationship to the \"out of distribution\" test data would be necessary to assess the validity of these results.\n\nMinor:\n* Typos and usage errors throughout the manuscript should be fixed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a method (DIG-MILP) to generate synthetic MILP instances that (a) have bounded and feasible solutions, (b) are representative of the original MILP data, and (c) can represent a diverse set of problem formulations. The method involves sampling primal/dual coefficients and slack variables of the MILP, using graph generation techniques. Experiments are conducted to demonstrate that (a) the synthetic instances and the original instances have similar solve times under similar solver hyperparameters, and (b) using DIG-MILP data enhances the generalization performance of ML methods trained to estimate MILP solutions.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the three points under \"Weaknesses\" above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dGiBydfEbA", "reviewer": "Reviewer_oN5U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The problem is worth investigating.\n+ The generation technique seems well suited.\n+ Many design choices made in relation to Integer Programming are well justified with judicious references from the Integer Programming literature.\n\n- Some statements are not proven or referenced.\n- Formalism is lacking at times.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a method to generate instances that are guaranteed to be feasible and bounded for problem types for which there exists some instances. This can be useful for training purposes, but also as a way of “anonymizing” instances. The generated instances are compared to the original instances in terms of solve time in a MIP solver and ability for a ML algorithm to predict the objective values.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have a few questions that I would like an answer for, and/or a change in the paper. Please see below. Thank you.\n\nPage 1: How does one measure the “quality” of a MILP instance?\n\nPage 2: what is dynamic range, in relation to MILP instances?\n\nPage 2: why is it important to ensure that instances are feasible and bounded? Infeasibility and unboundedness are important properties that need to be reflected in instances, in my opinion.\n\nPage 3: “Merely finding a set of feasible solutions to such a problem could be NP-hard”: is it or is it not? Is this statement true for one feasible solution? Please write more specifically and provide evidence or references. Throughout the paper, the use of the word “could” is misleading. It carries a lack of certainty, but the sentences look like they are written like statements. Please go through the different uses of “could” and attempt to replace them in order to clarify the paper.\n\nPage 3: “Within the entire MILP space H [...],the majority of MILP problems are infeasible or unbounded.” Where is the proof of this statement?\n\nPage 3: How does one sample “diversly” from the rational numbers? Would that imply that an arbitrarily large number is as likely to be sampled as an arbitrarily small number? Is there a distribution that can ensure that?\n\nPage 4: “no company would take efforts in solving and modeling infeasible real-world problems”. That is not true, to my knowledge. For example, the MIPLIB 2017 collection has a number of infeasible instances: https://miplib.zib.de/tag_infeasible.html. Perhaps most of them come from academia. Either way, please nuance this point and provide evidence.\n\nPage 4: Proposition 1 is used to justify the ability of DIG-MILP to generate “diverse” instances. However, given colored balls and a bag, stating that all colors exist in the bag and that the bag only contains colored balls does not mean that a sample drawn from the bag will be “diverse”. The bag could contain infinitely many red balls and 1 black ball. In any case, without a definition of diversity, no statement on the diversity of DIG-MILP can be proved.\n\nPage 4: what does “equivalence between sampling” mean?", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rySPhGdONT", "reviewer": "Reviewer_vj1H", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1. The setting of generating MIP instances is well-motivated and discussed. Overall the paper is well-written, easy-to-understand, and has a convincing experimental section. The formulation combining the VAE with GNN backbone makes sense. The comparisons to the Bowly methods as baselines makes sense.\n2. In task #1 on data sharing for solver configuration, the experiments throughout Fig 3 and Table 3/4 clearly show that the generated samples are reasonable for attaining better performance on the held-out samples\n3. In task #2 on value prediction for set covering and combinatorial actions, Table 5/6 clearly show that the generated augmentations outperform other Bowly and random generations from other distributions\n\n# Weaknesses\n1. I feel the paper needs to be carefully positioned when discussing scenario I on retaining private data, as it still seems challenging to get the model to produce representative samples that do not leak real data. For example, the abstract states this allows \"data sharing\nfor solver tuning without publishing the original data,\" but I do not feel it is a claim the paper properly supports in general, other than (if I understand correctly) S4.2.1 showing that the samples from SC and CA are reasonable for selecting test hyper-parameters in the CVS and IIS settings\n2. I feel the second setting on optimal value prediction is a reasonable demonstration, but slightly disconnected from the existing literature on optimal value prediction. E.g., section 4.1 cites Chen et al. 2023; 2024 for this setting, but these papers do not discuss the set covering or combinatorial action settings presented in S4.2.2, and it's not clear if there are existing published results that are directly comparable in these settings. I feel the paper would be much clearer if the augmented MIP data would improve an established experimental setting", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper explores how to generate instances of mixed-integer linear programs (MILPs) for generating 1) synthetic data that mirrors original data without leaking information, and 2) augmenting MILP solvers. S3.1 and S3.2 discuss the basic MIP formulation with optimal dual and slack variables. S3.3 discusses the main generation process of encoding the MIP variables and constraints into a graph that is that generated with a generative model using a VAE with a GNN for encoding and decoding, which is trained with the ELBO in eq (6) with the architectures in eqs (7) and (8).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is definitely within-scope for TMLR. I slightly mark the paper as not meeting claims and evidence due to the two weaknesses I have pointed out on retaining privative data and comparing to other optimal value prediction works. I am very open to further discussing these throughout the review period", "broader_impact_concerns": "I do not have any", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes DIG-MILP, a machine learning approach to generate MILP instances based on past observed instances. In particular, DIG-MILP is designed to ensure that the generated instances are both feasible and bounded, a guarantee that the concurrent work by Geng et al. does not provide. Reviewers found the question motivated and the paper well-written overall.

The authors have edited the submission in response to reviewer comments and concerns. As a result, reviewers (and I) agree that the paper satisfies both of the TMLR acceptance criteria: 1) claims being supported by convincing evidence and 2) there is an audience in the TMLR community who would be interested in this work.
Decision: Accept (poster)