MILP-StuDio: MILP Instance Generation via Block Structure Decomposition
Authors: Haoyang Liu
Jie Wang
Wanbo Zhang
Zijie Geng
Yufei Kuang
Xijun Li
Bin Li
Yongdong Zhang
Feng Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: Mixed Integer Linear Programming
MILP Instance Generation
Primary area: machine_learning_for_other_sciences_and_fields

Abstract: Mixed-integer linear programming (MILP) is one of the most popular mathematical formulations with numerous applications. In practice, improving the performance of MILP solvers often requires a large amount of high-quality data, which can be challenging to collect. Researchers thus turn to generation techniques to generate additional MILP instances. However, existing approaches do not take into account specific block structures—which are closely related to the problem formulations—in the constraint coefficient matrices (CCMs) of MILPs. Consequently, they are prone to generate computationally trivial or infeasible instances due to the disruptions of block structures and thus problem formulations. To address this challenge, we propose a novel MILP generation framework, called Block Structure Decomposition (MILP-StuDio), to generate high-quality instances by preserving the block structures. Specifically, MILP-StuDio begins by identifying the blocks in CCMs and decomposing the instances into block units, which serve as the building blocks of MILP instances. We then design three operators to construct new instances by removing, substituting, and appending block units in the original instances, enabling us to generate instances with flexible sizes. An appealing feature of MILP-StuDio is its strong ability to preserve the feasibility and computational hardness of the generated instances. Experiments on the commonly-used benchmarks demonstrate that using instances generated by MILP-StuDio is able to significantly reduce over 10% of the solving time for learning-based solvers.

