通过保留块结构生成高质量混合整数规划实例,提升求解器效率。
MILP-StuDio: MILP Instance Generation via Block Structure Decomposition
- 基于约束系数矩阵的块结构分解生成实例
- 生成实例可减少学习型求解器10%以上求解时间
- 适合需要真实难解实例的研究者与求解器开发者
混合整数线性规划(MILP)是广泛应用的数学建模方法。实际中,提升MILP求解器性能通常需大量高质量数据,但收集困难。现有生成方法未考虑约束系数矩阵(CCM)中的特定块结构,易破坏问题原始形式,生成计算上过于简单或不可行的实例。为此,我们提出新框架MILP-StuDio,通过块结构分解生成高质量实例。该方法先识别并分解CCM中的块,作为实例的基本单元;设计移除、替换、追加三种操作,灵活构建新实例。其优势在于有效保持实例的可行性和计算难度。在常用基准测试中,使用MILP-StuDio生成的实例,使学习型求解器求解时间显著减少超10%。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。