MILP-StuDio: MILP Instance Generation via Block Structure Decomposition

Authors: haoyang  liu
jie  wang
wanbo  zhang
zijie  geng
yufei  kuang
xijun  li
yongdong  zhang
bin  li
feng  wu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:35:29

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.

Main paper: 
 introduction: 
 Mixed-integer linear programming (MILP) is a fundamental mathematical optimization problem that finds extensive applications in the real world, such as scheduling [1] , planning [2] , and chip design [3, 4] . In industrial scenarios, the solving efficiency of MILPs is associated with substantial economic value. To speed up the solving process, a great number of high-quality MILP instances are required to develop or test the solvers. Here we give the following two examples. First, both traditional solvers [5, 6] and learning-based solvers [7] [8] [9] [10] rely heavily on a lot of MILP instances for hyperparameter tuning or model training. Second, evaluating the robustness of solvers needs a comprehensive MILP benchmark consisting of numerous instances. However, acquiring many instances is often difficult due to high acquisition costs or privacy concerns [11, 12] . As a result, the limited data availability poses great challenges and acts as a bottleneck for solver performance. 1a visualizes the CCMs of four instances from the FA problem, where the white points represent the nonzero entries in CCMs. As we can see, the CCMs exhibit similar block structures across instances, with the patterns in red boxes being the block units. Figure 1b illustrates the block decomposition process, advanced features, and applications of our proposed MILP-StuDio.This challenge motivates a wide range of MILP generation techniques. In the past, researchers relied on problem-specific techniques for generation [13] [14] [15] [16] [17] . 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 statistics-based and learning-based methods. Statistics-based approaches utilize a few instance statistics to sample in the MILP space [20] . More advanced learning-based approaches, exemplified by G2MILP [19] , leverage deep learning models to capture global instance features and iteratively modify constraints in the original instances. Though in the early stage, learning-based techniques offer convenience and strong adaptability for MILP generation, making them applicable in a 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 or infeasible 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.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 Ax ≤ b, where A is the constraint coefficient matrix (CCM), x is the decision variable and b is a vector. As shown in Figure 1a , 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 of 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 [21] [22] [23] [24] . Although a wide suite of CCM-based techniques have been developed to solve MILPs [25] [26] [27] , existing works on MILP generation rarely pay attention to 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 (MILP-StuDio), which takes into account the block structures throughout the generation process and addresses Challenge (1)-(3) simultaneously. Specifically, MILP-StuDio consists of three key steps. We begin by identifying the block structures in CCMs and decomposing the instances into block units, which serve as the building blocks in the MILP instances. We then construct a library of the block units, enabling efficient storage, retrieval, and utilization of the comprehensive block characteristics during the subsequent process. Leveraging this library, we 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 to generate instances with flexible sizes, effectively improving the diversity of instances.Experiments demonstrate that MILP-StuDio has the following advanced features. (1) Hardness preservation. MILP-StuDio can effectively preserve the computational hardness and feasibility in the (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-based solvers using instances generated by MILP-StuDio.2 Background 
milp and milp with block structure: 
 A MILP instance takes the form of:EQUATIONIn Formula (1), x denotes the decision variables, c ∈ R n denotes the coefficients in the objective function, A ∈ R m×n is the constraint coefficient matrix (CCM) and b ∈ R m denotes the terms on the right side of the constraints, respectively. The vectors l ∈ (R ∪ {-∞}) n and u ∈ (R ∪ {+∞}) n denote lower and upper bounds for the variables, respectively.In real-world applications, a significant portion of MILPs exhibit block structures-consisting of many block units-in their constraint coefficient matrices (CCMs) A. These problems, referred as MILPs with block structures, include many commonly-used and widely-studied datasets in recent papers on learning-based solvers [8] [9] [10] 28] , such as combinatorial auctions (CA), capacitated facility location (FA), item placement (IP), multiple knapsacks (MIK), and workload balancing (WA). In Figure 2 , we 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 a pixel value of 255 (white) to the entry (i, j) if the corresponding entry in the CCM A[i, j] is nonzero. Conversely, if A[i, j] 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-structured CCMs in the context of MILP solving has long been acknowledged by operational researchers, where instances with similar block structures share similar mathematical properties [29] [30] [31] . Furthermore, the block structures of CCMs are closely related to the problem formulations [30] . Thus, the block matrices have shown great potential in accelerating the solution process for a family of MILP problems [21] [22] [23] [24] . One notable technique developed to exploit this structure is Dantzig-Wolfe decomposition [25] for solving large-scale MILP instances.A MILP instance can be represented as a weighted bipartite graph G = (W ∪ V, E) [8] . The two sets of nodesW = {w 1 , • • • , w m } and V = {v 1 , • • • , v n }in the bipartite graph correspond to the MILP's constraints and variables, respectively. The edge set E = {e ij } comprises edges, each connecting a constraint node w i ∈ W with a variable node v j ∈ V. The presence of an edge e ij is determined by the coefficient matrix, with e ij = (e ij ) as its edge feature, and an edge e ij does not exist if A[i, j] = 0. Please refer to Appendix I.1 for more details on the graph features we use in this paper.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: Please refer to Section 7Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
