MILP-StuDio 是什么？按分块结构生成优化问题来训练 AI 求解器

MILP-StuDio 是一个生成混合整数线性规划问题实例的框架，由中国科学技术大学王杰教授团队（MIRA Lab）在 2024 年提出，论文标题是《MILP-StuDio：通过分块结构分解生成 MILP 实例》，被人工智能领域的重要会议接收。名字里的 StuDio 来自分块结构分解（Block Structure Decomposition）。

背景：用 AI 加速运筹求解

混合整数线性规划（MILP）是一类在工业界极其常用的数学优化问题，生产排程、物流配送、电力调度、芯片设计里的许多决策问题都可以写成 MILP。这类问题求解起来往往很难，规模稍大就可能要算很久。近年来，研究者开始用机器学习来辅助传统求解器，比如让 AI 学会更好的分支策略、预测哪些变量更可能取某个值，从而加速求解。但训练这样的 AI 需要大量的问题实例作为数据，而真实业务中的问题实例往往很少，还涉及商业机密，难以获取。

现有生成方法的问题

一个解决办法是自动生成大量的合成问题实例。但研究者发现，已有的生成方法往往会破坏真实问题中固有的结构：真实的 MILP 问题，其约束矩阵常常呈现出明显的分块结构，比如一个多工厂的生产问题，每个工厂内部的约束形成一个块，少数几条全局约束把各个块连接起来。生成的实例如果丢掉了这种结构，就和真实问题差别很大，用它们训练出来的 AI 在真实问题上效果不佳，甚至生成的问题根本不可解。

MILP-StuDio 怎么做

MILP-StuDio 的核心思路是保留问题的分块结构。它先识别出原始问题约束系数矩阵中的分块结构，把实例分解成一个个块单元，这些块相当于问题的“积木”。然后通过对这些块进行删除、替换和追加等操作，重新组合出新的实例。因为新实例由真实问题中的块拼成，它们保留了原问题的结构特征和计算难度，同时又在规模和具体数值上有所变化。它还能生成比原始实例规模更大的问题。

效果

论文报告，用 MILP-StuDio 生成的实例训练 AI 求解器，能显著提升求解质量，减少求解时间，效果明显优于用已有方法生成的数据。这为在真实数据稀缺的情况下训练 AI 运筹求解器，提供了一个实用的数据生成工具。