Abstract
Mixed-integer linear programming (MILP) is one of the most popularmathematical formulations with numerous applications. In practice, improvingthe performance of MILP solvers often requires a large amount of high-qualitydata, which can be challenging to collect. Researchers thus turn to generationtechniques to generate additional MILP instances. However, existing approachesdo not take into account specific block structures -- which are closely relatedto the problem formulations -- in the constraint coefficient matrices (CCMs) ofMILPs. Consequently, they are prone to generate computationally trivial orinfeasible instances due to the disruptions of block structures and thusproblem formulations. To address this challenge, we propose a novel MILPgeneration framework, called Block Structure Decomposition (MILP-StuDio), togenerate high-quality instances by preserving the block structures.Specifically, MILP-StuDio begins by identifying the blocks in CCMs anddecomposing the instances into block units, which serve as the building blocksof MILP instances. We then design three operators to construct new instances byremoving, substituting, and appending block units in the original instances,enabling us to generate instances with flexible sizes. An appealing feature ofMILP-StuDio is its strong ability to preserve the feasibility and computationalhardness of the generated instances. Experiments on the commonly-usedbenchmarks demonstrate that using instances generated by MILP-StuDio is able tosignificantly reduce over 10% of the solving time for learning-based solvers.