NeurIPS 2024｜拆解高复杂运筹问题的砖石，打破数据稀缺的瓶颈，中科大提出高质量运筹数据生成方法

科技 2024-12-13 20:03 德国

论文作者刘昊洋是中国科学技术大学 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.

微信公众号后台回复

加群：加入全球华人OR|AI|DS社区硕博微信学术群

资料：免费获得大量运筹学相关学习资料

人才库：加入运筹精英人才库，获得独家职位推荐

电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...

加入我们：加入「运筹OR帷幄」，参与内容创作平台运营

知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流

文章须知

文章作者：机器之心

微信编辑：疑疑

文章转载自『机器之心』公众号，原文链接：NeurIPS 2024｜拆解高复杂运筹问题的砖石，打破数据稀缺的瓶颈，中科大提出高质量运筹数据生成方法

关注我们

运筹OR帷幄

致力于成为全球最大的运筹学中文线上社区

推荐 | 文献综述撰写攻略

交通 | 城市轨道交通车辆配置与列车时刻表优化公众号格式

香港中文大学（深圳）& 深圳市大数据研究院张纵辉教授项目组诚招硕/博研究生、博士后、实习生

赠书活动 | 庄晓天《智能供应链：预测算法理论与实战》

报道 | 2025年1月-3月国际运筹优化会议汇总

『运筹OR帷幄』招募令 | 期待你的加入

【运筹OR帷幄】一周博士申请&会议信息汇总--2024.12(2)

供应链 | POMS论文解读：食品银行供应链中易腐物品的公平分配

求解器中一个参数的介绍：Degenerate Simplex Moves

最后俩天早鸟价：优惠1000元！寒假第三期运筹优化求解器/LLM决策科学/Python数据分析及其在业界实际应用培训课（线上）

学界|瑞士洛桑联邦理工学院招募计算音乐研究博士

服务运营 | 贸易信贷供应对零售库存的影响

NeurIPS 2024｜拆解高复杂运筹问题的砖石，打破数据稀缺的瓶颈，中科大提出高质量运筹数据生成方法

今年顶会这情况。。。大家提前做准备吧！

祝贺戴彧虹副院长当选为国际运筹学会联合会（IFORS）副主席

优化 | KM 定理：不动点迭代的重要工具

分享一下我强化学习的工作：Simple Policy Optimization

交通 | 无人机配送的设施选址决策

全奖｜瑞士洛桑联邦理工学院（EPFL）离散优化小组招收博士

AI顶会AAAI收了一篇论文：没算法没实验，全靠idea思路好...

报道 | 第十六届“行为运筹学与行为运营管理”研讨会会议通知（第三轮）

早鸟优惠1000元！寒假第三期运筹优化求解器/LLM决策科学/Python数据分析及其在业界实际应用培训课（线上）

学界|伦敦政治经济学院招募离散数学、运筹学和博弈论博士

交通 | 不确定优化：均值-方差/标准差最短路模型

双非全拒到博士全奖！逆袭到底有什么秘籍？我来告诉你！

中国团队首次刷新Sartori-PDPTW世界纪录，华为GTS联合深圳市大数据研究院、港中深以昇腾算力实现AI求解器突破

学界|瑞典隆德大学大学招募理论计算机科学\组合优化博士

优化 | 一个实用的端到端的深度学习库存模型

报道 | MIIS 2024 正式注册通道开启

供应链｜亚马逊魔法箱:揭秘全球最强大的物流网络

早鸟优惠1000元！第三期运筹优化求解器/LLM决策科学/Python数据分析及其在业界实际应用培训课（线上）

学界招聘|多伦多大学招募离散优化博士后

服务运营 | Operations Research: 具有异质性服务器池的队列的广义c/µ规则

全奖｜英国伯明翰大学招收计算理论、复杂性相关博士

供应链中订单履约系统与一盘货

优化 | 强化学习中的蒙特卡罗方法

【运筹OR帷幄】一周博士申请&会议信息汇总--2024.12(1)

分类

时事

民生

政务

教育

文化

科技

财富

体娱

健康

情感

旅行

百科

职场

楼市

企业

乐活

学术

汽车

时尚

创业

美食

幽默

美体

文摘

原创标签

时事社会财经军事教育体育科技汽车科学房产搞笑综艺明星音乐动漫游戏时尚健康旅游美食生活摄影宠物职场育儿情感小说曲艺文化历史三农文学娱乐电影视频图片新闻宗教电视剧纪录片广告创意壁纸头像心灵鸡汤星座命理教育培训艺术文化金融财经健康医疗美妆时尚餐饮美食母婴育儿社会新闻工业农业时事政治星座占卜幽默笑话独立短篇连载作品文化历史科技互联网

发布位置

广东北京山东江苏河南浙江山西福建河北上海四川陕西湖南安徽湖北内蒙古江西云南广西甘肃辽宁黑龙江贵州新疆重庆吉林天津海南青海宁夏西藏香港澳门台湾美国加拿大澳大利亚日本新加坡英国西班牙新西兰韩国泰国法国德国意大利缅甸菲律宾马来西亚越南荷兰柬埔寨俄罗斯巴西智利卢森堡芬兰瑞典比利时瑞士土耳其斐济挪威朝鲜尼日利亚阿根廷匈牙利爱尔兰印度老挝葡萄牙乌克兰印度尼西亚哈萨克斯坦塔吉克斯坦希腊南非蒙古奥地利肯尼亚加纳丹麦津巴布韦埃及坦桑尼亚捷克阿联酋安哥拉