motivated experiments: 
 Preserving the mathematical properties of the original instances is a fundamental concern in 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 is important to note that the term "problem structure" can be ambiguous and confusing. There are different understandings and definitions of the problem structure-such as the bipartite graph structure [19] 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.G2MILP is the first learning-based approach for MILP instance generation. While it has shown promising performance, we observe that G2MILP still encounters difficulties in generating highquality 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 instances from the workload appointment (WA) benchmark [32] using Gurobi [5] , a state-of-the-art traditional MILP solver. We set the masking ratio of G2MILP-which determines the proportion of constraints to be modified-to 0.01. The results are summarized in Table 1 . In this the Similarity metric refers to the graph structural distributional similarity score [19] (defined in Appendix I.3), Time represents the average solving time (with a time limit 1,000s), and Feasible ratio indicates the proportion of feasible instances out of the total instances. Results show that although the generated instances achieve a high similarity score, most of them are infeasible. Furthermore, the feasible instances exhibit a severe degradation in computational hardness.The aforementioned experiments provide evidence 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 to explore alternative definitions of problem structures that offer stronger correlations to the mathematical properties of the instances and can be effectively preserved during the generation process. One such promising structure is the block structures within CCMs.The concept of block structures within CCMs originates from traditional operational research and has proven to be effective for problem analysis [21] [22] [23] [24] . It is widely recognized that MILPs with similar block structures in CCMs often share similar formulations, resulting in similar mathematical properties [29] . We visualize and compare the CCMs of the original and generated instances in Figure 3 . In the middle figure, we observe that G2MILP breaks the block pattern in the left and introduces a noisy block in the bottom right. It becomes evident that the generation operation in 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. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
generation framework using block structure decomposition: 
 In this section, we introduce the proposed MILP-StuDio framework to generate high-quality instances. MILP-StuDio 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 Manipulation "-" using 1:2 "-" using 1:2 "-" using 1:2 "-" using 1:2 as it forms the core of our method. The subsequent sections, from Section 4.2 to Section 4.4, provide a detailed explanation of each step. The overview of MILP-StuDio is depicted in Figure 4 .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 blockdiagonal (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 are 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] .EQUATIONFormally, a MILP with a DBBD structure can be written asEQUATIONwhere the partition c= (c ⊤ 1 , • • • , c ⊤ k+1 ) ⊤ , x = (x ⊤ 1 , • • • , x ⊤ k+1 ) ⊤ and b = (b ⊤ 1 , • • • , b ⊤ k+1 ) ⊤ .To process more complex block structures beyond the three basic ones, we specify different types of constraints and variables in a CCM (and the corresponding MILP). First, we classify variables as block and bordered variables (Bl-Vars and Bd-Vars). The block variables DBBD are x block = (x ⊤ 1 , • • • , x ⊤ k ) ⊤ ,Reordering Rows and Columns in CCMs Given a MILP instance, the raw orders of rows and columns for a 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.We employ an enhanced variable partition algorithm based on the image representations of CCMs for block decomposition, using the constraint-variable classification results mentioned in Section 4.1. Specifically, we extract the sub-matrices of the block units BU in CCMs, i.e., which take the form of D i in BD, D i B i in BBD, andD i F i B i in DBBD.Finally, we partition and decompose the CCMs into sub-matrices of block units. The algorithm enables us to handle more complex structures beyond the basic three found by GCG, such as instances in WA with M-Cons, B-Cons and BD-Cons. In the case of WA, the sub-matrices are in the form of  D (1) i F i B i D (2) i   ,where D(1) i represents the diagonal block with DB-Cons, and D(2) i represents the diagonal block with B-Cons. Please refer to Section H.3 for the detailed implementation of the decomposition process.As we can see in Figure 1a , the block units across instances exhibit striking similarities in terms of the internal structures. 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 a sub-matrix contains constraints W = {w i1 , • • • , w i k } and variables Ṽ = {v i1 , • • • , v i l } in the instances, we then extract the sub-graph containing W, Ṽ and the edges connecting W and Ṽ 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.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 a block unit BU ins 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 BU ins from the original instances and another block unit BU from the structure library L. We then replace BU ins with BU to generate a new instance. The mix-up operator introduces structural variations through the incorporation of external block units.• Expansion. This operator involves randomly sampling a block unit BU from the structure library L and appending it to the original instances. This process generates new instances of larger sizes compared to the original ones, potentially introducing more complex structures.To preserve the block structures, the operators should leverage the constraint-variable 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 right-hand-side terms b i . 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 