MILP-StuDio: MILP Instance Generation via Block Structure Decomposition
Haoyang Liu', Jie Wang',, Wanbo Zhang', Zijie Geng', Yufei Kuang', Xijun Lia.3, Yongdong Zhang', Bin Li', Feng Wu'
MoE Key Laboratory of Brain-inspired Intelligent Perception and Cognition, University of Science and Technology of China
2 Shanghai Jiao Tong University
Noah's Ark Lab, Huawei Technologies
{dgyoung, zhang_wb wb, ustcgzj yfkuaag)amaaaa wwtuussteeee cn,
lixi jun@s edu. cn, binli, fengmu)@ustc.. edu. cn
Abstract
Mixed-integer linear programming (MILP) is one of the most popular mathematical formulations with numerous applications. In practice, improving the performance of MILP solvers often requires large amount of high-quality data, which can be challenging to collect. Researchers thus turn to generation techniques to generate additional MILP instances. However, existing approaches do take into account specific block structures wrichh are closely related to the problem formulations the constraint coefficient matrices (CCMs) of MILPs. Consequently, they are prone to generate computationally trivial or infcasible instances due to the disruptions of block structures and thus problem formulations. To address this challenge, propose novel MILP generation framework, called Block Structure Decomposition SttLP-StuDio). to generate high-quality instances by preserving the block structures. Specifically, MILP-StuDio begins by identifying the blocks in CCMs and decomposing the instances into block units, which serve as the building blocks of MILP instances. We then design three operators to construct new instances by removing, substituting, and appending block units in the original instances, enabling us to generate instances with flexible sizes. An appealing feature MILP-StuDio is its strong ability to preserve the feasibility and computational hardness of the generated instances. Experiments demonstrate that with instances generated by MILP-StuDio, the learning-base -baed solvers are able to significantly reduce over 10% of the solving time.
commonly-used benchmarks
Introduction
Mixed-integer linear programming (MILP) is fundamental mathematical optimization problem that finds extensive applications in the real world, such as scheduling (I). planning (2], and chip design
3 In industrial scenarios, the solving efficiency MILPs is associated with substantial economic value. To speed up the solving process, a great number of high-quality MILP instances are required develop test the solvers. Here we give the following two examples. First, both traditional solvers solvers [7410] rely heavily on lot of MILP instances for hyperparameter tuning or model training. Second, evaluating the robustness of solvers needs comprehensive MILP benchmark consisting of numerous instances. However, acquiring many instances is often difficult due to high acquisition costs or privacy concerns [1] 12] As result, the limited data availability poses great challenges and acts bottleneck for solver performance.
[5 and
Corresponding author. Email: jiewangx @ustc.edu.cn.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Advanced Features
Applications
MILP-StuDio
Hardness
Enhancing ML
CCM
Preservation
Solver
Stucture
Block Decomsp
Preservation
Enhuncing Traditional Solver
Scalable Generation
Benchmark Construction
Efffciennt
Structure Library
Generation
(a) CCMs in FA.
(h) Features and applications of MIL.P-tuDDio.
Figure I: Figure visualizes the CCMs of four instances from the FA problem, where the white points represent the nonzero entries in CCMs. As we see, the CCMs exhibit similar block structures across instances, with the patterns in red boxes being the block units. Figure Tb illustrates the block decomposition process, advanced features, and applications of our proposed MILP-StuDio.
This challenge motivates wide range MILP generation techniques. In the past, researchers relied on problem-specifie techniques for generation [1. These methods assumed knowledge of problem types and generated instances based on the corresponding mathematical formulations, such as the satisfiability problem [18], set covering problem [15], and others. However, these techniques require much expert knowledge to design and are limited to specific MILP problems. They also face limitations in practical scenarios where problem formulations are unknown [19].
In recent years, there has been some progress in general MILP generation that does not require explicit knowledge of the problem formulations. These approaches can be broadly classified into methods. Statistics-
statistics-bar baaed and learning-basse statistics to sample in the MILP space [20]. More advanced learning-based approaches, exemplified by G2MILP [99 leverage deep learning models to capture global instance features and iteratively modify constraints in the original instances. Though in the early stage, learning-basee techniques offer convenience and strong adaptability for MILP generation, making them applicable wider range of practical scenarios [19]. However, they still suffer from significant challenges. (1) They fail to account for the inherent problem structures adequately and disrupt instances' mathematical properties. This leads to low-quality instances with degrading computational hardness infcasible regions. (2) Existing methods fail to generate instances with different sizes from the original ones, limiting instance diversity. (3) The iterative style to modify constraints becomes time-consuming when dealing with large-scale instances.
approaches utilize a few instance
Therefore, a natural question arises: can we analyze and exploit the problem structures during generation to address the above challenges? Consider a MILP instance with constraints Av S b, where A is the constraint coefficient matrix (CCM), is the decision variable and b is vector. As shown in Figure Ta] we observe that a great number of real-world MILP problems exhibit structures with repeated patterns of block units in their CCMs. In operational research, researchers have long noticed the similar block structures CCMs across instances from the same problem type, and they have been aware of the critical role of CCMs in determining problem formulation and mathematical properties [41 Although a wide suite of CCM-based techniques have been developed to solve MILPs 25 27 existing works MILP generation rarely pay attention CCMs. Consequently, these works fail to preserve the block structures during the generation process.
In light of this, we propose a novel MILP generation framework called Block Structure Decomposition MMtLP-StuDio), which takes into account the block structures throughout the generation process and addresses Challenge (1)-(3) simultaneously. Specifically, MII.-SttDio consists of three key steps. We begin by identifying the block structures in CCMs and decomposing the instances into block units, which serve the building blocks in the MILP instances. We then construct library of the block units, enabling efficient storage, retrieval, and utilization the comprehensive block characteristics during the subsequent process. Leveraging this library, design three block operators on the original instances to generate new ones, including block reduction (eliminating certain blocks from the original instances), block mix-up (substituting some blocks with others sampled from the library), and block expansion (appending selected blocks from the library). These operators enable us generate instances with flexible sizes, effectively improving the diversity of instances.
Experiments demonstrate that MttuDio has the following advanced features. (1) Hardness preservation. MILP- can effectively preserve the computational hardness and fcasibility in the

---

(a) CA
(b) IP
MIK
(d) WA
Figure 2: Visualization of the CCMs of instances in four widely recognized benchmarks. The block structures can commonly seen in MILP problems.
generated instances. (2) Scalable generation. MILP-StuDio can generate instances with flexible sizes. (3) High efficiency. MILP-StuDio can reduce over two-thirds of the generation time in real-world large datasets. We observe an over 10% reduction in the solving time for learning-baan based solvers using instances generated by MILP-StuDio.
2 Background
2.1 MILP and MILP with Block Structure
MILP instance takes the form of:
min BER
c cJa, x. s.t.
x u. D RT-P.
(I)
In Formula (T) denotes the decision variables, R denotes the coefficients in the objective function, A E mR is the constraint coefficient matrix (CCM) and b E Ihm denotes the terms on the right side of the constraints, respectively. The vectors I (IR U f-o0)) and (R (+00))" denote lower and upper bounds for the variables, respectively.
In real-world applications, significant portion of MILPs exhibit block structures of many block units in their constraint coefficient matrices (CCMs) A. These problems, referred as MILPs with block structures, include many commonly-
and widely-studied datasets in recent papers learning-basee baaegg--bddddee solvers [8-10) (88). such as combinatorial auctions (CA), capacitated facility location (FA), item placement (IP), multiple knapsacks (MIK), and workload balancing (WA). In Figure visualize the CCMs of MILP instances using a black-and-white digital image representation [29] In this representation, the rows and columns of the digital images correspond to the constraints and variables in the MILPs, respectively. To construct the digital image, we assign pixel value of 255 (white) to the entry (i,j) if the corresponding entry in the CCM A j] is nonzero. Conversely, if jii is zero, we set the pixel value to 0 (black). This mapping allows us to depict the sparsity patterns and structural characteristics of CCMs visually. For each problem, the CCMs of the instances present a similar block structure, characterizing specific mathematical formulations.
The importance of block structrdd CCMs in the context of MILP solving has long been acknowl- edged by operational researchers, where instances with similar block structures share similar math- ematical properties [1 Furthermore, the block structures of CCMs closely related to the problem formulations 30 Thus, the block matrices have shown great potential in accelerating the solution process for family of MILP problems 24 One notable technique developed exploit this structure is Dantzig- -onle decomposition 255 for solving large-scale MILP instances.
2.2 Bipartite Graph Representation of MILPs
The two sets of nodes W [wr,.... Wm } and V -..,... ", } in the bipartite graph correspond to the MILP's constraints and variables, respectively. The edge set = {eiz} comprises edges, each connecting constraint node w; E W with variable node U; V. The presence of an edge Ei is determined by the coefficient matrix, with eij = -(es) as its edge feature, and an edge eij does not exist A[i. 0. Please refer to Appendix I.I for more details the graph features use in this paper.
MILP instance can represented weighted bipartite graph g = (.V.E g
3 Motivated Experiments
Preserving the mathematical properties the original instances is fundamental concern MILP generation [19] These properties encompass feasibility, computational hardness, and problem structures, with the latter being particularly crucial. The problem structure directly determines the problem formulation and, consequently, impacts other mathematical properties. However, it
3

---

is important to note that the term "problem structure" can be ambiguous and confusing. There are different understandings and defiiitions of the problem structure- such as the bipartite graph structure [9 and the CCM's block structure [29 and we are supposed to identify the most relevant and useful ones that contribute to the mathematical properties of MILPs. Analyzing and exploiting these specific structure types become key factors in improving the quality of the generated instances.
3.1 Challenges of Low-Quality Generation
G2MILP the first learning- -based approach for MILP instance generation. While has shown promising performance, we observe that G2MILP still encounters difficulties in generating high- quality instances for MILPs with block structures. To evaluate its performance, we compare the graph structural distributional similarity and solving properties of the original and generated in- stances from the workload appointment (WA) benchmark [32) using Gurobi [5], a state-of-the-ae traditional MILP solver. We set the masking ratio of 12MILP-whire determines the proportion of constraints to be modified-to 0.01. The results are summarized in Table In this table,
the Similarity metric refers the graph struc- tural distributional similarity score [19] (defined in Appendix I.3]. Time represents the average solving time (with a time limit 1,000s), and Fea- sible ratio indicates the proportion of feasible instances out of the total instances. Results show that although the generated instances achieve high similarity score, most of them are infeasi- ble. Furthermore, the feasible instances exhibit severe degradation in computational hardness.
Table The comparison of graph similarity and solving properties between the original instances and the generated instances using G2MILP [9), a popular MILP generation framework. Here use 100 original instances to generate 1,000 instances.
Similarity
Time
Feasible Ratio
Original G2MILP
1.000
1000.00
100.00%
0.854
12.01
10.00%
3.2 Visualization of CCMs
The aforementioned experiments provide evi- dence that by iterative modifications of sampled constraints, G2MILP can generate MILP with high graph structural distributional similarities to the original instances, but may lead to disruptions in mathematical properties. Consequently, it becomes necessary explore alternative definitions of problem structures that offer stronger correlations can be effectively preserved during the generation process. One such promising structure is the block structures within CCMs.
mathematical properties of the instances and
The concept of block structures within CCMs originates from traditional operational research and widely recognized that MILPs with
has proven to effective for problem analysis 241 similar block structures in CCMs often share similar formulations, resulting in similar mathematical properties
We visualize and compare the CCMs of the original and generated instances in Figure 3 In the middle figure, observe that G2MILP breaks the block pattern in the left and introduces noisy block in the bottom right. It becomes evident that the generation operation G2MILP breaks the block structures presenting in the original instances. Thus, it motivates us that exploring and preserving the block structures in CCMs can hold the potential for generating high-quality instances.
Figure 3: Visualization of CCMs from original instances (left), instances generated by G2MILP (middle), and instances generated by MILP-StuDi (right).
4 Generation Framework Using Block Structure Decomposition
In this section, we introduce the proposed MILP-StuDio framework to generate high-quality instances. MII---tuDio comprises three steps: block decomposition, construction of structure library, and block manipulations. We begin by presenting the concept of block decomposition for MILP in Section 4.1

---

Block Decomposition
Structure library
min c'ix Ar S 1 E
D
Bo
Sub-matrices
Subgraph Extraction
B
B
MII.P Instances
Image Representation
CCM block
Sub-graphs
Reordering
Block Decomposition
Library Construction
Block Manipulation
Sampling
Manipulation
(b) Mix-up
(c) Expansion
L
Subgraph
Reduction
D
Stublo
Instance
Bo
B
B.
Figure 4: An overview of MILP-StuDio. (1) We detect the block structures in the original instances and decompose the CCMs into sub-matrices of block units. (2) The sub-matrices are transferred into the corresponding sub-gre sub-graphs of instances' bipartite graph representations. These sub-gres wub-graphs are used construct the structure library. (3) We sample instances and sub-graphs of block units and perform block manipulations, including block reduction, mix-up and expansion.
as it forms the core of our method. The subsequent sections, from Section 4.2 to Section detailed explanation of each step. The overview MILP-StuDio is depicted in Figure
provide
4.1 Block Decomposition of MILP
In this part, we specify the block structures that we are interested in. CCMs are often reordered to achieve the well-studied block structures (30,, including the block-diagonal (BD), bordered block- diagonal (BBD), and doubly bordered block-diagonal (DBBD) structures. We highlight the block unit of the decomposition in blue in Equation (2). We can see that the former two structures special cases of the latter one. Despite the simplicity, they are the building blocks for more complex block structures and are widely used in operational research 30
D1
D
F
Di
D2
D2
F2
D2
:
(2)
D
DR B
D
K
F
B
B2
B,
B
B
C
(a) Biackalaagonal
(b) Bordered block-diagonal
(c) Doubly bordered block-diagonal
Formally, MILP with DBBD structure be written
min #ER"
cTx1 cT c σy
Cb++1 Ix-1;
s.l. D + F by 1sish k.
(B-Cons F, O, otherwise DB-Cons)
Σ B,c + Ca & betl,
(M-Cons)
1 x X R"
where the partition c = (cT c = (zT x++11 and b = (bT.... .... bb11) To process more complex block structures beyond the three basic ones, we specify different types of constraints and variables in CCM (and the corresponding MILP). First, we classify variables as block and bordered variables (BI-Vars and Bd- vars..s). The block variables DBBD are Phiack = ,.."
(x= ........ xx )T
which are involved in the blocks D... (1 < i < k). The bordered variables
5

---

defined to be those in F. (1 <i k), i.. the variables 24++1. Notice that all the variables in BD and BBD are block variables. Then, we classify the constraints in an instance as master, block and doubly block constraints (M-Cons. B-Cons, and DB-Cons), which we have illustrated in Equation (2) As we can see, BD only contains B-Cons, BBD contains B-Cons and M-Cons, and DBBD contains DB-Cons and M-Cons. The classifications of constraints and variables make it possible for us to investigate more delicate structures in the instances- -such as the combination of the three basic ones-in the subsequent process (please see Appendix H.2 and H.4).
4.2 Block Decomposition
Reordering Rows and Columns in CCMs Given MILP instance, the raw orders of rows and columns for CCM are determined by the orders of constraints and variables respectively. which is defined when we establish the instance. Generally, the block structures are not readily apparent in this raw form. To identify and exploit these block structures, we employ a structure detector implemented in the Generic Column Generation (GCG) solver (33 for CCM reordering. This detector identifies row and column permutations that effectively cluster the nonzero coefficients, thereby revealing distinct block structures within CCMs.
Block Decomposition We employ an enhanced variable partition algorithm based on the image representations of CCMs for block decomposition, using the cunstraint-variable classification results mentioned in Section 4.1 Specifically, we extract the sub-matrices of the block units BU in CCMs,
Di
in BBD, and D B:
F.
i.e, which take the form of D; in BD,
in DBBD. Finally, we
B;
partition and decompose the CCMs into sub-matrices of block units. handle more complex structures beyond the basic three found by GCG, such as instances in WA with
The algorithm enables us to
DD11) (1)
M-Cons, B-Cons and BD-Cons. In the case of WA, the sub-matrices are in the form of
B (
where D represents the diagonal block with DB-Cons, and D represents the diagonal block with B-Cons. Please refer to Section H.3 for the detailed implementation of the decomposition process.
4.3 Construction of Structure Library
As we can see in Figure Tal the block units across instances exhibit striking similarities in terms of the internal struetures. These common characteristics indicate that the distribution of block units holds valuable information about the problem formulations, making it an ideal building block for reconstructing new instances. Given block-unit sub-matrices of CCMs obtained in Section 4.2 we proceed to extract the corresponding bipartite sub-graphs within the graph representations of the original instances. Compared to the image representation, graph representation offers more convenience for modifying MILP instances during block manipulation. Specifically, suppose that sub-matrix contains constraints W {wi, ... wh. and variables y = ...,.... Us } in the
instances, we then extract the sub-graph containing W, V and the edges connecting W and V in the bipartite graph representation of the original instance. Subsequently, we collect these sub-graphs from all the training instances and utilize them to construct a comprehensive structure library denoted as L. This structure library serves as a repository for the collected sub-graphs, allowing efficient storage, retrieval, and utilization of the block information.
4.4 Scalable Generation via Block Manipulations
With the structure library, we devise three types of generation operators that enable the generation of high-quality MILP instances with flexible sizes. These operators, namely block reduction, block mix-up. and block expansion, play a crucial role in the instance generation process.
Reduction. This operator involves randomly sampling block unit Bl4ms from the original instances and then removing it. The reduction operator generates MILP instances with smaller sizes compared to the original ones, reducing the complexity of the problem.
Mix-up. This operator involves randomly sampling one block unit Buss from the original instances and another block unit BU from the structure library L. We then replace Bddss with Bl to generate a new instance. The mix-up operator introduces structural variations through the incorporation of external block units.

---

This operator involves randomly sampling a block unit BU from the structure library C and appending the original instances. This process generates new instances of larger sizes compared to the original ones, potentially introducing more complex structures.
Expansion.
To preserve the block structures, the operators should leverage the constraint-variabe classification results. Taking the expansion operator as an example, the coefficients of M-Cons in the external block unit should be properly inserted into the M-Cons of the original instances. Meanwhile, we construct new constraints for the B- and DB-Cons of the block using the corresponding hight-hand-side terms by. Finally, we design a coefficient refinement algorithm to align the coefficients of the external blocks during mix-up and expansion (please see Appendix H.4 for details).
5 Experiments
5.1 Experiment Settings
Benchmarks We consider four MILP problem benchmarks: combinatorial auctions (CA) [16]. capacitated facility location (FA) [17], item placement (IP) [32] and workload appointmnnt (WA)
32). The first two benchmarks, CA and FA, are commonly-used benchmarks proposed in [8] The
last two benchmarks, IP and WA, come from two challenging real-world problem families used in
NeurlPS ML4CO 2021 competition 32] The numbers of training, validation, and testing instances are 100, 20, and 50. More details on the benchmarks are in Appendix [.2]
Metries We leverage three metrics evaluate the similarity between the original and generated instances. (1) Graph statistics are composed of 11 classical statistics of the bipartite graph (34).
Following [19], we compute the Gensen-Shannon divergence for each statistic between the generated
and original instances. We then standardize the metrics into similarity scores ranging from 0 to 1. (2) Computational hardness is measured by the average solving time of the instances using the Gurobi solver [. (3) Feasible ratio is the proportion of feasible instances out of the total ones.
We consider two baselines for MILP generation. The first baseline is the statistics- based MILP generation approach Bowly [20), which generates MILP instances by controlling specific statistical features, including the coefficient density and coefficient mean. We these features to match the corresponding statistics of the original instances so as to generate instances with high statistical similarity with the original ones. The second baseline is the learning-basee approach G2MILP [19. By leveraging masked VAE, G2MILP iteratively masks one constraint node in the bipartite graph and replaces it with a generated one.
Baselines
Downstream Tasks We consider three downstream tasks to demonstrate the effectiveness of the generated instances in practical applications. (1) Improving the performance of bearning-based solvers, including predict-and-seane
(PS) 110] in Section [5.3 and the GNN approach for learning-tor sorninggto-bbanch [8] in Appendix F. (2) Hyperparameter tuning for the traditional solver (please see Appendix [F3).
In the above two tasks, we use MILP-StuDio and the baselines to generate new instances to enrich the training data. We also consider the task of (3) hard instances generation in Section 5.4 which reflects the ability to construct hard benchmarks.
Variants of MILP-StuDio During the generation process, we use the three operators to generate one-third of the instances, respectively. We can choose different modification ratios, which implies that we will remove (substitute or append) block units when performing the reduction (mix-up or expansion) operator until the proportions of variables modified in the instance reaches 17.
5.2 Similarity between the Generated and the Original Instances
For each generation technique, we use 100 original instances to generate 1,000 instances and evaluate the similarity between them. As shown in Table 2, we present the graph structural distributional similarity scores between the original and generated instances. We do not consider Bowly in WA since the instance sizes in WA are so large that the generation time is over 200 hours. The results suggest that MILP-StuDi shows a high graph structural similarity compared to the baselines. In FA, instances generated from G2MILP present a low similarity, while our proposed MILP-StuDio can still achieve high similarity score. As the modification ratio increases, the similarity scores of G2MILP and MILP- StuDio decrease, whereas G2MILP suffers from a more severe degradation.
We also evaluate the computational hardness and feasibility of the generated instances in Table 3 We report the average solving time and feasibility ratio for each dataset. Results demonstrate that the instances generated by the basclines represent a severe degradation in computational hardness.
7

---

Table Structural Distributional similarity scores between the generated instances and the original ones. The higher score implies higher similarity. Timeout implies the generation time is over 200h.
fj 0.01
0.05
1j 0.10
Bowly
G2MILP
MILP-StuDio
G2MILP
MILP-StuDio
G2MILP
MILD-StuDio
CA
0.567
0.997
0.997
0.995
0.981
0,990
0.946
FA
0.077
0.358
0.663
0.092
0.646
0.091
0.618
IP 0,484
0.717
0.661
0.352
0,528
0.336
0.493
WA
Timeout
0.854
0.980
0.484
0.853
0.249
0.783
Table 3:
Average solving time (s) and feasible ratio (in parentheses) of the instances. We set the
solving time limit to be 1,000s. We mark the values closest to those in original instances in bold.
CA
FA
WA
Original Instances
0.50 (100.0%)
4.78 (100.0%)
1000 (100.0%)
1000 (100.0%)
Bowly
0.02 (100.0%)
0.07 (100.0%)
56.45 (100.0%)
Timcout
G2MILP " 0.01
0.58 (100.0%)
0.02 (1.7%)
802.3 (100.0%)
12.01 (10.0%)
MILP-StuDio 7) = 0.01
0.50 (.000%))
4,94 (100.0%)
1000 (100.0%)
1000 (100.0% %
G2MILP 77 = 0.05
0.69 (100.0%)
0.01 (1.8%)
0.14 (100.0%)
0.01 (0.0%)
MIL.--tuDio 7 = 0.05
0.48 (100.0%)
4.92 (100.0%)
691.66 (100.0%)
1000 (100.0 %)
G2MILP 1 = 0.10
0.72 (100.0%)
0.01 (2.0%)
0.03 (100.0%)
0.02 (0.0%)
MILP-StuDio 1 = 0.10
0.40 (100.0%)
4.64 (100.0%) 0%
550.33 (100.0%)
1000 (94.5 5)
Moreover, most of the instances generated by G2MILP in FA and WA datasets are infeasible. Encouragingly, MIL.PStuDDio is able to preserve the computational hardness and feasibility of the original instances, making it strong method for maintaining instances' mathematical properties.
We visualize the CCMs of the original and generated instances to demonstrate the effectiveness of MILP-StuDio in preserving block structures in Appendix G MILP-StuDio is able to preserve the block structures while all the baselines fail to do so.
5.3 Improving the Performance of Learning-basse based Solvers
GNN branching policy g and prdict-and--earde [10 are two representative approaches of learning- based solvers. Here we report the results of PS built on Gurobi and leave the other in Appendix [.1 In alignment with [10) we consider two additional baselines Gurobi and BKS. For each instance, we run Gurobi on a single-thread mode for 1 1,000 seconds. We also run Gurobi (5) for 3,600 seconds and denote the obtained objective values as the best-known solution (BKS). For more details on the implementation of PS, please refer to Appendix [H.]] Table demonstrates the performance of MILP-StuDio-enhanced PS and the baselines, where we set the modification ratio = 0.05. We report three metrics to measure the solving performance. (1) Obj represents the objective values achieved by different methods. (2) gapans is the absolute primal gap defined as gapats := |Obj BBS) where smaller gaps indicate superior primal solutions and, consequently, better performance. (3) Time denotes the average time used to find the solutions.
In CA and FA, all the approaches can solve the instances to the optimal with gapats = 0, thus we compare the Time metric. In IP and WA, all the approaches reach the time limit of 1,000s, thus we mainly focus on the gapats metric. Methods built on PS does not perform well in CA compared to Gurobi, since CA easy for Gurobi to solve and PS needs to spend time for network inference. Even so, PS achieves a comparable performance to Gurobi. In the other three datasets, SiL.--StDDi-enhaacee PS outperforms other baselines, achieving the best solving time or gapabs
5.4 Hard Benchmark Generation
The hard instance generation task is important as it provides valuable resources for evaluating solvers and thus potentially motivates more efficient algorithms. The objective of this experiment test the ability to generate harder instances within a given number of iterations. We use 30 original instances to construct the pool. each iteration, for each instance the pool, we employ mix-up or expansion operators to generate two new ones, and We then select the instance among and with the longest solving time to replace in the pool. This setting is to preserve the diversity of the pool. We observe that there exist slight differences in the hardness of the original instances, and the generated instances
8

---

Table 4: Comparison of solving performance in PS between our approach and baseline methods, under 1, 0000s time limit. In IP and WA, all the approaches reach the time limit, thus we do not consider the Time metric. The notation Infeasible implies that a majority of the generated instances are infeasible and thus cannot be used as the training data for PS. "1" indicates that higher is better, and '4' indicates that lower better. We mark the best values in bold.
CA (RKS 7453.42)
FA
IP (RKS 11.16)
WA 698.80)
Obj f
guPas L
Time
Obj
gapass 4 Time
Obj 4 gaPaha
Obj
gapats
Gurobi
7453.42
0.00
0.77
17865.38
0.00
7.36
11.43
0.27
698.85
0.05
PS
7453.42
0.00
0.94
17865.38
0.00
7.19
11,40
0.24
699.05
0.25
PS+Bowly
7453.42
0.00
0.93
17865.38
0.00
7.25
11.63
0.47
Timcout Infeasible
PS+G2MILP
7453.42
0.00
0.89
Infeasible
11.55
0.39
SS+MiLP-StuDio
7453.42
0.00
0.78
17865.38
0.00
7.07
11.29
0.13
698.83
0.03
200
Time Imi:
20
Average Time
150
153.4
18
16
100
14
50-
12
Iteration Step
0
Bowly
G2MILP
MILP-StuDio
Figure Mcan solving time during iterations.
Figure 6: Generation time of 1,000 instances in WA.
derived from the harder original instances are also harder than those from easier ones. If we had simply generated 60 instances and selected the hardest 30, the proportion of instances generated from the hard original instances would have continuously increased, reducing the diversity of the pool. In Figure we depict the growth curve of the average solving time of instances in the pool during 10 iterations. The solving time of the final set is two times larger than that of the initial set, suggesting MILP-StuDio's ability generate increasingly harder instances during iterations.
5.5 Extensive Studies
Generation Efficiency WA is challenging benchmark with large instance sizes. The instances in WA have over 60,000 constraints and variables, making generation WA especially consccnnu We compare the generation time of the generation techniques to generate 1,000 instances. We set the time limit to 200 hours. The results Table show that MILP-StuDio significantly archives 3x acceleration compared to G2MILP, demonstrating high generation efficiency.
More Results We conduct ablation studies on three operators and modification ratios in Appendix F2 and we also try to extend MILP-SStDD to MILPs without block structures in Appendix F.4 and MILPss in the real-world industrial dataset in Appendix[F. F.5
6 Related Work on MILP Generation
The field of MILP generation encompasses two main categories: problem-specific generation and general MILP generation. Problem-specific generation methods rely on expert knowledge of the mathematical formulation of problems to generate instances. Examples include set covering [15]. combinatorial auctions [16), and satisfiability [18). While these methods can generate instances tailored to specific problem types, they are limited in their applicability and require much modeling expert knowledge. On the other hand, general MILP generation techniques aim to generate MILPs using statistical information 20 or by leveraging neural networks to capture instance distributions 19 G2MILP [9 is the first learning-basee generation framework designed for generating general MIIPss This approach represents MII.Ps as bipartite graphs and utilizes masked variational auto-encoder [35] to iteratively corrupt and replace parts of the original graphs to generate new ones.

---

7 Limitations and Future Avenue
Our method originates from the field of operational research and designed for instances with block structures. The performance of the detector in GCG influences the overall generation quality. Although the detector can identify wide range of useful structures in the real world, it is still limited when facing instances with extremely complex structures, The exploration of enhancing the performance of the detector, such as those involving prior knowledge the instances, represents a promising avenue for future research.
8 Conclusion
In this paper, we propose a novel MILP generation framework AMILP-SSuliig to generate high-quality MILP instances. Inspired by the studies of CCMs in operational research, MILP-StulDio manipulates the block structures CCMs to preserve the mathematical properties-includnng the computational hardness and fcasibility-off the instances. Furthermore, MILP-StuDio has a strong ability of scalable generation and high generation efficiency. Experiments demonstrate the effectiveness of MILP-StuDio in improving the performance of learning-based solvers.
9
Acknowledgement
The authors would like to thank all the anonymous reviewers for their insightful comments and valuable suggestions. This work supported by the National Key R&D Program of China under contract 2022ZD011980 and the National Nature Science Foundations of China grants U23A20388 and 62021001.
References
[1] John A Muckstadt and Richard C Wilson. An application of mixed-intesd programming duality to scheduling thermal generating systems. IEEE Transactions on Power Apparatus and Systems, (12), 1968.
[2] Yves Pochet and Laurence A Wolsey. Production planning by mixed integer programming. volume 149. Springer, 2006.
[3] Kefan Ma, Liquan Xiao, Jianmin Zhang, and Tiejun Li. Accelerating an fpga-based sat solver by software and hardware co-design. Chinese Journal of Electronics, 28(5):953-995 3013991,,2200 2019.
[4] Zhihai Wang, Jie Wang, Yinqi Bai Qingyue Yang, Xing Li, Lei Chen, Jianye Hao, Mingxuan Yuan, Bin Li, Yongdong Zhang, and Feng Wu. Towards next cext-generation logic synthesis: A scalable neural circuit generation framework. In The Thirly-eighth Annuul Conference Neural Information Prucessing Systems, 2024.
[5] LLC Gurobi Optimization. Gurobi optimizer. URL http://www. gurobi. com, 2021.
[6] Tobias Achterberg. Scip: solving constraint integer programs. Mathematical Programming Computation, 1:1 11144,,22 2009.
[7] He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
[8] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
[9] Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning selection for mixed-integer linear programming via hierarchical sequence model. In The Eleventh International Conference on Learning Representations, 2023.
[10] Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A gun-gedded predict-and-seare framework for mixed-integer linear programming. In The Eleventh International Conference on Learning Representations, 2023.
10

---

[11] Byoung- Woon Kim and Chong-Min Kyung. Exploiting intellectual properties with imprecise design costs for system-on-chie synthesis. IEEE Transactions on Very Large Scale Integration (VISI) Systems, 10(3):240-222, 2002. doi: N0.1109/TV1.SS.2022.00000 10433327..
[12] Jun Sakuma and Shigenobu Kobayashi. A genetic algorithm for privacy preserving combinato- rial optimization. In Proceedings of the 9th annual conference Genetic and evolutionary computation, pages 1372-1379, 2007.
[13] Russ J Vander Wiel and Nikolaos V Sahinidis. Heuristic bounds and test problem generation for the time-dependent traveling salesman problem. Transportation Science, 29(2):167-183, 1995.
[14] David Bergman, André Augusto Ciré, Willem Jan van Hoeve, and J. Hooker. Decision diagrams for optimization. Constraints, 20:494 4944944495.,9 495, 2015.
[15] Egon Balas and Andrew Ho. Set covering algorithms using culting planes, heuristics, and subgradient optimization: a computational study. Springer, 1980.
[16] Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards universal test suite for combinatorial auction algorithms. In Proceedings of the 2nd ACM Conference on Electronic Commerce, pages 66-76, 2000.
[17] Gérard Cornuéjols, Ramaswami Sridharan, and Jean-Michel Thizy. A comparison of heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research, 50:280-297, 1991.
[18] Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, and Jure Leskovec. G2sat: learning to generate sat formulas. Advances in neural information processing systems, 32, 2019.
[19] 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, 2023.
[20] Simon Andrew Bowly. Stress testing mixed integer programming solvers through new test instance generation methods. PhD thesis, School of Mathematical Sciences, Monash University. 2019.
[21] Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear optimization, volume 6. Athena Scientific Belmont, MA, 1997.
[22] Guy Desaulniers, Jacques Desrosiers, and Marius M Solomon. Column generation, volume 5. Springer Science Business Media, 2006.
[23] Marco E Lübbecke and Jacques Desrosiers. Selected topies in column generation. Operations research, 53(6): 1007-1033, 2005.
[24] Daniel Bienstock George Nemhauser and I. Wolsey. Integer programming and combinatorial optimization, 1993.
[25] George B. Dantzig and Philip Wolfe. Decomposition principle for linear programs. Opera- tions Research, 8: 1011 1960. Itt.httts://app. www.nticscoollaatttt.... httpaattissccclaaaaorooorrruuuoe C 61768820
[26] FG Commoner. A sufficient condition for a matrix to be totally unimodular. Networks, 3(4): 351-365, 1973.
[27] Ilias Mitrai, Wentao Tang, and Prodromos Daoutidis. Stochastic blockmodeling for learning the structure of optimization problems. AIChE Journal, 68(6)) 2022.
[28] Jiacheng Lin, Meng XU, Zhihua Xiong, and Huangang Wang. CAMBranch: Contrastive learning with augmented MILPss for branching. The Twelfth International Conference on Learning Representations, 2024. URL httpp///wwrreeeeeeeeeoooo///////
11

---

[29] Zachary Steever, Chase C. Murray. Junsong Yuan, Mark H. Karwan, and Marco E. Lübbecke. An image-base basee approach to detecting structural similarity among mixed integer programs. INFORMS J. Comput., 34(4): 1 1890- 2022. doi: 10. N0.1288//10..2021.1111 URL https
//doi.org/ 10. 1 2021 1117
[30] JAKUB MARE. Exploiting structure in integer progrums. PhD thesis, Citeseer, 2011.
[31] 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 compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443-490, 2021.
[32] Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Alcksandr M. Kazachkov, Elias Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J. Maddison, Morris Christopher, Dimitri Papageorgio,, Augustin Parjadis, Sebastian Pokutta, Antoine Prouvost, Lara Scavuzzo, Giulia Zarpellon, Linxin Yang. Sha Lai, Akang Wang, Xiaodong Luo. Xiang Zhou, Haohan Huang, Shengcheng Shao, Yuanming Zhu, Dong Zhang, Tao Quan, Zixuan Cao, Yang Xu, Zhewei Huang, Shuchang Zhou, Chen Binbin, He Minggui, Hao Hao, Zhang Zhiyu, An Zhiwu, and Mao Kun. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In Douwe Kiela, Marco Ciccone, and Barbara Caputo, editors, Proceedings of the NeurlPS 2021 Competitions and Demonstrations Track, volume 176 of Proceedings of Machine Learning Research, pages 220-231. PMLR, 06-14 Dec 2022. URL https:// proceedings mlr. pwwss/vv76..... gassee2a. html
[33] Gerald Gamrath and Marco E. Lübbecke. Experiments with a generic dantzig- decompo- sition for integer programs. In The Sea, 2010. URI, (tRl.httss://// sta//pppp.eemmtiicccccoollaa http:///awp.......oo//////e..eaa CorpusID: 14380165
org/
[34] Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: bench- marking models for de novo molecular design. Journal of chemical information and modeling, 59(3):1096-1) 108, 2019.
[35] Diederik P Kingma and Max Welling, Auto-encoding variational bayes. arXiv preprint arXiv:1312.61 14, 2013.
[36] Xijun Li, Fangzhou Zhu, Hui-Ling Zhen, Weilin Luo, Meng Lu, Yimin Huang, Zhenan Fan, Zirui Zhou, Yufei Kuang, Zhihai Wang, Zijie Geng, Yang Li, Haoyang Liu, Zhiwu An, Muming Yang, Jianshu Li, Jie Wang, Junchi Yan, Defeng Sun, Tao Zhong, Yong Zhang, Jia Zeng, Mingxuan Yuan, Jianye Hao, Jun Yao, and Kun Mao. Machine learning insides optverse ai solver: Design principles and applications, 2024.
[37] Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33: 18877-18888, 2020.
[38] Prateek Gupta, Elias B Khalil, Didier Chetélat, Maxime Gasse, Yoshua Bengio, Andrea Lodi, and M Pawan Kumar. Lookback for learning to branch. arXiv preprint arXiv:2206.1 14987, 2022.
[39] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' D'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja. Pengming Wang. et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349 2020.
[40] Jie Wang. Zhihai Wang, Xijun Li, Yufei Kuang, Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng. Yongdong Zhang, and Feng Wu. Learning to cut via hierarchical sequence/set model for efficient -inteer programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1-17, 2024. doi: 10. 109/TPAMM..2244443377
[41] Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer pro- gramming: Learning to cut. Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9367-9376. PMIR, 13-18 Jul 2020. URL. https //proceedings. mll. iieess/v19/ttageee htmml html
12

---

[42] Zeren Huang. Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Min jie Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed -nteger program- ming. Pattern Recognit, 123:108353, 2021. URL UtR.https:// htttss:/appl semanticscoolar org/
CorpusID:236247861
[43] Haotian Ling, Zhihai Wang, and Jie Wang. Learning to stop cut generation for efficient mixed- integer linear programming. Proceedings of the AAAI Conference on Artificial Intelligence, 38 (18):20759-200)) 207677 Mar. 2024. doi: 10.1609aaai. v.8v 18.0004, URL URLhttps: //ojs. aaai org/index, php/ http///arrcc//e////0005
[44] Abdel Ghani Labassi, Didier Chetelat, and Andrea Lodi. Learning to compare nodes in branch and bound with graph neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors. Advances in Neural Infor- mation Processing Systems, volume 35, pages 32000-32010. Curran Associates, Inc., wtt.e////paaee///////eea Conf wwwnee.eneee.... pdf
2022. URL httpos://procooddings newrips. cc https/ccpppppeeeeseeeeeeeeeeeeee 0ebb1188743eecffaaa16666666
[45] Yufei Kuang, Xijun Li, Jie Wang, Fangzhou Zhu, Meng Lu, Zhihai Wang, Jia Zeng, Houqiang Li, Yongdong Zhang, and Feng Wu. Accelerate presolve in large-scale linear programming via reinforcement learning. arXiv preprint arXiv:2310. 1845, 2023.
[46] Chang Liu, Zhichen Dong, Haobo Ma. Weilin Luo. Xijun Li, Bowen Pang. Jia Zeng, and Junchi Yan. 1.2p-MIP: Learning to presolve for mixed integer programming. In The Twelfth International Conference on Learning Representations, 2024. URL httLhhtps: /tttps://openreview
het/foruuntdd=McfYiitp"
[47] Huigen Ye, Hua Xu, and Hongyan Wang. Light-MIL Solving large-scale mixed integer linear programs with lightweight optimizer and small-scale training dataset. In The Twelfth International Conference on Learning Representations, 2024. httpttt//tppprrreeeetts
net/forum?ine id www.:mmddddddddddiooo 2odd222/oumm661
[48] Huigen Ye, Hua Xu, Hongyan Wang, Chengming Wang, and Yu Jiang. GNN&GBDT-quided fast optimizing framework for large-scale integer programming. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 39864-39878 PMLR, 23-29 Jul 2023. URL https //proceedings. mlr, prwss/ w202/ye23e...ee html
[49] Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning a large neighhorhood search algorithm for mixed integer programs. ArXiv, abs/2107.10201, 2021.
org/ htg/CorppusDD :261142355
[50] Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra N. Dilkina, and Benoit Steiner. Search- ing large neighborhoods for integer linear programs with contrastive learning. In Interna- tional Conference on Machine Learning, 2023. URL CorpusID:256598829
http://cp...ematicccccccooollaa. org/
[51] Ted K. Ralphs and Matthew V. Galati. Decomposition methods for integer programming. 2011. :trg/CorpusID:1220000 122662809
URL htL.ttts:: www.:eiiiaaanniinaeeeee
[52] George B. Dantzig and Philip Wolfe. Decomposition principle for linear programs. Opera- tions Research, 8:101-111, 1960. URL ptttpp::/apii.smmaticooo
org/CorpusID
61768820
[53] George Bernard Dantzig and Mukund Narain Thapa. Linear programming: Theory and extensions, volume 2. Springer, 2003.
[54] Brian T. Denton, Andrew J. Miller, Hari Balasubramanian, and Todd R. Huschka. Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper: Res., 58(4-Part-1) I): 802-816, 2010. doi: 10. 10.1 1090.00791. URL. ltttts://////t http:://doooooo/o///// 10. 1287 opre 1090. 11990.7911
13

---

[55] Hans Kellerer. Ulrich Pferschy, and David Pisinger. Multiple Knapsack Problems, pages 285
316. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. ISBN 978-3-540-24477-7 doi:
http:///w....aaa//////////////// http::///4a..oo////...0000//5633 10. 10.1007/978.33554-447777 10.
10
[56] Gonzalo E. Constante-Florr and Antonio J. Conejo. Security-constranned unit commitment: decomposition approach embodying kron reduction. Eur J. Open: Res., 319())427-441
2024. doi:
2023
06. 013
[57] T. C. Hu, Multi-commodity network flows. Operations Research, 11:344-360, 1963. URL
ortp:ttacccc.....ooroor/paaaaaaa 1219322073
[58]
Alessandro Lonardi, Mario Putti, and Caterina De Bacco. Multicommodity routing optimization for engineering networks. Scientific Reports, 12(1):7474, May 2022. ISSN 2045-2322. doi: 10. (0.1038/s41598-022 1348-9. URL httphtts / www.oo........... 10. 1038/ s41598-022 11348-9
[59] Alexander Cowen-Rivers, Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan-Rhys Grifliths, Alexandre Maravel, Jianye Hao, Jun Wang, Jan Peters, and Haitham Bou Ammar. Hebo:
Pushing the limits of sample-efficient hyperparameter optimisation. Journal of Artificial Intelligence Research, 74, 07 2022.
[60] Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. In Learning Meets Combinatorial Algorithms at NeurIPS2020, 2020. URL https
14

---

Table of Contents for Appendix
More Related Work
16
A.1 Machine Learning for Solving MILP
16
A.2 MILP with Block Structure
16
Broader Impacts
16
The Importance of MILPs with Block Structures
17
Explanation:
Why do the MILPs Exhibit Block Structures?
17
E
Introductions the Underlying Learning-Bans Based Solvers
18
Learning Branch
18
Predict-and-Seaun
18
F
Extensive Experiment Results
19
F1
Experiments on Learning Branch
19
F2
More Results on Different Generation Operators and Modification Ratios
21
F3
Enhancing the Traditional Solvers via Hyperparameter Tuning
22
More Results on Non-Structured MILPs
23
More Results on Real-world Industrial Dataset
25
Visualizations of CCMs
25
Implementation Details
26
H.1
Implementation of Predict-and-Seard)
26
H.2
Implementation of Classification Algorithm for Constraints and Variables
29
H3
Implementation of Partition Algorithm for Block Units
29
H.4
Details on Block Manipulation
31
More Details the Data and Experiments
32
Details on Bipartite Graph Representations
32
2 Details on the Benchmarks
32
1.3
Details on Graph Distributional Similarity
33
15

---

A More Related Work
A.1 Machine Learning for Solving MILP
In recent years, there has been notable progress in utilizing machine learning approaches to accelerate MILP solvers [36]. The geaning-baseed approaches for solving MILPs be broadly categorized into two main groups. The first group of works replaces specific components of the solver that greatly
impact solving efficiency, such branching 3 (7-39] cut selection 440 9 41] node selection
7 44] and presolve [45 46]. These approaches are integrated into exact MILP solvers, ensuring that
the resulting solutions are optimal. However, they also inherit the limitation of exact solvers, which can be time-consuming for solving large-scale instances.
The second category includes Saaming-aided search approaches, which encompass techniques such as predict-and-oge speeitt-and-optimize [10] 44 488. large neighbor search [49 [50] and so on. Among these methods, peddict-and-earchl (PS) [10] has gained significant popularity. In PS, machine learning model is first employed to predict a feasible solution, which is then used as an initial point for a traditional solver to explore the solution space and find the best possible solution within defined neighborhood. By leveraging the predicted feasible solution, PS effectively reduces the search space of the solver, leading to accelerated search and the discovery of high-quality solutions.
By leveraging machine learning techniques, these approaches have demonstrated substantial im- provements in the solving efficiency and solution quality of MILP problems. However, training such learning-bast -basen models requires many MILP instances as training data, which can be challenging to obtain in real- wellwwold applications [19]. There is still ongoing research in this area to improve the sample efficiency of these solvers [0 and study the MILP generation techniques [9].
A.2 MILP with Block Structure
Operational researchers have observed that a great number of real-world MILP problems exhibit block structures within their constraint coefficient matrices (CCMs) 30 27 These problems are prevalent in various applications, including scheduling, planning, and knapsack scenarios [31 [6] Thus, many researchers have focused on understanding the impact of these block structures on the mathematical properties of the instances, and how to leverage them to accelerate the solving process(21] 24 26 51). Among this stream of research, the Dantzig- Wolfe decomposition (DWD) [52] stands out as one of the most successful applications. Many classical textbooks linear pro- gramming dedicate sections to discussing this decomposition algorithm [53] 21), underscoring its importance. DWD is widely utilized when CCM contains both block -lcck-diagonals and coupling con- straints [52). and can significantly accelerate the solving process for large-scale linear programming
and mixed-integer linear programming.
To identify the block structures a raw CCM, the state-of-the-an detecting algorithm is implemented in GCG (Generic Column Generation) [33, distributed with the SCIP framework (6). This sophisti- cated algorithm utilizes row and column permutations to effectively cluster the nonzero coefficients in CCMs, thereby revealing distinct block structures, including the useful block-diagonal, bordered block- -dakolaa,,,,,,, and doubly bordered block-diagonal structures.
B Broader Impacts
This paper introduces a MILP instance generation framework (MILP-StuDio) that aims to generate additional MILP instances with highly similar computational properties to the original instances. Our approach holds significant potential in numerous practical applications and important engineering scenarios, including scheduling, planning, facility location, etc. With instances generated by MILP. StuDio, we can improve the performance of block-box learning- based or traditional solvers at a low data acquisition cost. One notable advantage of our proposed method that it does not rely on the knowledge of MILP formulations and can be applied to general MILP instances, eliminating concerns regarding privacy disclosure. Furthermore, as a alug-and-play module, MII. StuuDo offers great convenience for users.
16

---

C
The Importance of MILPs with Block Structures
The MILPs with block structures are important in industrial and academic fields. We found that MILP instances with block structures are commonly encountered in practical scenarios and have been important topic in operations research (OR) with much effort [25 54].8..
MILP with block structures is an important topic in OR. Analyzing block structures is critical tool for analyzing the mathematical properties of instances or accelerating the solving process (e.g.. Dantzig- Wolfe decomposition (25) in OR. The MIPLIB dataset also provides visualization results of the constraint coefficient matrices for each instance, highlighting the prevalence of block structures.
The MILP instances with block structures are common and have wide applications in daily production and life. There are many examples where the instances present block structures, including the allocation and scheduling problems [54], the multi-knapsaan
problem [55], the courtty-oonstrained unit commitment problem in electric power systems [56], multicommodity network flow [57], multicommodity transportation problem (58) and so on. In real-world optimization scenarios, there are different types of similar items-such as different workers or machines in planning and scheduling problems, set of power generation units in the electric power systems, vehicles in the routing problems, and so on- with relevant variables naturally presents block-structured form in the mathematical models.
The datasets we used in this paper (IP and WA) are from real-world applications. The NeruIPS 2021 Competition of Machine Learning for Combinatorial Optimization (32) released three well- recognized challenging datasets from real-world applications (IP, WA, and the anonymous dataset). Two of the three competition datasets (IP and WA) have block structures. Moreover, instances from the anonymous dataset are selected from MIPLIB with large parts having block structures. These further reflect the wide application of block structures in real-world applications. Thus, our method works in a wide range of problems in practice.
Researchers have investigated specific MILP problems with block structures. MILP with block structures has a large scope the optimization field and there has been a wide range of works on specific problems with block structures, and they have developed a suite of optimization problems tailored to these problems. For example, the tailored algorithm for the commitment problem in electric power systems [4], multicommodity transportation problem [6], vehicle routing problem [7], and so on.
constrained unit
Thus, MILP with block structures has a large scope in production and optimization. It has drawn much attention in the industry and academic fields.
D Explanation: Why do the MILPs Exhibit Block Structures?
The key reasons why MILP instances exhibit block structures can be summarized as follows.
Repeated items or entities with similar attributes. many real-world applications involving scheduling, planning, and packing problems, we often encounter multiple items or entities that share the same type or attributes. For instance, be multiple destinations or vehicles that exhibit similar characteristics. Similarly, in knapsack problem, there can be multiple packages or items that are interchangeable from the perspective of operational research or mathematical modeling.
scheduling problem, there may
Symmetric interactions between different types of items. These repeated items or entities, as well as their interactions, lead to symmetries in the mathematical formulation of the MILP instances. For example, in scheduling problem, all the vehicles may be able pick up items from the same set of places and satisfy the demand of the same set of locations.
These symmetries in the problem structure are reflected in the blocks of CCMs, where each block may represent the information associated with certain vehicle, destination, other item type.
important to note that although StuDoS designed primarily for MILP instances with block structures, it has broader application to a wider category of problems, including those with more complex block structures (Appendix H.4), blocks of different sizes (Appendix (H.4), and even non-structural MILPs (Appendix F.4
17

---

E Introductions the Underlying Learning-Based Solvers
E.1 Learning to Branch
Branching is a critical component of branch-ane sarucchannd-booee and-bound (B&B) solvers for mixed-integer linear programming (MILP) problems. It involves selecting fractional variable to partition the feasible region in each iteration. The effectiveness of the chosen variable and the time required to make the search
branching decision are crucial factors that heavily impact the size of the branch-and- tree and, consequently, the solver's efficiency. Thus, there have been many efforts to develop effective and efficient branching policies. Among the conventional branching policies, the strong branching policy has been demonstrated to yield the smallest branch-and saanch-nnd-boune bound trees. This policy identifies the fractional variable that provides the largest improvement in the bound before performing the branching operation. However, the evaluation process associated with strong branching involves solving considerable number of linear relaxations of the original MILP, resulting in unacceptable time and computational costs.
To address the limitations of strong branching, 8 proposes GNN-based approach that employs behavior cloning to imitate the strong branching policy. In this approach, the B&B process is formulated Markov decision process, with the solver acting as the environment. At each step, the branching policy receives the current state S, which includes information on past branching decisions and current solving statistics. Subsequently, the policy selects action a from the set of integer variables with fractional values in the current state. The researchers parameterize the branching policy GNN model, which serves fast approximation of the strong branching policy.
During the training process, we first run the strong branching expert on the training and testing instances to collect the state-action pair (s, a), forming the training dataset Prain and testing dataset Deet. The GNN branching policy Hy is then trained by minimizing the cross-entropy loss
((0)
Σ
log To (a s).
DDusin
(s,
The imitation accuracy refers to the consistency of the learned GNN policy compared to the strong branching expert on the testing dataset Diest:
ACC
Σ
II arg max (a(a
DDest
(s,
where is the indicator function defined as I(c) = i if the condition c is true, and I(c) 0 otherwise. The imitation accuracy of the GNN model reflects the similarity between the learned branching policy and the expert policy, and it significantly impacts the solver's efficiency.
E.2
Predict-and-Search
Different from learning-to-branchh which replaces certain heuristies in a traditional B&B solver, Predict-and-Seant (PS) [10] belongs to another category of learning- based solvers that directly predict a feasible solution and subsequently perform the neighborhood search. PS aims leverage learning- based model to approximate the solution distribution p(z I) given an instance I from the instance dataset DD. Given an instance I, the solution distribution p(x [T defined as follows:
exp(-E(xx, I))
TTT2. xx, if x is feasible, where the energy function E(x, +oo, otherwise.
p(= I) Σ exp(-E((zII)
In the prediction step, PS employs GNN model to approximate the solution distribution for the binary variables in a MILP instance. To train the GNN predictor po (x [T. PS adopts the assumption, as described in 39), that the variables are independent of each other, i.e., Po (x: Σ)= = II Po (x; I). To calculate the prediction target, PS collects a set of m feasible solutions for each instance I, is constructed. Here, p; p(x; 1|Z) represents the
from which vector p (p1.
probability of variable I; being assigned the value 1, given the instance I. The GNN predictor then outputs the predicted probability pe pa( 1[Z) for each variable. Finally, the predictor pe trained by minimizing the cross-entropy loss
((6)
Σ
(ps (o = I,, + (1 - p.) log(1 po 1 I,)))
j=
18

---

where N represents the number of instances in the training set.
In the search step, PS performs the neighborhood search based the predicted partial solution i. This involves employing a traditional solver, such as SCIP [ or Gurobi [5] to explore the neighborhood ( A) of æ in search of optimal feasible solution. Here A represents the trust. region radius, and ( 4) {æ E R" || æ||1 S. 4} is the trust region. The neighborhood search process is formulated as the following MILP problem.
min
cJx, s.t. A S b, x u.
ZER
It is worth noting that the accuracy of the GNN predictor strongly influences the overall solving performance. reliable and accurate prediction of a feasible solution can effectively reduce the search time. Conversely, an inaccurate prediction may result in an inferior search neighborhood and sub-optimal solution.
F Extensive Experiment Results
F.1
Experiments on Learning to Branch
In this section, we conduct experiments on the learning-to-brane task further demonstrate the effectiveness of MIL in enhancing the learning- -baed solvers.
We conduct the learning-to-brand branch experiments following the setting described in the original paper [8] In our experiments, we evaluate the performance of the solvers using two benchmark problems: the capacitated facility location (FA) and item placement (IP) problems. The capacitated facility location problem (FA) is chosen
Experiment Setup
representative problem that solvers can successfully solve within the given time limit. This problem serves as a benchmark to test the solving efficiency of solvers. The item placement problem (IP) is selected solvers struggle to find the optimal solution within the given time limit. By including this challenging problem, we can gain insights into the solvers' ability to find a high-quality primal solution.
benchmark where the
The training, validation, and testing instance sets used in this work are identical to those described in the main paper. Specifically, for each benchmark, we use 100 training instances, 20 validation instances, and 50 testing instances. To generate training samples, we execute the strong branching expert on instances in each benchmark, collecting 1,000 training samples, 200 validation samples, and 200 testing samples. For the final evaluation, we test the solving performance on 50 instances.
We implement the model with the code available at / http://///g/uuuuuuoge wtw.ttttwooooooeeettottotttttttt com http//s4d///// http///ddmmmmeeennnee lettm/eeeannbbacccc This code leverages the state-of-the-ard open-source solver SCIP 8.0.3 [6] as the backend solver. During lesting, the solving time limit for each instance is set to 1,000 seconds. Consistent with the setting in [ we disabled solver restarts and only allowed the cutting plane generation module to be employed at the root node.
Baselines The first bascline we consider is the GNN model (8), which is trained on an initial set of 1,000 samples collected from 100 original instances (GNN). To explore the effectiveness of different instance generation techniques, we use the same set of 100 training instances to generate an additional 1,000 instances using each technique. Subsequently, we collect 10,000 training samples by running a strong branching expert again on these instances. combination with the original 1,000 samples, we have a comprehensive enriched training dataset consisting of 11 11,000 samples. Thus, the three generation techniques lead to the following approaches: GNN+Bowly, GNN+G2MILP 1) x, where 77 implies that we set the modification ratio to be
7 x, CWN+MMI.P-StUD. ar. Additionally, we compare our method with GNN model trained on 11,000 samples collected from 1,100 original instances (GNN-/ /000). This comparison allows us to demonstrate that the improvement achieved by our approach is not only due to an increase in the number of training samples but also the high quality of the generated instances. To provide comprehensive evaluation, we also compare the solving performance of our method with that of the SCIP solver [ (SCIP), which serves as our backend solver for comparison purposes.
Experiment Results and solving performance. As discussed in Appendix E.T imitation accuracy serves crucial
this section, we conduct a comprehensive comparison of imitation accuracy
19

---

Table Comparison of branching accuracy on the testing datasets. 'Trivial samples' implies that the computational hardness of the generated instances is so low that the solver does not need to perform branching to solve them. As a result, we are unable to collect any branching samples for these trivial instances. We mark the best performance in bold among the methods using the generation technique. We can see that PtSulooo can consistently improve the branching accuracy of the learned models.
IP
GNN-I 1000
0.621
0.780
GNN
0.545
0.640
GNN+Bowly
Trivial samples
0.358
GNN+G2MILP v 0.01
0.535
0.765
GNN+G2MILP 1y 0.05
0.545
0.705
GNN+G2MILP v = 0.10
0,560
0,705
GNN=MILP-StuDio 0.01
0,585
0.800
UNN+MILP-StuDDe 7 0.05
0.605
0.790
MON+MILP-StuDie 7 0.10
0.560
0.740
Table 6: Comparison of solving performance in learning-to-branch between our approach and baseline methods, under 1, 000-second time limit. 'Obj' represents the objective values achieved by different methods and 'Time' denotes the average time used to find the solutions. "J" indicates that lower is better. We mark the best values in bold. 'Trivial samples' implies that the computational hardness of the generated instances is so low that the solver does not need to perform branching to solve them. As result, we are unable collect any branching samples for these trivial instances.
FA
IP
Obj
Time
Obj 4
Time 4
SCIP
17865.38
58.18
22.03
1000.00
GNN-1000
17865.38
51.63
20.72
1000.00
GNN
17865.38
55.06
21.04
1000.00
Bow++Bolly
Trivial samples
22.58
1000.00
GNN+G2MILP 7 0.01
17865.38
58.81
21.09
1000.00
GNN+G2MILP 7 0.05
17865.38
61.33
22.11
1000.00
GNN+G2MILP 17- 0.10
17865.38
59.64
20.93
1000.00
GNN+MILP -tuuLi n = 0.01
17865.38
48.28
20.03
1000.00
MON-MILP-StDDie 0.05
17865.38
47.58
21.00
1000.00
ONN+MILP-SuDDD. n 0.10
17865.38
53.70
20.39
1000.00
metric for evaluating the performance of the GNN model. Thus, we first compare our methods with other GNN-based baselines, including GNN, ANN-11000. GNN+Bowly, and GNN+G2MILP regarding imitation accuracy. The corresponding results are presented in Table where we observe that StuuiS yields the most significant improvement in imitation accuracy. Interestingly, we find that the instances generated by Bowly in FA are computationally trivial, such that the solver does not need to perform any branching operations to solve them. Consequently, we are unable to collect additional branching samples from these trivial instances to further train the GNN model.
Furthermore, we evaluate the solving performance of the different baselines, as summarized in Table eechnique-enhanced baselines and
6. Notably, SANN+MLP--StDD outperforms all the achieves comparable solving performance of GNN-11000 This suggests that incorporating the MILP-StuDio method can boost the performance of the GNN branching policy. We also find that the generated data from MILP-StuDio with different modification ratios can be beneficial for training the GNN model while using instances generated by the G2MILP method may potentially disrupt the training of the GNN model. These findings substantiate the effectiveness MtuuDStuDio in enhancing the GNN branching policy, both in terms of imitation accuracy and solving performance.
20

---

Table 7: Structural similarity scores between the generated and original instances in FA. We compare the effect of different generation operators and modification ratios. We find that the mix-up up operator can generate the most realistic instances.
0.01
1
0.05
7f
0.10
G2MILP
0.358
0.092
0.091
MILP-StuDio (red)
0,541
0,515
0.474
MILP-StuDia (mix)
0.907
0.908
0.907
MtLP-StuDio (exp)
0.543
0.517
0.475
Table 8: Average solving time (s) and feasibility of instances solved by Gurobi. is the masking ratio. Numbers in the parentheses are feasible ratios in the instances. The instances generated by the G2MIL are found to have extremely low feasible ratio.
1) = 0.01
17 0.05
7) 0.10
G2MILP
0.02 (1.7%)
0.01 (1.8%)
0.01 (2.0%)
MILP-StuDio (red)
4.29 (100.0%)
4.46 (100.0%)
4.26 (100.0%)
MILP-StuDio (mix)
5.35 (100.0%)
5.00 (100.0%)
4.26 (100.0%)
MILP- (exp) 5.18 (100.0%)
5.30 (100.0%)
5.42 (100.0%)
F.2 More Results on Different Generation Operators and Modification Ratios
In this part, we investigate the influence of different generation operators and modification ratios of Mtt.P-ttDDo. "MIL.-StuDio (Optor) r = x² denotes the generation approach that uses the operator Optor ('red' means reduction, 'mix" represents mix-up, and 'exp' denotes expansion) and modification ratio 77 =..
Influence on the Similarity between the Generated and the Original Instances We conduct experiments the FA benchmark. We first compute the graph distributional similarity score for the 100 original instances and 1,000 instances generated using different operators and modification ratios. The results presented in Table suggest that the choice of generation operator and modification ratio can impact the values of the similarity scores. (1) MIL.-StuDio consistently outperforms G2MILP in similarity scores. (2) Among the three operators, mix-up achieves the highest similarity scores, with values exceeding 0.8 across the modification ratios. Although the reduction and expansion operators yield lower similarity scores, they are still able to achieve comparable performance in the downstream tasks, as shown in the following paragraph. This finding indicates that there is not necessarily a positive correlation between the structural similarity scores and the benefits for the downstream tasks.
We also evaluate the computational properties of the generated instances. The results in Table g show that the three operators are able to preserve the computational hardness of the original instances. Importantly, all the operators succeed in generating feasible instances, which is a crucial requirement for the downstream tasks. In contrast, the instances generated by the G2MILP approach are found to have an extremely low feasible ratio.
Moreover, the modification ratio increases, we observe a decrease in the similarity scores. Consid- ering the good computational properties we have discussed, this finding suggests that the increasing modification ratios lead to the generation of more novel instances. This observation indicates that MILP-StuDio is able to generate instances increasingly distinct from the original data, while still preserving the computational hardness and feasibility properties.
Influence of Generation Operators on the Performance of Predict-and-Search We investigate the influence of instances generated with different operators on the performance of Predict-and- Search (PS). Specifically, we conduct experiments on the FA and IP benchmarks, using 1,000 generated instances based on 100 original instances and different operators. For comparison, we also report the results of SI-MILLP-StDDD
0.05. In PS+MILP-StuDD 7 0.05, we use the three
21

---

Table Comparison of prediction loss on the testing datasets for different generation operators. We set the modification ratio 17 0.05. We mark the best values in bold.
FA
IP
PS
20.45
341.33
PS+MILP- 1y 0.05
18.25
341.33
PS+MILP PtSuuDo (red) r 0.05
15,33
341.33
PS+MII Pt-StuDio (mix) 0.05
20.44
341.33
P-SuuDi (exp) = 0.05
20.56
341.33
Table 10: Comparison of solving performance in PS between different operators of MILP-StuDio, under 1, 000-second time limit. In the IP benchmark, all the approaches reach the time limit of 1.000s, thus we do not consider the Time metric. * indicates that lower is better.
FA (BKS 17865.38)
(BKS 11.16)
Obj 4
gaPabs +
Time +
Obj 4
gdPats
PS
17865.38
0.00
7.19
11.40
0.24
PS+MILP DS-MILP-StuDio
StuDio y 0.05
17865.38
0.00
7.07
11.29
0.13
PS+MILP-StuDii (red) = 0.05
17865.38
0.00
7.01
11.38
0.22
PS+MILP-StuDio (mix) 0.05
17865.38
0.00
6.95
11.32
0.16
PS+MII.P-StuDio (exp) 7 0.05
17865.38
0.00
6.96
11.37
0.21
operators (red, mix, and exp) to generate 1,000 instances (333, 334, and 333 using the three operators, respectively). The results are presented in Tables and [0] which compare the prediction loss and solving performance on the testing datasets for the different methods. The key findings are as follows. (1) All three generation operators are beneficial for the performance of the PS algorithm. (2) The PS algorithm is not overly sensitive to the choice of generation operator (3) The most beneficial operator may differ across different benchmarks.
Influence of Modification Ratio on the Performance of Predict-and-Search We investigate how the modification ratio impacts the performance of PS. Specifically, we conduct experiments on the FA and IP benchmarks, generating 1,000 instances using 100 original instances with different modification ratios (0.01, 0.05, 0.10] for both the MILP- PS+MM..-SSuDDo, we use the three operators (red, mix, and exp) to generate one-third of the 1 1,000 instances, respectively. The results are presented in Tables IT and 12] in which we compare the prediction loss and solving performance on the testing datasets for the different methods. Tables [I and showcase the following results. (1)
and G2MILP approaches. In
consistently outperforms G2MILP across modification ratios, (2) A smaller modification ratio MILP-StuDio can lead to slightly better performance of PS. (3) MILP StuDio is not sensitive the masking ratio in general.
F33 Enhancing the Traditional Solvers via Hyperparameter Tuning
In our Gurobi hyperparameter tuning experiment, We employ the Bayesian optimization framework provided by the HÉBO package [59]. Each tuning process involves 100 trials, where different hyperparameter configurations are sampled and evaluated. To strike balance between tuning effi- ciency and effectiveness, we focus on optimizing eight key hyperparameters: Heuristics, MIPFocus, VarBranch, BranchDir, Presolve, PrePasses, Cuts, and Method. We list and briefly introduce the key hyperparameters in Table [3
We utilize the Bayesian optimization package HEBO [59] to perform hyperparameter tuning for the Gurobi solver. We start by using the original dataset consisting of 20 FA instances and generate an additional 200 instances using the MILP-StuDis framework with a modification ratio of 0.05. This enriched dataset is then used to run the hyperparameter optimization process, where we perform 100 trials to search for the best parameter configuration. Finally, we evaluate the performance of the tuned Gurobi solver on testing dataset of 50 instances. We denote the default Gurobi as Gurobi, the Gurobi tuned on the 20 original instances as Gurobi-tuned, and the Gurobi tuned with additional instances generated by Bowly, G2MILP, and Mtu.P-tuDio as tuned-Bowe
tuned-G2n medd-G2MIL... and tuned-MILP MILP-StuDio, respectively. Experiment results in Table 14 demonstrate that Gurobi tuned with
22

---

Table 11: Comparison of prediction loss using different modification ratios on the testing datasets. The notation 'ineeasbbee' implies that majority of the generated instances are infeasible and thus cannot be used as the training data for PS. We mark the best values bold.
FA
IP
PS
19.45
341.33
PS+G2MILP 1) = 0.01
Infeasible
348.90
PS+MIL.P-StDDio y
18.52
341.33
PS+G2MILP 0.05
Infeasible 18.25
363.76
PS+MILP-SStDDio 0.05
341.33
PS+G2MILP 7 0.10
Infeasible 19.39
348.91
PS+MILP-StuDio r 0.10
341.33
Table 12:
Comparison of solving performance in PS with different modification ratios of MILP- StuDio and G2MILP, under 1, 000-second time limit. In the IP benchmark, all the approaches reach the time limit of I, ,,000s, thus do not consider the Time metrie. The notation 'Infeasible' implies that a majority of the generated instances are infeasible and thus cannot be used as the training data for PS. '4' indicates that lower is better. We mark the best values bold.
FA (BKS 17865.38)
IP (BKS
Obj
gapas 4 Time
Obj f
gaPaha
PS
17865.38
0.00
7.19
11.40
0.24
PS+G2MILP 7 = 0.01
Infeasible
11.57
0.41
PS+MIL.-SStuDio y)
17865.38
0.00
7.08
11.22
0.06
PS+G2MILP y 0.05
Infeasible 0.00
11.55
0.39
PS+MILP-StuDio v 0.05
17865.38
7.07
11.29
0.13
PS+G2MILP y 0.10
Infeasible
11.62
0.46
PS+MILP-SStDDio y 0.10
17865.38
0.00
7.11
11.53
0.37
Table 13: Selected hyperparameters of Gurobi.
Hyperparameter
Type
Min
Max
Description
Heuristics
double 0
Time spent in feasibility heuristics.
MIPFocus
integer 0
Set the focus of the MIP solver.
VarBranch
integer -1
Branch variable selection strategy.
BranchDir
integer -1
Preferred branch direction.
Presolve
integer -1
Controls the presolve level.
PrePasses
integer -1
20
Presolve pass limit.
Cuts
integer -1
Global cut generation control.
Method
integer -1
5
Algorithm used to solve continuous models.
additional instances generated by the MILP-StuDio framework (tuned-MILP-StuDiig consistently outperforms the other baseline methods.
E.4 More Results Non-Structured MILPs
While MILP-StuDia is primarily designed to handle MILP instances with block structures in their CCMs, it is also important to evaluate its performance wider classes of MILP problems, including those that may not exhibit such structured characteristics. Evaluating MILP-StuDio's s capabilities in this broader context will highlight its potential for broader applications.
To extend our method general MILP instances, the framework remains unchanged and we just need to adjust the block decomposition and partition Algorithms and 2. Specifically, the constraint
23

---

Table 14: Comparison of solving performance in Gurobi hyperparameter tuning. We mark the best performance in bold.
FA
gaPab + Time 4
Gurobi
0.00
6.06
Gurobi-tuned
0.00
6.04
luned-Bowly
0.00
5,96
tuned-G22 Luned-G2MILP
Infeasible
tuned-MILP --adMMIL--Suuio
0.00
5.83
and variable classification Algorithm 1 is tailored to general MILPs. The graph community reflects the connection of the constraints and variables, which can serve as a generalization blocks. Block partition and community discovery both graph node clustering. Thus, cluster the constraints and variables according to the community and classification results to form generalized 'blocks'.
To this end, we provide more results on the SC (set covering) and MIS (maximum independent set) datasets (two popular benchmarks with non-structural instances from (8) and further investigate improvement of the MI solvers. We use 100 original instances, following the generation algorithm described in and [3],, and generate 1,000 new instances using G2MILP and MILP- PStuDio. The results demonstrate the outstanding performance of MILP-StuDia
general MILP instances without block structures. (1) Tables 13 and I7 show that MILP-StuDio can even outperform existing generation methods in terms of the similarity score and feasibility ratio. (2) Tables 15 and 17 show that MiLDoStuDio better preserves instances' computational hardness with closer sol solving time to the original instances. (3) Tables 16 and show that MILP-StuDDi leads to the greatest improvement for the PS solver.
Table 15: The similarity score, computational hardness, and feasibility ratio between the original and generated instances on the non non-structural large-scale Setcover benchmark (larger than that in Appendix E.4). We set the solving time limit 300s and 17 0.05. We mark the best performance in bold.
Original
Bowly
G2MILP
MtLP-StuDio
Similarity
1,00
0.231
0.763
0.766
Solving Time
300,0
3.72
300,0
300,0
Fcasibility Ratio
100%
100%
100%
100%
Table 16: The performance of the PS solver trained by instances generated by different methods on the non-structural Setcover benchmark. We the solving time limit 300s and r) 0.05. We mark the best performance in bold.
Gurobi
PS
Bowly
G2MILP
MII.P-ttuDio
Time
300.0
300.0
300.0
300.0
300.0
Obj
123.80
123.95
124.00
123.80
123.80
gaPa..
0.21
0.22
0.22
0.21
0.21
24

---

Table 17: The similarity score, computational hardness, and feasibility ratio between the original and generated instances on the non non- structural MIS benchmark. We set the solving time limit 300s and ? = 0.05. We mark the best performance in bold.
Original
Bowly
G2MILP
MIL.P-StuDio
Similarity
1.00
0.182
0.921
0,919
Solving Time
300.0
1.38
300,0
300.0
Feasihiliiy Ratio
100%
100%
100%
100%
Table 18: The performance of the PS solver trained by instances generated by different methods on the non-structural MIS benchmark. We set the solving time limit 300s and r = 0.05. We mark the best performance in bold.
Gurobi
PS
Bowly
G2MILP MILP-StuDio
Time
119.74
36.85
42.92
21.39
11.33
Obj
683.75
683.75
683.75
683.75
683.75
0.00
0.00
0.00
0,00
0.00
F,5 More Results Real-world Industrial Dataset
To further demonstrate the effectiveness in real-world applications, we also conduct experiments on a real-world scheduling dataset from an anonymous enterprise, which one of the largest global commercial technology enterprises. The instances do not present clear block structures. The results in Table 19 show that the extended framework generalizes well on the general MILP datasets and has promising potential for real-world applications. The dataset contains 36 training and 12 testing instances. The few training instances reflect the data inavailability problem in real-world applications. We use different data generation methods to enhance the performance of the MLPS solver and list the solving time, objective value, and node number in Table 19 as follows. MILP-StuDD outperforms other baselines in this dataset, highlighting its strong performance and applicability.
Table 19: The results in the real-world dataset.
Time (1000s time limit)
Ohj
Node Number
PS+G2MILP
PS+MILP.SUDD
PS+MILP StaDio
PS+GIMILP
PS+MILP-SON Stuuioo
instnneel
1509652.00 00
1509652.00
2096522.0
144.21
146.67
131.80
38767.00
37647.00
30513.00
instmee2
205197.00
205197,00
205197.00
5.83
9,51
10.11
723.00
1047.00
instnne:1
7483.00
7483,00
7463.00
29,50
32.68
38.49
555.00
751. 00
901.00
instane24
447781.00
384454.99
318675.99
1000.30
1000.00
10545.00
6201.00
S186.00
instnnee5
1465601 00
1465601 100
1465601 00
186.85
81 67
63.55
24317.00
11481.00 10
9732.0
anstacee6
1299554.00
1293554.00
1293354.00
38.65
25.41
$2.45
3471.00
2357.00
Instance?
1290554.00
1293554.00
1293554,00
28.96
24.82
31.76
3471.00
2357.00
3002.00
instanee
612151.00
612151,000
612151.00
0:18
0.35
13.00
55.00
13.00)
instacce9
1578141.00
1578141.00
1575141.00
28.53
26.74
23.61
3083.00
3207.00
3150.00
instancel0
1149250.00
1149250.00
1149250.00
154.00
instaneel1 LI
1000555.00 00
1030555.00
1030555.00
0.27
0.35
0.34
1.00
1.00
1.00
instancel2
1216465.00
1216445.00
1216445.00
23.10
Average
984113.66
978836650
973354992
125.35
115.02
112.86
7694.25
5528.42
5462.42
G Visualizations of CCMs
To provide further insights into the characteristics of the instances generated by MILP-StuDio, we visualize the Constraint Coefficient Matrices (CCMs) of both the original and generated instances in Figure 10 The CCM visualization is powerful tool to understand the structural propertics of MILP instances, as it captures the patterns and relationships between the constraints and variables. By comparing the CCMs of the original and generated instances, we can understand how well MILP-StuDio is able to preserve the key structural characteristics of the input problems.
As shown in Figure 7 TO MILP-StuDio is able to successfully maintain the block structures observed in the original instances across the various benchmark problems. This indicates that the generated instances share similar underlying problem structures with the original data, which is a desirable property. This ability to preserve the structural properties of MILP instances crucial for the effective training and evaluation of machine barning-based MILP solvers. In contrast, Bowly struggles to
25

---

capture the intricate CCM structures, while G2MILP introduces additional noise that disrupts the block structures in the generated CCMs.
H Implementation Details
H.1 Implementation of Predict-and--Sarch
For model structure, the PS models used in this paper align with those outlined the original papers [T]. We use the code in method to implement PS. For the PS predictor, we leverage a graph neural network comprising four half-convolution layers. We conducted all the experiments GTX 3090 GPUs and Intel(R) (con(R) E5-2667 V4CPUs 3.20GHz.
com/sr wwwpiddnnnnneeeeeeeeeeeeeeeeeeee ant--and-Serchh MILP
single machine with NVidia GeForce
In the training process of MILP-StuDio, we set the initial learning rate to be 0.001 and the training epoch be 1000 with early stopping. addition, the partial solution size parameter (No, ky) and neighborhood parameter A are two important parameters in PS. The partial solution size parameter (ka, k1, A) represents the numbers of variables fixed with values and in a partial solution. The neighborhood parameter A defines the radius of the searching neighborhood. We list these two parameters used in our experiments in Table 20
Table 20: The partial solution size parameter (ka, k1, A) and neighborhood parameter A.
Benchmark
CA
FA
IP
WA
(ko, ki, A)
(300,0,10)
(20,0,10)
(50,5,10)
(0,600,5)
26

---

CA: original.
CA: Bowly
CA: MILP-StuDio. Figure 7: The visualization of the CCMs of original and generated instances from CA.
CA G2MILP.
FA: original.
FA: Bowly
FA: G2MILP.
FA: MILP-StuDio.
Figure 8: The visualization of the CCMs of original and generated instances from FA.
27

---

IP: original.
IP: Bowly.
G2MILP. Figure 9: The visualization of the CCMs of original and generated instances from IP.
IP: MILP-StuDio.
WA: original.
WA: Bowly (failed due time out).
WA: G2MILP.
WA: MILP-StuDio.
Figure 10: The visualization of the CCMs of original and generated instances from WA.
28

---

H.2 Implementation of Classification Algorithm for Constraints and Variables
In Section 4.1 we classified the constraints into M-Cons, B-Cons, and DB-Come and the variables into BI- Vars and Bd- Vars. As shown in Equation (4), we show the constraint and variable classification results for the bordered block-diagonal and doubly bordered block-diagonal structures.
Di
D
F
D2
D2
F2
B-Cons
B B-Cons
D
D
FR
(4)
B1
B2
B
M-Cons
B1
B ...
B
C
M-Cons
BI-Vars
BI-Vars
Bd-Vars
Identifying these different types of constraints and variables in CCM can aid the (1) variable partition process during block decomposition and (2) block manipulation process during generation. Considering the CCM, we denote the following attributes for each row (constraint) and column (variable). For row in CCM A Rmxa Tmax the maximum z-coordinate of nonzero entries, Jmin is the minimum a-coordinate of nonzero entries, and h is the number of nonzero entries. Similarly, given column in CCM, we denote the maximum y-coordinate of the nonzero entries by Umaax the minimum y-coordinate of the nonzero entries by Ymin and the number of nonzero entries by hy. we first give the following observations.
The nonzero entries in an M-Con often have a wide range of x-indices, i.e., large Jiax Tmin and high standard deviation of
The nonzero entries in a B-Con often have a narrow range of z-indices, i.c., small Zmax and small standard deviation of x.
For a Bd-Var, the nonzero entries in the corresponding column of CCM have wide range of y-indices and high density (the proportion of nonzero entries in the column), i.e., large Ymax V/min and ht/ /mm
DB-Cons are defined as constraints containing Bd- Vars.
Using these observations, we define vector features for each row and column in the CCM. The row features include the standard deviation trow_feat [o]] ). the proportion of nonzeros (density, row_feat [1]), and ranges of the r-coordinates (row_feat [2] ). For a column in CCM, we consider the range (col_ ccal_feat [o]) and density (col feat [1]) of the nonzero entries. The pseudo-code of the classification algorithm is presented in Algorithm 1. For the hyperparameter used in this paper, we set Φ1 = 0.75, Φ22 = 0.75, Φ3 = 0.5, Φ1 = 0.2, and Φ = 0.5, and set DB =True only in WA.
H.3 Implementation of Partition Algorithm for Block Units
In Section 4.2. we use GCG to reorder the rows and columns CCMs and obtain an initial variable partition result from GCG. However, GCG sometimes cannot partition the variables well, such as the situation in CA where GCG fails to identify the blocks since the blocks CA contain different numbers of variables. Thus, need to refine the partition obtain better ones. Specifically, that many blocks in CCMs contain regular lines (mainly horizontal and diagonal lines). Thus, we define line detection for block identification. Splitting these lines by columns we can get the block units from the CCMs. To get block units by lines from the reordered CCM image, we design the following partition algorithm in Algorithm 2 The algorithm iterates over the points the image and finds the endpoint in the columns of the lines mentioned above. With all the endpoints in columns, we can split one image into block units in columns. To keep the algorithm concise, we introduce two criteria, each representing different detection method.
find
Criterion 1: horizontal line detection. This criterion help to locate the endpoint of
horizontal lines in the image precisely.
Criterion 2: diagonal line detection. This criterion can also help to locate the endpoint of diagonal lines in the image precisely.
We set for CA and Ç 3 for other benchmarks.
29

---

Algorithm 1: Classification algorithm for constraints and variables in CCMs
Input: The CCM A Ru to be analyzed, hyperparameter Φ1, d2, da. 64, and Φs, the binary controller DB to determine whether identify DB-Vars
Output: The classification results for each row and column: B-Conslist, M-Conslist,
DB-Conslist, BI-Varse Varslist, and Bd- Varslist
Initialize: set B-Conslist, M-Conslist, DB-Conslist, BI- B1-Varslist, and Bd- ad-Varslist be empty
2 Compute the column features and row features of A and normalize them
DB =True then for j in (1.....n) do if the features of the j-th variable col sol_fea[[o]>> 01 and col_feat [1]> 02 then Append j to Bd- Bd-Varslist end else
Append j to BI- BI-Varslist
10
end
11
end
12 end
Append the indices of constraints that contain variables in BI-Varslist into DB-Conslist
14
for i in (1....,,)) m do
the i-th constraint is not in DB-Cons and the features of the i-th constraint row_feat [0] > 63, row_feat [1] >> Φ1 and row low_feate [2] > Ø5 then
16
Append M-Conslist end
17
18
else end
19
Append i to B-Conslist
20
end
22
return B-Conslist, M-Conslist, DB-Conslist, B1- Bl-Varslist and Bd- Varslist
Algorithm 2:
Partition algorithm for variables in CCMs
Input: The image representation Á [Rmx* of reordered CCM to be analyzed Output:
The partition results for the columns
Initialize: set Partitionlist to be empty, cut-off point and q, detection horizon Ç.
2 Criterion Al: 1][
Ali j
2] = Ali <|ß
<]
255 and
Ali |][] + =
3 Criterion 2: Ali 1][s] -Ài 2|D1 ... Ali <|b = 255 and Á + 1 = 0.
for j in {1,-.. .n] do
for i in (1, {1. do
if A A(d 255 then if Criterion
Criterion is satisfied then
q = j
A Append [p : to Partitionlist
p ạ break
11
12
end
end
14
end
15 end
16 return Partitionlist
30

---

H.4
Details on Block Manipulation
Block manipulation We leverage the classification results for constraints and variables aid the block manipulation process, in which the results can help us process more complex structures of CCMs beyond the three basic ones. For example, we can process the following structures in Equation which is the combination of DB- DB-Cons, M-Cons, and B-Cons.
Di
F F2
D2
D
Fk
B1
BN
B₁
C
(5)
Di
D2
DR
Different types of constraints and variables have different manipulation methods. For example, when we apply the reduction and expansion operators, the manipulation of BI-Vars can change the variable numbers, and the manipulation of B-Cons and DB-Cons can change the constraint numbers.
For the mix-up mi and expansion operators. the number of the introduced M-Cons my may mismatch that in the original instance m2. We define successful matching if mı 2 m2 If my m2, the operators can performed well. Otherwise, we drop the last my m2 M-Cons in the Block unit, such that the M-Cons can be perfectly matched.
Coefficient refinement In addition to the block structures, we have observed the presence of specific patterns in the coefficient values of weal-wrldd MILP instances. These patterns contribute to the overall problem structure and are worth considering during the instance generation process. For instance, as shown in Equation (6). we write two CCMs from different instances. certain MILP instances (like FA), the nonzero coefficients within the B-Cons (rows of D) remain consistent across block units within a given instance (marked in the same color, blue or red, in the same instance), but may differ across different instances (marked in different colors). However, when applying mix-up or expansion operators to generate new instances, the introduced constraint coefficients from other instances can potentially disrupt this inherent coherence.
To address this issue, have incorporated a constraint refinement component that focuses on preserving the distribution of coefficient values in such scenarios. Specifically, we define a "non- trivial constraint"
constraint that contains values other than -1, and For each MILP instance, we identify the non-trivial constraints in the block units. For the k-th non-trivial constraint a in
(i) the block unit, we then compute the mean p and variance (( across the constraint coefficients and block units in this instance. During the instance generation process, whenever the refinement
component is triggered (e.g., after mix-up expansion operations), it samples the new constraint
coefficients for the introduced blocks from Gaussian distribution M( %xx)), the generated instances maintain similar distribution of non-trivial coefficients observed in the original instances. The pseudo code of coefficient refinement is in Algorithm and we activate this component in FA and IP.
(8)) This ensures that
D
D
D
D
(6)
D
D
B
B Instance
B
B
B
Bu
Instance
31

---

Algorithm 3: Coefficient refinement algorithm
Input: An instance dataset {_i # Compute the mean and variance 2 for i in {1,... .N do
Determine K, the number of non-trivial constraints for each block unit. We denote the k-th non-trivial constraint in the block unit by a₂
for k in (1.... } do
Compute the mean Me (4) and variance 0jk across coefficients in and block units in Iz end
end
8
When performing mix-up or expansion, given an instance I, and block unit Bu
for k in (1,... K) do
( to replace those in Bu Sample the non-trivial coefficients from N( %%
10
end
12
Performing mix-up or expansion
Table 21:
The variable, constraint, and edge features used for MILP-StuDD and G2MILP.
Index
Variable Feature Name
Description
0
Objective
The objective coefficient of the variable The variable type, including binary, integer, implicit- integer, and continuous
1-4
Variable type
5
Specified lower bound Specified upper bound
Binary, whether the variable has lower bound Binary, whether the variable has upper bound Binary, whether the variable reaches its lower bound Binary, whether the variable reaches its upper bound
6
7
Lower bound
8
Upper bound
Index
Constraint Feature Name
Description
0
Bias
Normalized right-hand-side term of the constraint
Index
Edge Feature Name
Description
0
Coefficient
Constraint coefficient the edge
I More Details on the Data and Experiments
L.1 Details on Bipartite Graph Representations
The bipartite instance graph representation utilized by MILP-StuDio closely aligns with the approach presented in the G2MILP paper [19]. This representation can be extracted using the observation function provided by the Ecole framework [60]. We list the graph features in Table 21
1.2 Details the Benchmarks
The CA and FA benchmark instances are generated following the process described in g. Specifically, the CA instances were generated using the algorithm from [16). and the FA instances were generated using the algorithm presented in [17]. The IP and WA instances are obtained from the NeurIPS ML4CO 2021 competition [32]. The statistical and structural information for all the instances is provided in Table
32

---

Table 22: Statistical information of the benchmarks we used in this paper.
CA
FA
IP
WA
Constraint Number
193
10201
195
64306
Variable Number
500
10100
1083
61000
Block Number
94
100
105
60
Constraint Type (-Cons)
M.
M. B
M. B
M. D and DB
Variable Type (-Vars)
B1
B1
and Bd
1.3 Details on Graph Distributional Similarity
To evaluate the distributional similarity between the training and generated MILP instances, we compute 11 graph statistics [19] as detailed in Table 23 First, we calculate these statistics for both the original training instances
the generated instances. Then, we compute the Jensen- Shannon divergence (ISD) Dis.i. for each of the 11 statistics, where i = ,,..,.1111 11. The JSD ranges from to log 2, so we standardized the values as follows: Djs,
log (log 2 - Dis.:) Finally, we obtain an overall similarity score by taking the mean of the standardized JSD values, score 7 E Dist, The resulting score falls within the range of [0, 1], where higher value indicates stronger distributional similarity between the training and generated instances.
Table 23: Statistics for computing structural distributional similarity
Feature
Description
coef dens cons cons_degree mean cons cons_degree_ste std var var_degree_ment var_ var_derree_ste std Ihs mean Ihs std_ rhs_mean rhs_std clustering coef
Proportion of non-zero entries in CCM A.
Average degree of the constraint vertices.
Standard deviation of the constraint vertex degrees. Average degree of variable vertices.
Standard deviation of the variable vertex degrees.
Mean of non-zero entries in CCM A.
Standard deviation of non-zero entries in CCM A.
Mean of the right-hand-side term b.
Standard deviation of the right-hand-side term b.
Clustering coefficient of the graph.
modularity
Modularity of the graph.
33

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We do so in the abstract and introduction of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to Section 7
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
34

---

Justification:
This paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
35

---

Answer:
[No]
Justification:
We will release the code the paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
cesssnnnoiccyy icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//guuii wwwtii/gguie///eeeeeeoocc CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer to Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please see Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
36

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:///////iss.eeeeeeeee https///ccpcppctceccccccioeeeee
Answer: [Yes]
Justification: Our research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please refer Appendix
B
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
37

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Please refer to Appendix and I.2
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whw.ree.wthhhe....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
38

---

Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details on the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "PyeYq7OaOO", "reviewer": "Reviewer_jQXE", "summary": "The paper presents a novel framework for generating high-quality MILP instances. The proposed method, MILP-StuDio, leverages the block structures in constraint coefficient matrices (CCMs) of MILP instances to preserve computational hardness while allowing scalable and efficient generation. The framework consists of three main steps: block decomposition, structure library construction, and block manipulation through reduction, mix-up, and expansion. Experimental results demonstrate MILP-StuDio's ability to generate instances that improve the performance of learning-based solvers and maintain high similarity to original instances in terms of graph structural distribution and solving properties.", "questions": "1. Can you provide formal mathematical proofs to support the claim that the MILP-StuDio framework preserves the feasibility and computational hardness of generated instances? How do you theoretically ensure that the generated instances are representative of the original distribution?\n2. How does MILP-StuDio handle MILP instances that do not exhibit clear block structures? Can you provide empirical evidence or case studies demonstrating the framework's applicability to a diverse range of MILP problems beyond those with explicit block structures?\n3. How do you ensure that the instances generated by MILP-StuDio do not introduce biases that are absent in naturally occurring MILP problems? Can you provide an analysis comparing the distribution and complexity of generated instances with real-world instances?", "limitations": "N/A", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The method takes a further look into the block structures to generate MILP instances that share more similarity with the original structures. The empirical results seem better than the previous method G2MILP.", "weaknesses": "The proposed MILP-StuDio framework is tailored to highly artificial or synthetic problems with explicit block structures. The paper does not provide a convincing argument or empirical evidence showing that the framework can be generalized in real-world applications. Actually, in most of the real-world applications, most MILP instances do not have such clear block structures at all. MILP instances can have varying and overlapping structures that are not neatly decomposable. The paper is cherry-picking on specific synthetic/artificial datasets (all the four datasets) that have very structured blocks. It’s of no use to generate well-structured data that could be easily manually generated. The paper does not address how the method handles variability in block structures, leading to concerns about its robustness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments. We **show the applicability of MILP-StuDio Global Response**. Our rebuttal includes **Tables A1-6 in the attached PDF**. We sincerely hope that we could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.\n\n# W & Q2\n\n>Most MILPs in the real world do not have block structures\n\n**MILPs with block structures have drawn much attention in industrial and academic fields**. They are commonly seen in practice and have been a critical topic in OR (**Global Response 1**). They are challenging for existing generation methods, and MILP-StuDio is **the first method** designed to address them effectively.\n\n>Generalize to general MILPs without clear block structures \n\n**Our method can generalize to MILPs without clear block structures**. In **Appendix E.4**, we conduct experiments on Setcover, a popular benchmark without block structures. We provide further results.\n\n1. For general MILPs, **we can still use the framework and adjust the block partition Algorithms 2**. Specifically, the cons&var classification Algorithm 1 is tailored to general MILPs. The graph community reflects the connection of the constraints and variables, which can serve as a generalization of blocks. Block partition and community discovery are both graph node clustering. Thus, we cluster the constraints and variables according to the community and classification results to form generalized 'blocks'.\n2. **We also conduct experiments on MIS without block structures**. We also compare the improvement of downstream ML solvers. The results in **Tables A1-4** show that the extended framework generalizes well on general MILPs and performs best **in instance properties and downstream tasks**. \n\nThus, MILP-StuDio can be generalized in real-world applications.\n\n# Q1& Q3.2\n\n>Theoretical results for (1) preservation of the feasibility and computational hardness; (2) representativeness of the original distribution\n\n**The theoretical guarantee for these topics remains an open problem**. In operations research, researchers study the theoretical results when specific problem formulations are given. For general MILPs, we do not know the problem structure, and thus theoretical results become extremely hard due to MILPs' complex combinatorial nature. \n\n1. We try to propose a **feasible condition** for the mix operator. We analyze the BBD structure with the same notations in Sec 4.1. We place the proof in the comment.\n\n   >**Proposition.** Suppose that the original instance P1 is feasible with the form $\\min_x\\sum_ic_i^Tx_i\\, s.t.D_ix_i\\le b_i,\\sum_iB_ix_i\\le b$. We substitute $(c_1,D_1,b_1,B_1)$ with $(c'_1,D'_1,b'_1,B'_1)$ to obtain new ones P2. Suppose further that the matrix $B_1$ and $B'_1$, $D_1$ and $D'_1$ have the same sizes. We define the problem P3 by $\\min_x1\\,s.t.D'_1x_1\\le b'_1,D_1x_1\\le b_1,B'_1x_1=B_1x_1.$ **Then the generated instance P2 is feasible if P1 and P3 share a feasible solution of $x_1$**.\n\n   We are sorry that the analysis of computational hardness is much more intractable without knowing the formulations. We are also sorry that we might not understand the definition of representativeness of a distribution in math. We would appreciate it if you could kindly provide more insights into it. \n\n\n>Compare the distribution & complexity between the generated and real instances\n\n2. Though difficult in theory, we would like to provide empirical results to show the strong performance of MILP-StuDio in the following aspects.\n\n   - **Feasibility and hardness (Complexity)**. Experiments show that MILP-StuDio has the strong ability to preserve feasibility and computational hardness, both in MILPs with and without block structures (**Tables 2 and 3 in the paper; Tables A1 and A3**).  \n\n   - **Representativeness (Distribution)**.  We provide graph statistics of the generated and original instances to **compare the distribution and complexity** between them (**Tables A5-6**).\n\n   The results in **Tables A5-6** show that MILP-StuDio can generate instances with similar graph statistics distribution and complexity to the original ones. The high similarity indicates the representativeness of the distribution.\n\n# Q3.1\n\n>Techniques to avoid introducing biases\n\n1. **Existing work can introduce severe random noise to the structures of CCMs**. In Figures 3 and 7-10, the CCMs of instances generated by existing methods are quite different in matrix structure compared to the original ones.\n\n2. **We propose a series of techniques to mitigate both structural and coefficient biases**. Different from existing works, MILP-StuDio has the following key features.\n\n   - **We consider the global block structures**. We perform **Algorithms 1 (cons&var classification) and 2 (block partition)** to ensure the high-level block structures (e.g., BD, BBD).\n\n   - **We avoid structural biases introduced by random sampling and inaccurate networks.** Rather than sampling noisy latent variables and using biased ML models for constraint/variable generation, MILP-StuDio leverages collected blocks from the library. The blocks in the library obey the real distribution in the dataset, leading to fewer artificial biases. **Figures 3 and 7-10** show that the generated instances are highly similar to the original ones in terms of CCM structures.\n\n   - **Techniques to avoid coefficient biases**. We find that the distribution of coefficients in the introduced block units may not match that in the original instances (Please see **Appendix G.4**). This may lead to degradation in computational hardness. Thus, we propose the coefficient refinement algorithm **Algorithm 3** to modify the coefficient in block units.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "5b2CUSQX7x", "reviewer": "Reviewer_jbdZ", "summary": "This work presents a method for generating MILP instances by leveraging block structure decomposition. The primary aim is to address the challenges of generating high-quality MILP instances that preserve computational properties and structures of the original problems, thereby supporting the study and development of both traditional and learning-based MILP algorithms.", "questions": "Question:\n- How does the choice of subgraphs during block decomposition and manipulation affect the overall quality and difficulty of the generated MILP instances?\n- Could the proposed approach be potentially extended for more general MIP problems that without block structure?", "limitations": "Not applicable.", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Strength:\n- The paper is easy to follow\n- It is interesting to study instance generation as real-world MIP data is generally limited for the study of learning-based MIP algorithms.\n- Although the idea of studying block structure is not new, the focus on block structure decomposition for MILP instance generation makes sense.\n- The paper provides numerical experiments on multiple datasets and results looks promising.", "weaknesses": "Weakness:\n- The paper lacks a detailed discussion on the criteria for selecting subgraphs during block decomposition and manipulation, which could impact the quality of the generated inst\n- The proposed method only works on problems with block structures, which limits its broader applicability\n- The number of instances on the test bed is very small.\n- Code is not provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments. We provide **more evidence to show the applicability of MILP-StuDio Global Response**. Our rebuttal includes **Tables A1-6 and B1-5 in the attached PDF**. We sincerely hope that we could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.\n\n# W1 & Q1\n\n> How the criteria for selecting subgraphs impact on the quality and difficulty of the generated instances\n\nThanks for your valuable suggestion. We conduct extensive experiments to investigate the **impact of different policies for selecting subgraphs** during the MILP instance generation process using MILP-StuDio (mix).\n\nThe policy we used in our paper is the **random policy**. Given an original instance, we randomly sample a block unit $\\mathcal{BU}_{ins}$ (and thus the corresponding subgraph, called instance subgraph) in the instance and randomly sample a block unit $\\mathcal{BU}$ (subgraph) from the structure library. We then substitute the instance subgraph with the subgraph sampled from the library.\n\nWe explore several subgraph selection policies:\n\n1. **Random Policy (Rand 1-3)**: To test the robustness of our random policy, we run three different random seeds.\n2. **Similarity-based Policy (Sim)**: Sim randomly samples an instance subgraph and five block units (subgraphs) from the structure library. Sim then compares the graph similarity score between the instance subgraph and the five subgraphs and then selects the subgraph with the highest similarity to perform the mix-up operation.\n3. **Reinforcement Learning Policy (RL)**: RL randomly samples an instance subgraph $\\mathcal{BU}\\_{ins}$ and five block units from the structure library. Each pair of the instance subgraph and subgraph $(\\mathcal{BU}\\_{ins},\\mathcal{BU})$ forms a state, and the five sampled subgraphs are the actions. The reward is designed as the negative absolute value of the difference in computational time between the original and generated instances, $-|t_1-t_2|$.\n\nWe compare the performance of these subgraph selection policies in terms of the similarity score, computational hardness, and feasibility ratio of the generated instances in **Table B1**. We also provide the improvement of the downstream learning-based solver PS and GNN branching policy, in **Tables B2 and B3**. Our key observations are:\n\n1. The performance of the Rand 1-3 policies are close to each other, indicating that our **random policy for subgraph sampling is robust to the random factors**.\n2. The performance of the Sim and RL policies is slightly better than Rand 1-3, but the difference is not distinct. This implies that **the simple random policy can achieve a satisfactory performance**.\n\nIn summary, MILP-StuDio is not overly sensitive to the subgraph sampling policy, and the simple random policy is robust enough to achieve a good performance.\n\n# W2 & Q2\n\n> The proposed method only works on problems with block structures\n\nThanks for your valuable suggestion. \n\n1. **MILPs with block structures are commonly seen in real-world applications**, and a large number of works in operations research have studied specific types of MILPs with block structures in the past few decades (**Global Response 1**). \n\n2. **We believe that our framework can generalize to general MILPs and adjust to broader applicability**. To demonstrate the effectiveness and generalizability of MILP-StuDio, we have also **adjusted our method and conducted experiments on the general non-structural MILP benchmarks in Appendix E.4**. Here we provide more results.\n\n   - To extend our method to general MILP instances, **the framework remains unchanged and we just need to adjust the block decomposition and partition algorithms 1 and 2**. Specifically, the cons&var classification Algorithm 1 is tailored to general MILPs. The graph community reflects the connection of the constraints and variables, which can serve as a generalization of blocks. Block partition and community discovery are both graph node clustering. Thus, we cluster the constraints and variables according to the community and classification results to form generalized 'blocks'.\n\n   - We provide more results on the **Setcover and MIS datasets (two popular benchmarks with non-structural instances)** and further investigate the improvement of the ML solvers. The results demonstrate the outstanding performance of MILP-StuDio on general MILP instances without block structures. (1) **Tables A1 and A3** show that MILP-StuDio can even outperform existing generation methods in terms of the **similarity score and feasibility ratio**. (2) **Tables A1 and A3** show that MILP-StuDio better preserves instances' **computational hardness** with closer solving time to the original instances. (3)  **Tables A2 and A4** show that MILP-StuDio leads to the **greatest improvement for the PS solver**.\n\n# W3\n\n> The number of instances on the test bed is very small.\n\nThanks for your suggestion. We use a set of 150 testing instances to evaluate the performance of PS and GNN branching policy. The results are reported in **Table B4** for PS and **Table B5** for GNN branching policy. The results on the larger dataset are consistent with those on the small dataset. **MILP-StuDio still leads to the greatest improvement in the performance of the learning-based solvers**.\n\n# W4\n\nWe will upload the relevant code to an anonymous link in the official comment.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "GaKoiu1Ld9", "reviewer": "Reviewer_Rqw8", "summary": "This paper presents a method for generating instances for mixed\ninteger programming that mimic the characteristics of existing\ninstances. The main insight is that the performance characteristics of\nMIP solvers relate to the structure of the coefficient matrix of the\ninstance, with a few examples of such structure given in the paper. So\nthe new method is designed to discover such structures and replicate\nthem/combine them in the instances it generates. In experimental\nresults, the generator seems to produce instances whose behavior is\ncloser to that of the rest of the family.", "questions": "No specific questions", "limitations": "Addressed sufficiently", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I liked the overall idea. The paper identifies a feature of instances\nthat existing generators ignore, proposes a not-too-complicated way to\nuse it, and the results match the expectations.\n\nOverall a solid paper.", "weaknesses": "I think the latter two of the evaluation criteria are\nunder-explored. Specifically:\n\n- Improving the performance of learning-based solvers: I would expect\n  a lot more detail on how these solvers were trained. In general,\n  this aspect of the work is not explained very well, I think, and is\n  presented as if it should self-evident (which it is not, to me).\n\n- Hard benchmark generation: here there is just a very briefly\n  explained generation of a pool of instances that progressively gets\n  harder. I do not understand exactly why this test was performed like\n  this, what the original instances, nor do I find this a convincing\n  argument that the generator can produce instances of increasing\n  difficulty.\n\nFinally, I don't like the title of the paper at all. It feels labored\nand gimmicky. It is not a reason to reject, though.\n\nvarious places: operational research -> operations research\n\n110: motivated -> motivating\n\n(3): what is bold O?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. Our rebuttal includes **Tables C1-2 in the attached PDF**. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n# W1\n\n>More details on the training of ML solvers\n\nWe use **predict-and-search** (PS) [1] and **learning-to-branch** (Branching) [2] ML solvers in this paper. We provide a **brief introduction to the solvers in Appendix D**. We also provide **part of the training and implementation information in Appendix G.1 for PS and Appendix E.1 for Branching**. Here we would like to provide more details to address your concerns. \n\n- **PS**. The implementation and training process align with those in [1]. PS aims to **predict an initial feasible solution for the binary variables**.\n\n  - **Data usage**. The original training and validation set consists of 100 and 20 instances, respectively. We generate 1,000 additional instances to enrich the training set. Then, we run Gurobi on each instance $I$ and collect 50 optimal or near-optimal solutions to approximate the solution distribution $p_i$ for each binary variable of $I$.\n\n  - **Training**. We use a GNN with four half-convolution layers for prediction. To train the GNN predictor $p_\\theta(x|I)$, PS adopts the assumption that the variables are independent of each other, $p_\\theta(x|I)=\\prod_ip_\\theta(x_i|I)$. To calculate the prediction target, PS uses the 50 collected solutions of $I$, from which a vector of solution distribution $(p_1,p_2,\\dots,p_n)$ is constructed. Here, $p_i=p(x_i=1|I)$ is the probability of variable $x_i$ being assigned the value 1 in $I$. The GNN predictor then outputs the predicted probability $p_\\theta(x_i=1|I)$ for each variable. The predictor is trained by minimizing the cross-entropy loss\n\n    $$L(\\theta) = -\\sum\\_{i,j}p_i\\log p_\\theta(x_i=1|I_j)+(1-p_i)\\log (1-p_\\theta(x_i=1|I_j))).$$\n\n  - **Hyperparameters**. We set the learning rate to be 0.001, the training epoch to be 10,000, and he batch size to be 8.\n\n- **Branching**. The implementation and training process align with [2]. The experiment settings and results on Branching are in **Appendix E**. Branching is critical in Branch-and-Bound algorithm and can be formulated as a Markov decision process. The branching policy decides to select a variable and partitions its feasible region at each step. **The quality of the selected variables significantly impact the algorithm's efficiency**. The strong branching policy (expert) can select high-quality variables but consumes a long decision time. GNN branching policy serves as a fast approximation.\n\n  - **Data usage**. The training and validation instances are identical to those in PS. Then we run the expert on each instance to collect 11,000 state and selected variable pair $(s,a)$, forming the training dataset $D$.\n  - **Training**. The GNN branching policy $\\pi_\\theta$ aims to imitate the decision behavior of the expert and is trained by minimizing\n        $$L(\\theta)=-\\sum_{(s,a)\\in D}\\log\\pi_\\theta(a|s).$$\n  - **Hyperparameters**. We set the initial learning rate to be 1e-4, the epoch to be 1,000 with early stopping, and the batch size to be 8.\n\n[1] A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming.\n\n[2] Exact Combinatorial Optimization with Graph Convolutional Neural Networks.\n\n# W2\n\n>Discussions on the hard instance generation\n\nWe would like to give a detailed explanation of the experiment. The test was done in [3], and we followed their settings. \n\n1. **Hard instance generation** task is **important** as it provides valuable resources to evaluate solvers and thus potentially motivates more efficient algorithms. \n2. **Experiment settings**. The objective of this experiment is to **test the ability to generate harder instances within a given number of iterations**. We use 30 original instances to construct the pool. In each iteration, for each instance $I$ in the pool, we employ mix/exp on it to generate two new ones, $I'$ and $I''$. We then select the instance among $I,I'$ and $I''$ with the longest solving time to replace $I$ in the pool. This setting is to **preserve the diversity of the pool**. We observe that there exist slight differences in the hardness of the original instances, and the generated instances derived from the harder original instances are also harder than those from easier ones. If we had simply generated 60 instances and selected the hardest 30, the proportion of instances generated from the hard original instances would have continuously increased, reducing the diversity of the pool.\n3. **More experiment results**. To provide more convincing evidence, we compare with G2MILP in Setcover dataset (G2MILP fails in FA) and find that MILP-StuDio can obtain a harder dataset in the given iterations (**Figure C2**). Additionally, we present the distribution of instance solving times in **Figure C1**, which demonstrates that the solving time becomes progressively longer across the entire distribution during the iterations.\n4. **Discussions**. The superior performance of MILP-StuDio can be attributed to the strong ability of the mix/exp operators to preserve the hardness. Moreover, exp can generate larger instances and thus are more likely to generate harder ones.\n\n[3] G2MILP: Learning to Generate Mixed-Integer Linear Programming Instances for MILP Solvers.\n\n>The title is labored and gimmicky\n\nThank you for your valuable suggestion. We will sincerely consider trying to improve the title.\n\n>operational research -> operations research; motivated -> motivating\n\nThank you very much for reading this article carefully and pointing out the typos. We will fix it in time.\n\n>bold O in (3)\n\nIn Eq (3), **O** refers to the matrix with all entries zero.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "FUb5UOjATH", "reviewer": "Reviewer_zDfV", "summary": "In this paper, the authors note the specific block structures in the constraint coefficient matrices (CCMs) of MILP instances that are closely related to problem formulations, and propose a novel MILP generation framework, called MILP-StuDio. MILP-StuDio identifies blocks in CCMs and decomposes instances into block units that serve as building blocks for MILP instances. New instances are constructed by removing, substituting and appending block units from the original instance. This allows MILP-StuDio to generate approximate instances with high feasibility and computational hardness as existing instances. The authors claim that using instances generated by MILP-StuDio, the learning-based solver is able to significantly reduce the solution time by more than 10%.", "questions": "Please reply to my comment listed in 'Weaknesses'.", "limitations": "Not applicable.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The logical coherence and structural integrity of the manuscript are particularly noteworthy. The organization of the paper with a clear and effective division of content that facilitates understanding and engagement with the material.\n\n2. The code repository and appendices provided by the author are notable for their rich content and contribution to the replicability of the research. The codebase is meticulously organized, enabling a systematic understanding and replication of the study's procedures. The supplementary materials effectively supplement the paper's main content.\n\n3. The paper presents a novel and insightful approach to generating high-quality MILP instances through the exploration of block structures in CCMs. The visualisation of CCMs is particularly compelling, and effectively highlights the central idea of the paper by giving the reader an understanding of how MILP-StuDio's property of preserving block structure works.\n\n4. The robustness of MILP-StuDio is commendable. Even in the absence of clear block structures, as seen in non-structured MILP problems like the set covering problem, the method is able to generate instances that are still usable for downstream tasks. This demonstrates the adaptability and general applicability of the proposed framework.\n\n5. The experimental design is meticulously crafted and effectively demonstrates the advantages of MILP-StuDio. The comparison with both Bowly and G2MILP reveals that MILP-StuDio achieves higher similarity scores while preserving computational hardness and feasibility. Furthermore, the impressive results in improving the performance of learning-based solvers.", "weaknesses": "The significantly lower similarity scores for the red and exp operators (Table 7), despite their successful performance in downstream tasks, raises concerns about the appropriateness of the similarity metric for evaluating MILP instance generation. The consistent decline in similarity scores with increasing modification ratios, while maintaining computational hardness and feasibility, further suggests potential limitations of the similarity metric. Could the authors kindly elaborate on their thoughts regarding the role of similarity in MILP instance generation and whether alternative metrics or considerations might be more suitable for this task?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n> 1. The lower similarity scores for red/exp and increasing modification ratios suggest limitations of the similarity metric.\n\nThanks for the valuable insight. The red/exp operators change the instance sizes. The similarity score reflects the statistical similarity between the generated and original instances, considering factors such as density, node degree, coefficients, modularity, etc.\n\nTo investigate the similarity score, we first compare the similarity between the original instances with different sizes, which are highly similar in computational hardness and mathematical structures. Using the same setting as in Table 7 in our paper, the results in **Table D1** on the FA dataset show that the similarity scores between instances with different sizes are low. Second, we compare the similarity between the generated instances using exp/red and the original instances with the same sizes (e.g., we compare the similarity between instances generated by red $\\eta=0.05$ and original instances with Size 0.95). As shown in **Table D2**, the generated instances achieve high similarity scores.\n\nThis suggests that the similarity score has a drawback: **it is sensitive to the graph statistics but fails to capture the information of block structures or problem formulations**, which are crucial determinants of the mathematical properties and computational hardness.\n\n**Table D1**: We compare the similarity between original instances with different sizes. \"Size x\" refers to instances with x times the size compared to the ones used in the main paper. We use the code provided in [1] to obtain original instances with corresponding sizes.\n\n||Size 0.95|Size 1.00|Size 1.05|\n|-|-|-|-|\n|**Size 0.95**|1.00|0.34|0.26|\n|**Size 1.00**|-|1.00|0.41|\n|**Size 1.05**|-|-|1.00|\n\n**Table D2**: We compare the similarity between instances generated by red/exp operators and original instances with the same instance sizes.\n\n||MILP-StuDio (red)|MILP-StuDio (exp)|\n|-|-|-|\n|$\\eta=0.05$|0.60|0.62|\n\n> 2. Explain the role of similarity in MILP generation and whether alternative metrics might be more suitable.\n\nIt is a good question! To evaluate the generation quality, we may need to incorporate multiple metrics that capture different aspects of the instance properties. Since MILP generation aims to address data inavailability in downstream tasks, we think the **most effective metric is the improvement in downstream tasks brought by the generated instances**. \n\n1. **The MILP generation field is still in its early stages, and the graph distributional similarity is a simple and intuitive metric to measure the similarity**. The similarity score serves as an important metric in [2], thus we still adopt it as a metric. This situation is analogous to the molecular generation field, where researchers also used metrics like KL divergence and Frechet ChemNet Distance to assess the graph distributional similarity in the early works [3,4].\n\n2. **We need to incorporate multiple metrics to measure the quality of the instances**. While the graph similarity score cannot reflect the mathematical properties and hardness, computational hardness alone fails to capture the structural information. In molecular generation, researchers compare various metrics, such as validity, uniqueness, and novelty [3,4]. Recently, metrics more related to chemical properties have been proposed, such as atom/molecule stability and drug-likeness [5,6]. **We believe more suitable metrics will be proposed** for MILP generation in the future. \n\n   We propose two metrics more related to the mathematical structures.  (1) **CCM similarity** captures the block structure features, in which we calculate the distance of two digital representations of CCMs. (2) **Constraint distribution** reflects the formulation information. For each instance, we construct a 17-dimensional feature whose components are the proportions of 17 types of constraints proposed in MIPLIB. We then calculate the cosine similarity of the features between two instances.\n\n3. **The improvement in downstream tasks may be the most effective metric** to test the applicability. Unlike molecular generation, where the goal is to discover novel molecules or drugs, MILP generation aims to **address data unavailability in the downstream tasks**. Therefore, the improvement in downstream task performance **is in line with the initial goal**, while the similarity and computational hardness are intermediate metrics. While existing work [2] mainly focuses on a single task, we try to provide as many tasks as possible to demonstrate the effectiveness comprehensively.\n\n   - Improving the performance of learning-based solvers, including two ML solvers PS (**Table 4 in the paper**) and GNN approach for branching (**Tables 5 and 6**).\n   - Hyperparameter tuning for traditional solvers (**Table 14**).\n   - Hard instances generation for benchmark construction (**Figure 5 in the paper**). \n\n   We show that MILP-StuDio successfully achieves the best performance across all the tested tasks.\n\n[1] Exact Combinatorial Optimization with Graph Convolutional Neural Networks.\n\n[2] A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability.\n\n[3] Molecule optimization by explainable evolution.\n\n[4] Data-Efficient Molecular Generation with Hierarchical Textual Inversion.\n\n[5] Target Specific De Novo Design of Drug Candidate Molecules with Graph Transformer-based Generative Adversarial Networks.\n\n[6] Geometry-Complete Diffusion for 3D Molecule Generation and Optimization.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers,

We sincerely thank all reviewers' insightful and constructive comments, which helped to significantly improve our work. We have responded to the comments given by each reviewer in detail. In this global response, we provide a review on the MILPs with block structures and generalization of our framework to general MILPs without clear block structures. We hope this could be helpful for you to better understand our work. 

**We explain that the 'Table/Figure x' is the table or figure from the paper, and 'Table/Figure A/B/C x' is in the attached PDF of the author rebuttal.**

# The Importance of MILPs with Block Structures

**The MILPs with block structures are important in industrial and academic fields**. We found that MILP instances with block structures are commonly encountered in practical scenarios and have been an important topic in operations research (OR) with much effort [1-7]. 

- **MILP with block structures is an important topic in OR**. Analyzing block structures is a critical tool for analyzing the mathematical properties of instances or accelerating the solving process (e.g., Dantzig-Wolfe decomposition [1]) in OR. The MIPLIB dataset also provides visualization results of the constraint coefficient matrices for each instance, highlighting the prevalence of block structures.

- **The MILP instances with block structures are common and have wide applications in daily production and life**. There are many examples where the instances present block structures, including the allocation and scheduling problems  [2], the multi-knapsack problem  [3], the security-constrained unit commitment problem in electric power systems  [4], multicommodity network flow [5], multicommodity transportation problem  [6], vehicle routing problem [7] and so on. In real-world optimization scenarios, there are different types of similar items---such as different workers or machines in planning and scheduling problems, a set of power generation units in the electric power systems, vehicles in the routing problems, and so on---with relevant variables naturally presents a block-structured form in the mathematical models. 

- **The datasets we used in this paper (IP and WA) are from real-world applications**. The NeruIPS 2021 Competition of Machine Learning for Combinatorial Optimization released three well-recognized challenging datasets from real-world applications (IP, WA, and the anonymous dataset). Two out of the three competition datasets (IP and WA) have block structures. Moreover, instances from the anonymous dataset are selected from MIPLIB with large parts having block structures. These further reflect the wide application of block structures in real-world applications. Thus, our method indeed works in a wide range of problems in practice. 

- **Researchers have investigated specific MILP problems with block structures**. MILP with block structures has a large scope in the optimization field and there has been a wide range of works on specific problems with block structures, and they have developed a suite of optimization problems tailored to these problems. For example, the tailored algorithm for the security-constrained unit commitment problem in electric power systems  [4], multicommodity transportation problem  [6], vehicle routing problem [7], and so on 

Thus, MILP with block structures has a large scope in production and optimization. It has drawn much attention in the industry and academic fields.  

# Generalize Our Framework to General MILPs

**We believe that our framework can generalize to general MILPs and adjust to broader applicability**. To demonstrate the effectiveness and generalizability of MILP-StuDio, we have also **adjusted our method and conducted experiments on the general non-structural MILP benchmarks in Appendix E.4**. Here we provide more results.

- To extend our method to general MILP instances, **the framework remains unchanged and we just need to adjust the block decomposition and partition Algorithms 1 and 2**. Specifically, the cons&var classification Algorithm 1 is tailored to general MILPs. The graph community reflects the connection of the constraints and variables, which can serve as a generalization of blocks. Block partition and community discovery are both graph node clustering. Thus, we cluster the constraints and variables according to the community and classification results to form generalized 'blocks'.

- We provide more results on the **Setcover and MIS datasets (two popular benchmarks with non-structural instances)** and further investigate the improvement of the ML solvers. The results demonstrate the outstanding performance of MILP-StuDio on general MILP instances without block structures. (1) **Tables A1 and A3** show that MILP-StuDio can even outperform existing generation methods in terms of the **similarity score and feasibility ratio**. (2) **Tables A1 and A3** show that MILP-StuDio better preserves instances' **computational hardness** with closer solving time to the original instances. (3)  **Tables A2 and A4** show that MILP-StuDio leads to the **greatest improvement for the PS solver**.

[1] Decomposition principle for linear programs.

[2] Optimal Allocation of Surgery Blocks to Operating Rooms Under Uncertainty.

[3] Multiple Knapsack Problems.

[4] Security-constrained unit commitment: A decomposition approach embodying Kron reduction.

[5] Multi-Commodity Network Flows.

[6] Multicommodity routing optimization for engineering networks.

[7] The Vehicle Routing Problem.

Meta-review: The work presents an instance generator for mixed-integer linear programs (MILP) with block structure. The reviews were mixed, with some reviewers appreciating the originality of the work, while others raised concerns about its applicability, technical details, and overall impact. The authors' rebuttals were focused on addressing these three key aspects, and they were active and responsive throughout the review process. However, it is unfortunate that only one reviewer (Rqw8) fully engaged in the discussions during and after the rebuttal period.

I have carefully evaluated the paper, the reviews, and the responses. Overall, I am confident that the authors provided comprehensive answers that addressed all the major concerns raised by the review team. Specifically, the authors included experiments on industrial instances, generalized their methodology to a broader class of MILPs, and clarified the technical concerns and general limitations. These changes are also straightforward to incorporate into the main text or to add to the appendix, assuming the authors do implement them.

In conclusion, I believe this is a novel and potentially impactful contribution. Beyond the strong numerical evidence supporting the enhancement of learning-based solvers, it is important to note that block structure is pervasive in mathematical programming and continues to be an area of active research (e.g., in stochastic programming and Benders approaches). The methodology could also be valuable in assessing novel decomposition techniques or in learning general properties associated with real-world instances of interest. The “image representation” is also intriguing and could inspire similar approaches for other structures. Therefore, I do recommend acceptance as I believe this paper is above the bar.
Decision: Accept (poster)