AIxiv专栏是AI在线发布学术、技术内容的栏目。过去数年，AI在线AIxiv专栏接收报道了2000多篇内容，覆盖全球各大高校与企业的顶级实验室，有效促进了学术交流与传播。如果您有优秀的工作想要分享，欢迎投稿或者联系报道。投稿邮箱：[email protected]；[email protected]
论文作者刘昊洋是中国科学技术大学 2023 级硕士生，师从王杰教授，主要的研究方向为强化学习与学习优化理论及方法。他曾在 NeurIPS、ICML 和 ICLR 等人工智能顶级会议上发表论文三篇，曾获中国科学技术大学黄渝纪念奖学金、华为奖学金等荣誉。
近日，中科大王杰教授团队（MIRA Lab）提出了矩阵分块分解技术生成数学优化问题，有效解决运筹优化领域数据稀缺的问题，大幅提升 AI 运筹求解器求解质量。
数学优化在运筹优化领域中具有核心地位，是一种通过构建数学模型来寻找最优解的技术。混合整数线性规划（MILP）是一种基础的数学优化问题，在实际世界中有广泛的应用，如工业、金融、物流和芯片设计，其求解效率关系到重大的经济收益。
王杰教授团队提出了一种新颖的 MILP 生成框架，该框架在整个生成过程中考虑问题分块结构，从而生成高质量的优化问题样例，大幅提升求解器的求解质量。目前论文已被人工智能顶级会议 NeurIPS 2024 接收。
论文标题：MILP-StuDio: MILP Instance Generation via Block Structure Decomposition
论文链接：https://arxiv.org/abs/2410.22806
近年来，该团队已在国际人工智能顶级会议上发表了混合整数线性规划、偏微分方程等数据生成方法相关的论文四篇 [1-4]，提出了混合整数优化领域首个基于机器学习的数据生成框架 G2MILP。目前，G2MILP [2] 发表在人工智能顶会 NeurIPS 2023 中并取得大会 Spotlight，之后扩展了难例生成的相关任务并公开于 [5]。
引言
为了加速 MILP 求解过程，传统求解器和 AI 求解器都在很大程度上依赖大量高质量的 MILP 样例进行超参数调优或模型训练。然而，由于高昂的获取成本或隐私问题，获取大量样例通常是困难的，稀缺的训练数据成为严重制约求解器性能的瓶颈。
因此，研究者希望能开发 MILP 优化问题的数据生成技术来缓解数据稀缺的挑战。近年来，通用 MILP 生成方面取得了一些进展。然而，现有方法仍然面临显著的挑战。
（1）目前的方法在生成过程中往往忽略了 MILP 约束系数矩阵中与问题建模紧密相连的特定块状结构，这导致了块状结构的破坏和问题建模的改变，进而产生了难度过低或者不可解的样例。
（2）现有方法未能生成与原始样例不同大小的样例，限制了样例的多样性。
（3）在生成大规模样例时，现有方法需要大量运行时间。
针对上述挑战，研究者尝试分析和利用问题结构以解决上述问题。研究者观察到许多现实世界的 MILP 问题在其约束系数矩阵中表现出重复的块单元模式。基于此，研究者提出了一种新颖的 MILP 生成框架，该框架在整个生成过程中考虑问题分块结构，从而生成高质量的样例。
背景和问题介绍
混合整数线性规划（MILP）是一种应用广泛的通用优化模型，其具体形式如下
现实应用中，许多 MILP 样例在其约束系数矩阵 A 中表现出由多个块单元组成的分块结构。这些具有块结构的 MILP 问题，在现实场景中广泛存在，包括多个被广泛研究的多个数据集，如组合拍卖（CA）、容量设施选址（FA）、物品放置（IP）、多重背包（MIK）和工作负载平衡（WA）等。在图 1 中，研究者使用可视化这些 MILP 样例的约束系数矩阵。
图 1：四个常见运筹优化问题中约束系数矩阵的分块结构
在运筹学中，研究人员早已注意到来自同一问题类型的样例中约束系数矩阵的相似块结构，并意识到约束系数矩阵在确定问题建模和数学性质中的关键作用。因此，现有的一些 MILP 方法已经利用了该分块结构，并在加速此类 MILP 问题的求解过程中展现出了巨大潜力，著名的例子包括求解大规模 MILP 问题的 Dantzig-Wolfe 分解和 Benders 分解。
方法介绍
分块结构分析
现实场景中很多问题，将其约束系数矩阵会重新排列可以得到明显得分块结构。图 2 是一些简单的分块例子，研究者将块单元用蓝色突出显示。尽管这些结构相对简单，但它们是更复杂块结构的基本构建块，并在运筹学中广泛使用。
图 2：一些简单的分块约束矩阵例子
约束矩阵分块
研究者根据约束系数矩阵变量划分算法进行块分解。具体而言，研究者提取约束系数矩阵中块单元的子矩阵。在上面的三个分块例子中，第一个约束矩阵的分块单元子矩阵是
，在第二个例子中是 
，在第三个例子中是 
。最后，研究者将约束系数矩阵划分为一系列的分块单元的子矩阵。
各样例之间的块单元在内部结构上展现出显著的相似性。这些共同特征表明，块单元的分布蕴含着关于问题建模信息，使其成为重构新样例的理想砖石。在获得分块单元子矩阵后，并将其收集起来构建一个样例结构库。这个结构库作为收集到的子图的存储库，允许高效存储、检索和利用块信息。
通过分块实现可扩展生成
借助结构库，研究者设计了三类生成算子，生成具有多种规模的高质量 MILP 样例。
块删减：随机从原始样例中抽取一个分块单元并将其移除，生成的 MILP 样例相比原始样例具有更小的规模。
块替换：随机从原始样例中抽取一个块单元，然后用结构库中抽取的另一个块单元进行替换。块替换算子通过引入外部块单元带来了结构上的变化。
块增加：从结构库中随机抽取一个块单元并将其添加到原始样例中。这个过程生成的新样例规模相较于原始样例更大。
为了保留块结构，这些操作符应根据约束和变量的分类进行精确匹配结果。
研究者的方法具体流程如图 3 所示。
图 3：方法的总体流程。
实验
研究者实验测试了生成样例的求解时间，发现该方法生成样例的计算难度和可行性与原样例的更加相近。说明生成的样例数学性质得到更好的保持。此外，研究者还将方法生成的样例作为 AI 求解器的训练数据，实验表明该的方法能相比于其他数据生成方法能够跟显著提升求解器的性能，在困难的样例上相比于 Gurobi 降低 66.9% 的 gap。
[1] MILP-StuDio: MILP Instance Generation via Block Structure Decomposition. Haoyang Liu, Jie Wang, Wanbo Zhang, Zijie Geng, Yufei Kuang, Xijun Li, Bin Li, Yongdong Zhang, Feng Wu. NeurIPS 2024.
[2] A Deep Instance Generative Framework for MILP Solvers Under Limited Data Availability. Zijie Geng, Xijun Li, Jie Wang, Xiao Li, Yongdong Zhang, Feng Wu. NeurIPS 2023, Spotlight.
[3] Accelerating Data Generation for Neural Operators via Krylov Subspace Recycling. Hong Wang, Zhongkai Hao, Jie Wang, Zijie Geng, Zhen Wang, Bin Li, Feng Wu. ICLR 2024, Spotlight.
[4] Accelerating PDE Data Generation via Differential Operator Action in Solution Space. Huanshuo Dong, Hong Wang, Haoyang Liu, Jian Luo, Jie Wang. ICML 2024.
[5] G2MILP: Learning to Generate Mixed-Integer Linear Programming Instances for MILP Solvers. Jie Wang, Zijie Geng, Xijun Li, Jianye Hao, Yongdong Zhang, Feng Wu.