experiment settings: 
 Benchmarks We consider four MILP problem benchmarks: combinatorial auctions (CA) [16] , capacitated facility location (FA) [17] , item placement (IP) [32] and workload appointment (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 NeurIPS 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 I.2.Metrics We leverage three metrics to 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 Jensen-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 [5] . (3) Feasible ratio is the proportion of feasible instances out of the total ones.Baselines 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 set 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-based approach G2MILP [19] . By leveraging masked VAE, G2MILP iteratively masks one constraint node in the bipartite graph and replaces it with a generated one.We consider three downstream tasks to demonstrate the effectiveness of the generated instances in practical applications. (1) Improving the performance of learning-based solvers, including predict-and-search (PS) [10] in Section 5.3 and the GNN approach for learning-to-branch [8] in Appendix F.1. (2) Hyperparameter tuning for the traditional solver (please see Appendix F.3).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.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 η.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-StuDio 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 a 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 baselines represent a severe degradation in computational hardness. Moreover, most of the instances generated by G2MILP in FA and WA datasets are infeasible. Encouragingly, MILP-StuDio is able to preserve the computational hardness and feasibility of the original instances, making it a 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.GNN branching policy [8] and predict-and-search [10] are two representative approaches of learningbased solvers. Here we report the results of PS built on Gurobi and leave the other in Appendix F.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,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.1. Table 4 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. In CA and FA, all the approaches can solve the instances to the optimal with gap abs = 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 gap abs metric. Methods built on PS does not perform well in CA compared to Gurobi, since CA is easy for Gurobi to solve and PS needs to spend time for network inference. Even so, PS+MILP-StuDio achieves a comparable performance to Gurobi. In the other three datasets, MILP-StuDio-enhanced PS outperforms other baselines, achieving the best solving time or gap abs .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 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 in 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 Table 4 : Comparison of solving performance in PS between our approach and baseline methods, under a 1, 000s 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. '↑' indicates that higher is better, and '↓' indicates that lower is better. We mark the best values in bold. 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 5 , 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 to generate increasingly harder instances during iterations.Generation Efficiency WA is a challenging benchmark with large instance sizes. The instances in WA have over 60,000 constraints and variables, making generation in WA especially time-consuming. We compare the generation time of the generation techniques to generate 1,000 instances. We set the time limit to 200 hours. The results in Table 6 show that MILP-StuDio significantly archives 3× acceleration compared to G2MILP, demonstrating high generation efficiency.We conduct ablation studies on three operators and modification ratios in Appendix F.2, and we also try to extend MILP-StuDio to MILPs without block structures in Appendix F. 4 and MILPs in the real-world industrial dataset in Appendix F.5. 
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 [19] is the first learning-based generation framework designed for generating general MILPs. This approach represents MILPs as bipartite graphs and utilizes a masked variational auto-encoder [35] to iteratively corrupt and replace parts of the original graphs to generate new ones.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 a 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. 
limitations and future avenue: 
 Our method originates from the field of operational research and is designed for instances with block structures. The performance of the detector in GCG influences the overall generation quality.Although the detector can identify a 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 of the instances, represents a promising avenue for future research.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, confidence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean.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 to 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. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
conclusion: 
 In In recent years, there has been notable progress in utilizing machine learning approaches to accelerate MILP solvers [36] . The learning-based approaches for solving MILPs can be broadly categorized into two main groups. The first group of works replaces specific components of the solver that greatly impact solving efficiency, such as branching [8, [37] [38] [39] , cut selection [40, 9, [41] [42] [43] , 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 learning-aided search approaches, which encompass techniques such as predict-and-optimize [10, 47, 48] , large neighbor search [49, 50] and so on. Among these methods, predict-and-search (PS) [10] has gained significant popularity. In PS, a 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 a 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 improvements in the solving efficiency and solution quality of MILP problems. However, training such learning-based models requires many MILP instances as training data, which can be challenging to obtain in real-world applications [19] . There is still ongoing research in this area to improve the sample efficiency of these solvers [10] and study the MILP generation techniques [19] . 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: This paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or 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? Answer: [Yes] Justification: Please refer to Appendix H 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? 
 
 Appendix: 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, 16, 17] . 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 on linear programming dedicate sections to discussing this decomposition algorithm [53, 21] , underscoring its importance. DWD is widely utilized when a CCM contains both block-diagonals and coupling constraints [52] , and can significantly accelerate the solving process for large-scale linear programming and mixed-integer linear programming.To identify the block structures in a raw CCM, the state-of-the-art detecting algorithm is implemented in GCG (Generic Column Generation) [33] , distributed with the SCIP framework [6] . This sophisticated 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-diagonal, and doubly bordered block-diagonal structures.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 is 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 plug-and-play module, MILP-StuDio offers great convenience for users.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 [25, [54] [55] [56] [57] [58] .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 [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-knapsack problem [55] , the security-constrained 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, 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 [32] released three wellrecognized 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 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.The key reasons why MILP instances exhibit block structures can be summarized as follows.• Repeated items or entities with similar attributes. In 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, in a scheduling problem, there may be multiple destinations or vehicles that exhibit similar characteristics. Similarly, in a knapsack problem, there can be multiple packages or items that are interchangeable from the perspective of operational research or mathematical modeling.• 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 a scheduling problem, all the vehicles may be able to 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 a certain vehicle, destination, or other item type.It is important to note that although MILP-StuDio is designed primarily for MILP instances with block structures, it has a 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).Branching is a critical component of branch-and-bound (B&B) solvers for mixed-integer linear programming (MILP) problems. It involves selecting a fractional variable to partition the feasible region in each iteration. The effectiveness of the chosen variable and the time required to make the branching decision are crucial factors that heavily impact the size of the branch-and-bound search 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-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 a 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 a GNN-based approach that employs behavior cloning to imitate the strong branching policy. In this approach, the B&B process is formulated as a 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 an action a from the set of integer variables with fractional values in the current state. The researchers parameterize the branching policy as a GNN model, which serves as a 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 D train and testing dataset D test . The GNN branching policy π θ is then trained by minimizing the cross-entropy lossL(θ) = - 1 |D train | (s,a)∈Dtrain log π θ (a | s).The imitation accuracy refers to the consistency of the learned GNN policy compared to the strong branching expert on the testing dataset D test :ACC = 1 |D test | (s,a)∈Dtest I arg max â π θ (â | s) = a ,where I is the indicator function defined as I(c) = 1 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.Different from learning-to-branch, which replaces certain heuristics in a traditional B&B solver, Predict-and-Search (PS) [10] belongs to another category of learning-based solvers that directly predict a feasible solution and subsequently perform the neighborhood search. PS aims to leverage a learning-based model to approximate the solution distribution p(x | I) given an instance I from the instance dataset D. Given an instance I, the solution distribution p(x | I) is defined as follows:p(x | I) = exp(-E(x, I))x exp(-E( x, I)), where the energy function E(x, I) = c ⊤ x, if x is feasible, +∞, otherwise. In the prediction step, PS employs a GNN model to approximate the solution distribution for the binary variables in a MILP instance. To train the GNN predictor p θ (x | I), PS adopts the assumption, as described in [39] , that the variables are independent of each other, i.e., p θ (x | I) = n i=1 p θ (x i | I).To calculate the prediction target, PS collects a set of m feasible solutions for each instance I, from which a vector p = (p 1 , p 2 , . . . , p n ) ⊤ is constructed. Here, p i = p(x i = 1|I) represents the probability of variable x i being assigned the value 1, given the instance I. The GNN predictor then outputs the predicted probability p θ (x i = 1|I) for each variable. Finally, the predictor p θ is trained by minimizing the cross-entropy lossL(θ) = - 1 N N j=1 n i=1 (p i log p θ (x i = 1 | I j ) + (1 -p i ) log(1 -p θ (x i = 1 | I j ))) ,where N represents the number of instances in the training set.In the search step, PS performs the neighborhood search based on the predicted partial solution x. This involves employing a traditional solver, such as SCIP [6] or Gurobi [5] , to explore the neighborhood B( x, △) of x in search of an optimal feasible solution. Here △ represents the trust region radius, and B( x, △) = {x ∈ R n | ∥ x -x∥ 1 ≤ △} is the trust region. The neighborhood search process is formulated as the following MILP problem,min x∈R n c ⊤ x, s.t. Ax ≤ b, l ≤ x ≤ u, x ∈ B( x, △), x ∈ Z p × R n-p .It is worth noting that the accuracy of the GNN predictor strongly influences the overall solving performance. A 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.In this section, we conduct experiments on the learning-to-branch task to further demonstrate the effectiveness of MILP-StuDio in enhancing the learning-based solvers.Experiment Setup We conduct the learning-to-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 as a 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 as a benchmark where the 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.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 https://github.com/ds4dm/learn2branch. This code leverages the state-of-the-art open-source solver SCIP 8.0.3 [6] as the backend solver. During testing, the solving time limit for each instance is set to 1,000 seconds. Consistent with the setting in [8] , we disabled solver restarts and only allowed the cutting plane generation module to be employed at the root node.Baselines The first baseline 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. In combination with the original 1,000 samples, we have a comprehensive enriched training dataset consisting of 11,000 samples. Thus, the three generation techniques lead to the following approaches: GNN+Bowly, GNN+G2MILP η = x, GNN+MILP-StuDio η = x, where η = x implies that we set the modification ratio to be x. Additionally, we compare our method with a GNN model trained on 11,000 samples collected from 1,100 original instances (GNN-11000). 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 a comprehensive evaluation, we also compare the solving performance of our method with that of the SCIP solver [6] (SCIP), which serves as our backend solver for comparison purposes.In this section, we conduct a comprehensive comparison of imitation accuracy and solving performance. As discussed in Appendix E.1, imitation accuracy serves as a crucial Table 5 : 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 MILP-StuDio can consistently improve the branching accuracy of the learned models. metric for evaluating the performance of the GNN model. Thus, we first compare our methods with other GNN-based baselines, including GNN, GNN-11000, GNN+Bowly, and GNN+G2MILP regarding imitation accuracy. The corresponding results are presented in Table 5 , where we observe that MILP-StuDio 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 6 . Notably, GNN+MILP-StuDio outperforms all the generation-technique-enhanced baselines and 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 of MILP-StuDio in enhancing the GNN branching policy, both in terms of imitation accuracy and solving performance. In this part, we investigate the influence of different generation operators and modification ratios of MILP-StuDio. 'MILP-StuDio (Optor) η = x' denotes the generation approach that uses the operator Optor ('red' means reduction, 'mix' represents mix-up, and 'exp' denotes expansion) and modification ratio η = x.Influence on the Similarity between the Generated and the Original Instances We conduct experiments on 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 7 suggest that the choice of generation operator and modification ratio can impact the values of the similarity scores. (1) MILP-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 8 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, as the modification ratio increases, we observe a decrease in the similarity scores. Considering 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 PS+MILP-StuDio η = 0.05. In PS+MILP-StuDio η = 0.05, we use the three 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 9 and 10 , 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.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-StuDio and G2MILP approaches. In PS+MILP-StuDio, we use the three operators (red, mix, and exp) to generate one-third of the 1,000 instances, respectively. The results are presented in Tables 11 and 12 , in which we compare the prediction loss and solving performance on the testing datasets for the different methods. Tables 11 and 12 showcase the following results. (1) MILP-StuDio consistently outperforms G2MILP across modification ratios. (2) A smaller modification ratio in MILP-StuDio can lead to a slightly better performance of PS. (3) MILP-StuDio is not sensitive to the masking ratio in general.In our Gurobi hyperparameter tuning experiment, We employ the Bayesian optimization framework provided by the HEBO package [59] . Each tuning process involves 100 trials, where different hyperparameter configurations are sampled and evaluated. To strike a balance between tuning efficiency 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 13 .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-StuDio 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 a 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 MILP-StuDio as tuned-Bowly, tuned-G2MILP, and tuned-MILP-StuDio, respectively. Experiment results in Table 14 demonstrate that Gurobi tuned with While MILP-StuDio is primarily designed to handle MILP instances with block structures in their CCMs, it is also important to evaluate its performance on wider classes of MILP problems, including those that may not exhibit such structured characteristics. Evaluating MILP-StuDio's capabilities in this broader context will highlight its potential for broader applications.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 constraint 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 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'.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 the improvement of the ML solvers. We use 100 original instances, following the generation algorithm described in [8] and [15] ), and generate 1,000 new instances using G2MILP and MILP-StuDio.The results demonstrate the outstanding performance of MILP-StuDio on general MILP instances without block structures. (1) Tables 15 and 17 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 MILP-StuDio better preserves instances' computational hardness with closer solving time to the original instances. (3) Tables 16 and 18 show that MILP-StuDio 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-structural large-scale Setcover benchmark (larger than that in Appendix E.4). We set the solving time limit 300s and η = 0.05. We mark the best performance in bold.Original Table 16 : The performance of the PS solver trained by instances generated by different methods on the non-structural Setcover benchmark. We set the solving time limit 300s and η = 0.05. We mark the best performance in bold. The similarity score, computational hardness, and feasibility ratio between the original and generated instances on the non-structural MIS benchmark. We set the solving time limit 300s and η = 0.05. We mark the best performance in bold. 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 η = 0.05. We mark the best performance in bold. 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 7 -10. The CCM visualization is a powerful tool to understand the structural properties 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 -10, 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 is crucial for the effective training and evaluation of machine learning-based MILP solvers. In contrast, Bowly struggles to capture the intricate CCM structures, while G2MILP introduces additional noise that disrupts the block structures in the generated CCMs.H.1 Implementation of Predict-and-SearchFor model structure, the PS models used in this paper align with those outlined in the original papers [10] . We use the code in https://github.com/sribdcn/Predict-and-Search MILP method to implement PS. For the PS predictor, we leverage a graph neural network comprising four half-convolution layers. We conducted all the experiments on a single machine with NVidia GeForce GTX 3090 GPUs and Intel(R) Xeon(R) E5-2667 V4CPUs 3.20GHz.In the training process of MILP-StuDio, we set the initial learning rate to be 0.001 and the training epoch to be 1000 with early stopping. In addition, the partial solution size parameter (k 0 , k 1 ) and neighborhood parameter ∆ are two important parameters in PS. The partial solution size parameter (k 0 , k 1 , ∆) represents the numbers of variables fixed with values 0 and 1 in a partial solution. The neighborhood parameter ∆ defines the radius of the searching neighborhood. We list these two parameters used in our experiments in Table 20 . EQUATIONIdentifying these different types of constraints and variables in a 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 a row in CCM A ∈ R m×n , x max is the maximum x-coordinate of nonzero entries, x min is the minimum x-coordinate of nonzero entries, and h x is the number of nonzero entries.Similarly, given a column in CCM, we denote the maximum y-coordinate of the nonzero entries by y max , the minimum y-coordinate of the nonzero entries by y min , and the number of nonzero entries by h y . we first give the following observations.• The nonzero entries in an M-Con often have a wide range of x-indices, i.e., large x max -x min and high standard deviation of x. • The nonzero entries in a B-Con often have a narrow range of x-indices, i.e., small x max -x min and small standard deviation of x. • For a Bd-Var, the nonzero entries in the corresponding column of CCM have a wide range of y-indices and high density (the proportion of nonzero entries in the column), i.e., large y max -y min and h y /m. • 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 (row_feat[0]), the proportion of nonzeros (density, row_feat [1] ), and ranges of the x-coordinates (row_feat [2] ). For a column in CCM, we consider the range (col_feat[0]) 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, ϕ 2 = 0.75, ϕ 3 = 0.5, ϕ 4 = 0.2, and ϕ 5 = 0.5, and set DB =True only in WA.In Section 4.2, we use GCG to reorder the rows and columns in 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 in CA contain different numbers of variables. Thus, we need to refine the partition to obtain better ones. Specifically, we find that many blocks in CCMs contain regular lines (mainly horizontal and diagonal lines). Thus, we define a 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 in 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 a different detection method.• Criterion 1: horizontal line detection. This criterion can 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 ζ = 4 for CA and ζ = 3 for other benchmarks.Block manipulation We leverage the classification results for constraints and variables to 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 5, which is the combination of DB-Cons, M-Cons, and B-Cons.EQUATIONDifferent types of constraints and variables have different manipulation methods. For example, when we apply the reduction and expansion operators, the manipulation of Bl-Vars can change the variable numbers, and the manipulation of B-Cons and DB-Cons can change the constraint numbers.For the mix-up and expansion operators, the number of the introduced M-Cons m 1 may mismatch that in the original instance m 2 . We define a successful matching if m 1 ≥ m 2 If m 1 = m 2 , the operators can be performed well. Otherwise, we drop the last m 1 -m 2 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 real-world 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. In certain MILP instances (like FA), the nonzero coefficients within the B-Cons (rows of D) remain consistent across the 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, we have incorporated a constraint refinement component that focuses on preserving the distribution of coefficient values in such scenarios. Specifically, we define a "nontrivial constraint" as a constraint that contains values other than 0, -1, and 1. For each MILP instance, we identify the non-trivial constraints in the block units. For the k-th non-trivial constraint a k in the block unit, we then compute the mean µ(i) k and variance σ (i)k 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 or expansion operations), it samples the new constraint coefficients for the introduced blocks from a Gaussian distribution N (µEQUATIONk ). This ensures that the generated instances maintain a similar distribution of non-trivial coefficients as observed in the original instances. The pseudo code of coefficient refinement is in Algorithm 3 and we activate this component in FA and IP. Justification: We do so in the abstract and introduction of this paper.EQUATIONGuidelines:• 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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?
2. 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?
3. 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: Weakness:
- 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
- The proposed method only works on problems with block structures, which limits its broader applicability
- The number of instances on the test bed is very small.
- Code is not provided.
questions: questions: Question:
- How does the choice of subgraphs during block decomposition and manipulation affect the overall quality and difficulty of the generated MILP instances?
- Could the proposed approach be potentially extended for more general MIP problems that without block structure?
limitations: limitations: Not applicable.
paper_summary: paper_summary: This paper presents a method for generating instances for mixed
integer programming that mimic the characteristics of existing
instances. The main insight is that the performance characteristics of
MIP solvers relate to the structure of the coefficient matrix of the
instance, with a few examples of such structure given in the paper. So
the new method is designed to discover such structures and replicate
them/combine them in the instances it generates. In experimental
results, the generator seems to produce instances whose behavior is
closer to that of the rest of the family.
strength_weakness: strength_weakness: I think the latter two of the evaluation criteria are
under-explored. Specifically:

- Improving the performance of learning-based solvers: I would expect
  a lot more detail on how these solvers were trained. In general,
  this aspect of the work is not explained very well, I think, and is
  presented as if it should self-evident (which it is not, to me).

- Hard benchmark generation: here there is just a very briefly
  explained generation of a pool of instances that progressively gets
  harder. I do not understand exactly why this test was performed like
  this, what the original instances, nor do I find this a convincing
  argument that the generator can produce instances of increasing
  difficulty.

Finally, I don't like the title of the paper at all. It feels labored
and gimmicky. It is not a reason to reject, though.

various places: operational research -> operations research

110: motivated -> motivating

(3): what is bold O?
questions: questions: No specific questions
limitations: limitations: Addressed sufficiently
paper_summary: paper_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%.
strength_weakness: strength_weakness: 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?
questions: questions: Please reply to my comment listed in 'Weaknesses'.
limitations: limitations: Not applicable.

Comments: title: We are looking forward to the reviewers' feedback
Looking forward to your feedback
Looking forward to your feedback
Extensive studies on the proposed two metrics
Applicability and Evaluation on the Real-World Dataset
Eagerly await your valuable feedback
Applicability and Evaluation on the Real-World Dataset
Eagerly await your valuable feedback
comment: Dear Reviewer zDfV,

Thanks for your kind support and for helping us improve the paper. We are writing to gently remind you that the author-reviewer discussion period will end in less than **12 hours**. We sincerely hope that our response has properly addressed your concerns on the **similarity metric for evaluation**. If so, **we would deeply appreciate it if you could raise your scores**. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.

Best,

Authors
Dear Reviewer jbdZ,

We sincerely thank you for your time and efforts during the rebuttal process. We are writing to gently remind you that the author-reviewer discussion period will end in less than **12 hours**. We have responded to your further comments and eagerly await your feedback, and we sincerely hope that our response has properly addressed your concerns. We would deeply appreciate it if you could kindly point out your further concerns about applicability so that we could keep improving our work. We sincerely thank you once more for your insightful comments and kind support.

Best,

Authors
Dear Reviewer jQXE,

We sincerely thank you for your time and efforts during the rebuttal process. We are writing to gently remind you that the author-reviewer discussion period will end in less than **12 hours**. We eagerly await your feedback to understand if our responses have adequately addressed your concerns. If so, **we would deeply appreciate it if you could consider raising your score**. If not, please let us know your further concerns, and we will continue actively responding to your comments. We sincerely thank you once more for your insightful comments and kind support.

Best,

Authors
We conducted extensive experiments to study the two metrics we proposed in our rebuttal. We sincerely hope that our rebuttal has properly addressed your concerns. **If so, we would deeply appreciate it if you could raise your scores. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.**

- **CCM Similarity**: To measure the similarity of the Constraint Coefficient Matrices (CCMs) between the original and generated instances, we represented the CCMs using 0-1 matrix representations. The points with value 1 represent the nonzero entries in the CCMs, while the points with value 0 represent the zero entries. We then calculated the matrix similarity between the generated and original instances using the following formula:

  $$\text{CCM similarity}=1-\frac{\\|A_1-A_2\\|_1}{\eta mn}$$

  where $A_1$ and $A_2$ are the 0-1 matrices of the original and generated instances, respectively, $m$ is the number of constraints, $n$ is the number of variables, and $\eta$ is the modification ratio.

  Due to the sparsity of the CCMs, $\eta mn$ can be very large compared to $\\|A_1-A_2\\|_1$. Thus, the CCM similarity is always close to 1, and 0.01 of the CCM similarity can lead to a great difference in the structure. Recall the computational results in Table 3 in our paper, where the performance of MILP-StuDio and G2MILP is the closest in CA, and differ significantly in the other three datasets. This coincides with the results in Table D1, where the CCM similarity between G2MILP and MILP-StuDio is the closest in CA. 

  **Table D1**: The average CCM similarity between the generated and original instances. 

  |      | G2MILP ($\eta=0.05$) | MILP-StuDio (mix $\eta=0.05$) |
  | ---- | -------------------- | ----------------------------- |
  | CA   | 0.95                 | 0.98                          |
  | FA   | 0.93                 | 0.99                          |
  | IP   | 0.91                 | 0.99                          |
  | WA   | 0.87                 | 0.95                          |

- **Constraint distribution.** To capture the differences in the distribution of constraint types, we constructed a 17-dimensional feature vector for each instance, where each component represents the proportion of a specific constraint type proposed in MIPLIB. We then calculated the cosine similarity between the feature vectors of the generated and original instances. Since the modification ratio $\eta$ is small, the cosine similarity is always close to 1, and 0.01 of the cosine similarity can lead to a great difference in the structure. The CCM similarity between G2MILP and MILP-StuDio is the closest in CA, consistent with the results of computational hardness in Table 3 of the paper. 

  **Table D2**: The average cosine similarity between the features of the generated and original instances. 

  |      | G2MILP ($\eta=0.05$) | MILP-StuDio (mix $\eta=0.05$) |
  | ---- | -------------------- | ----------------------------- |
  | CA   | 1.00                 | 1.00                          |
  | FA   | 99.07                | 1.00                          |
  | IP   | 99.53                | 1.00                          |
  | WA   | 99.86                | 1.00                          |
We would like to express our sincere gratitude once again for your valuable feedback and constructive suggestions. We have made detailed clarifications regarding our applicability. We sincerely hope that our additional response has adequately addressed your concerns. If so, we would greatly appreciate your consideration in raising the score. If there are any remaining concerns, please let us know, and we will continue to actively address your comments and work on improving our submission.



### **Applicability to MILPs in the Real-world Industrial Dataset**

To further demonstrate the effectiveness in real-world applications, we also conduct experiments on a real-world scheduling dataset at an anonymous enterprise, which is **one of the largest global commercial technology enterprises**. The instances **do not** present clear block structures. The results in the following table 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 ML PS solver and list the solving time, objective value, and node number in Table B6 as follows. MILP-StuDio outperforms other baselines in this dataset, highlighting its strong performance and applicability.

| | | Solving time (1000s time limit) |  || Objective |   |   | Node Number |  |
| -| -| -| - | ------- | - | - | - | - | - |
|  | PS | G2MILP+PS  | MILP-StuDio+PS | PS | G2MILP+PS | MILP-StuDio+PS | PS   | G2MILP+PS   | MILP-StuDio+PS |
| instance 1|1509652.00|1509652.00|1509652.00|144.21| 146.67| 131.80 | 38767.00 | 37647.00|39513.00 |
| instance 2|205197.00| 205197.00|205197.00| 5.83| 9.51| 10.11| 723.00   | 746.00| 1047.00  |
| instance 3|7483.00 | 7483.00 | 7483.00| 29.50   | 32.68     | 38.49   | 555.00| 751.00| 901.00 |
| instance 4|447781.00  | 384454.99  | 318675.99 | 1000.00 | 1000.00| 1000.00| 16545.00 | 6201.00 | 5186.00|
| instance 5|1465601.00 | 1465601.00 | 1465601.00 | 186.85| 81.67| 63.55| 24317.00 | 11481.00| 9732.00 |
| instance 6| 1293554.00 | 1293554.00  | 1293554.00  | 38.65| 25.41| 32.45| 3471.00  | 2357.00| 3002.00 |
| instance 7| 1293554.00 | 1293554.00  | 1293554.00 | 38.96| 24.82| 31.76| 3471.00  | 2357.00| 3002.00|
| instance 8| 612151.00  | 612151.00  | 612151.00| 0.18| 0.35| 0.28| 13.00| 55.00| 13.00 |
| instance 9| 1578141.00 | 1578141.00 | 1578141.00| 28.53| 26.74|23.61| 3083.00  | 3207.00  | 3150.00  |
| instance 10| 1149250.00 | 1149250.00|1149250.00| 7.33| 8.89 | 8.05  | 1.00     | 154.00| 1.00  |
| instance 11| 1030555.00 | 1030555.00 |1030555.00| 0.27|0.35| 0.34 | 1.00| 1.00| 1.00 |
| instance 12| 1216445.00 | 1216445.00|1216445.00| 23.64| 23.10| 13.83    | 1384.00| 1384.00 | 1.00 |
| Average     | 984113.66  | 978836.50  | **973354.92**|125.35| 115.02|**112.86**| 7694.25  | 5528.42     | **5462.42**    |
Dear Reviewer jbdZ,

Thanks for your kind support and for helping us improve the paper. We sincerely hope that our rebuttal has properly addressed your concerns. **If so, we would deeply appreciate it if you could raise your scores. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.**

Best,

Authors
We would like to express our sincere gratitude once again for your valuable feedback and constructive suggestions. We have made detailed clarifications regarding our applicability. We sincerely hope that our additional response has adequately addressed your concerns. If so, we would greatly appreciate your consideration in raising the score. If there are any remaining concerns, please let us know, and we will continue to actively address your comments and work on improving our submission.

### Applicability to General MILPs in Multiple Downstream Tasks

- To the best of our knowledge, we are **the first to conduct an extensive study** on the applications of multiple downstream tasks as follows, which gives a comprehensive study of the wide usage of MILP-StuDio. MILP-StuDio achieves **state-of-the-art performance in the three tasks**.
  - **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 in our paper). This downstream task tests the benefit of a generation method to enhance the performance of a learning-based solver.
  - **Hyperparameter tuning for traditional solvers** (Table 14 in our paper). This downstream task tests the benefit of a generation method to enhance the performance of a traditional solver. This test is meaningful in industrial applications since the number of high-quality instances used for tuning is a bottleneck for the performance of a traditional solver.
  - **Hard instances generation for benchmark construction** (Figure 5 in the paper and Figures C1-2 in the attached pdf). Hard instance generation task is important as it provides valuable resources to evaluate solvers and thus potentially motivates more efficient algorithms. We find that MILP-StuDio can obtain a harder dataset in the given iterations than the baselines in Figure C2.
- MILP-StuDio is **the first method that can be applied to MILPs with block structures**.  Though commonly seen and widely used in real-world applications, MILPs with block structures remain a great challenge for existing generation methods. Existing methods fail to preserve the feasibility and computational hardness of these instances, while MILP-StuDio preserves almost 100% feasibility and comparable computational hardness.
- MILP-StuDio **can be applied to MILPs without block structures**. We can easily extend our framework to general MILPs as we state in rebuttal.

### Applicability to MILPs in the Real-world Industrial Dataset

To further demonstrate the effectiveness in real-world applications, we also conduct experiments on a real-world scheduling dataset at an anonymous enterprise, which is **one of the largest global commercial technology enterprises**. The instances **do not** present clear block structures. The results in the following table 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 ML PS solver and list the solving time, objective value, and node number in Table B6 as follows. MILP-StuDio outperforms other baselines in this dataset, highlighting its strong performance and applicability.

| | | Solving time (1000s time limit) |  || Objective |   |   | Node Number |  |
| -| -| -| - | ------- | - | - | - | - | - |
|  | PS | G2MILP+PS  | MILP-StuDio+PS | PS | G2MILP+PS | MILP-StuDio+PS | PS   | G2MILP+PS   | MILP-StuDio+PS |
| instance 1|1509652.00|1509652.00|1509652.00|144.21| 146.67| 131.80 | 38767.00 | 37647.00|39513.00 |
| instance 2|205197.00| 205197.00|205197.00| 5.83| 9.51| 10.11| 723.00   | 746.00| 1047.00  |
| instance 3|7483.00 | 7483.00 | 7483.00| 29.50   | 32.68     | 38.49   | 555.00| 751.00| 901.00 |
| instance 4|447781.00  | 384454.99  | 318675.99 | 1000.00 | 1000.00| 1000.00| 16545.00 | 6201.00 | 5186.00|
| instance 5|1465601.00 | 1465601.00 | 1465601.00 | 186.85| 81.67| 63.55| 24317.00 | 11481.00| 9732.00 |
| instance 6| 1293554.00 | 1293554.00  | 1293554.00  | 38.65| 25.41| 32.45| 3471.00  | 2357.00| 3002.00 |
| instance 7| 1293554.00 | 1293554.00  | 1293554.00 | 38.96| 24.82| 31.76| 3471.00  | 2357.00| 3002.00|
| instance 8| 612151.00  | 612151.00  | 612151.00| 0.18| 0.35| 0.28| 13.00| 55.00| 13.00 |
| instance 9| 1578141.00 | 1578141.00 | 1578141.00| 28.53| 26.74|23.61| 3083.00  | 3207.00  | 3150.00  |
| instance 10| 1149250.00 | 1149250.00|1149250.00| 7.33| 8.89 | 8.05  | 1.00     | 154.00| 1.00  |
| instance 11| 1030555.00 | 1030555.00 |1030555.00| 0.27|0.35| 0.34 | 1.00| 1.00| 1.00 |
| instance 12| 1216445.00 | 1216445.00|1216445.00| 23.64| 23.10| 13.83    | 1384.00| 1384.00 | 1.00 |
| Average     | 984113.66  | 978836.50  | **973354.92**|125.35| 115.02|**112.86**| 7694.25  | 5528.42     | **5462.42**    |
Dear Reviewer jQXE,

We would like to extend our sincere gratitude for the time and effort you have devoted to reviewing our submission. Your positive feedback, insightful comments, and constructive suggestions have been invaluable to us, guiding us in improving the quality of our work!

We are writing to gently remind you that the author-reviewer discussion period will end in less than 36 hours. We eagerly await your feedback to understand if our responses have adequately addressed all your concerns. If so, we would deeply appreciate it if you could raise your score. If not, we are eager to address any additional queries you might have, which will enable us to enhance our work further.

Once again, thank you for your guidance and support.

Best,

Authors
Dear Reviewer jbdZ,

We sincerely thank you for your valuable comments throughout the review period. We appreciate your time and feedback and would be grateful for any further specifics regarding areas that you believe we have not adequately addressed.

**Regarding the applications of MILPs with block structures.** MILPs with block structures indeed have a wide application in practice. Actually, as we have pointed out in **Appendix C**, the key reasons why MILP instances exhibit block structures can be summarized as follows.

- **Repeated items or entities with similar attributes.** In 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, in a scheduling problem, there may be multiple destinations or vehicles that exhibit similar characteristics. Similarly, in a knapsack problem, there can be multiple packages or items that are interchangeable from the perspective of operational research or mathematical modeling.

- **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 a scheduling problem, all the vehicles may be able to pick up items from the same set of places and satisfy the demand of the same set of locations. 

  

**Regarding the applicability of existing methods.** Though wide usage of MILPs with blocks, existing methods fail in these MILPs, leading to infeasibility or degradation of computational hardness. This severely limits the MILP generation method in real-world applications. Our work is a complement of existing methods that are meaningful for the MILP generation field.



**Regarding the applicability of our method.** We conduct extensive experiments to demonstrate the effectiveness of our method to the general MILP problems with or without block structures. We conduct **six groups of experiments** from **Table A1-6** in the attached pdf, which shows the superiority of MILP-StuDio in terms of the **statistical properties**, mathematical properties, and the **benefits to the downstream tasks**.



Thanks for your kind support and for helping us improve the paper. We sincerely appreciate your valuable suggestions.
Dear Reviewer Rqw8,

Thanks for your kind support and for helping us improve the paper. We sincerely hope that our rebuttal has properly addressed your concerns. If so, we would deeply appreciate it if you could raise your scores. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.

Best,

Authors
Dear Reviewer zDfV,

Thanks for your kind support and for helping us improve the paper. We sincerely hope that our rebuttal has properly addressed your concerns. If so, we would deeply appreciate it if you could raise your scores. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.

Best,

Authors
Dear Reviewer JQXE,

We are writing as the authors of the paper titled "MILP-StuDio: MILP Instance Generation via Block Structure Decomposition" (ID: 14255). Thanks again for your valuable comments and constructive suggestions, which are of great help to improve the quality of our work. As the deadline for the author-reviewer discussion period is approaching (due on Aug 13), we are looking forward to your further comments and/or questions.

We sincerely hope that our rebuttal has properly addressed your concerns. If so, we would deeply appreciate it if you could raise your scores. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our work.

Best,

Authors
Thanks for the authors' responses. But I still have concerns about applicability of this approach so I will keep my score.
Thanks very much for your reply! I acknowledge that I have read your response.
Dear Reviewer Rqw8,

Thank you for your kind support and valuable feedback on our paper! We deeply appreciate your insightful comments and constructive suggestions.

Best,

Authors
Thank you for you response. I liked in particular the general comments you gave on the presence of block structure in industrial instances. These comments would make a good addition to the paper.