目前论文已被人工智能顶级会议NeurIPS 2024接收。

原标题：NeurIPS 2024｜拆解高复杂运筹问题的砖石，打破数据稀缺的瓶颈，中科大提出高质量运筹数据生成方法
文章来源：机器之心
内容字数：5778字

研究背景与挑战

近年来，混合整数线性规划（MILP）在运筹优化领域的应用愈发广泛，但其求解过程依赖于大量高质量的样例。然而，由于获取样例的高昂成本或隐私问题，导致训练数据稀缺，限制了求解器的性能。为此，研究者们亟需开发MILP优化问题的数据生成技术，以缓解这一挑战。

新框架MILP-StuDio

中国科学技术大学王杰教授团队提出了一种新颖的MILP生成框架——MILP-StuDio，该框架在整个生成过程中考虑问题的分块结构。这一方法有效解决了传统生成方法中存在的样例难度过低或不可解等问题，并显著提升了生成样例的质量。

方法介绍

研究者分析了现实世界中许多MILP问题的约束系数矩阵，发现其存在明显的分块结构。基于此，研究者提出了一种块分解的方法，将约束系数矩阵划分为一系列块单元的子矩阵，并建立样例结构库以高效存储和利用这些块信息。研究者设计了三类生成算子：块删减、块替换和块增加，通过这些操作生成多种规模的高质量MILP样例。

实验结果

实验表明，使用该方法生成的样例在求解时间和可行性方面与原样例相近，数学性质得到了更好的保持。此外，将生成的样例用作AI求解器的训练数据，结果显示该方法相较于其他数据生成方法显著提升了求解器的性能，降低了求解难度。

论文信息

该研究成果已被国际人工智能顶级会议NeurIPS 2024接收，论文标题为《MILP-StuDio: MILP Instance Generation via Block Structure Decomposition》。相关论文链接为：https://arxiv.org/abs/2410.22806。

如您有优秀的研究工作想要分享，欢迎联系投稿邮箱：liyazhou@jiqizhixin.com；zhaoyunfeng@jiqizhixin.com。

联系作者

文章来源：机器之心
作者微信：
作者简介：专业的人工智能媒体和产业服务平台