1. e-works数字化企业网
  2. 新闻
  3. 资讯

当大模型开始研究整数规划:34个开放性难题迎来突破

 
2026年09月26日
关键字:大模型  

—LLM4MIP:求解器+自主思考的AI

电网的机组启停、高铁的运行时刻、大模型训练与推理中的GPU资源分配,看似不同的决策任务,背后都可能是一道混合整数规划问题(Mixed Integer Programming,MIP)。求解这类问题,不仅要找到一个好方案,还要证明“没有更好的方案”;而一些极难实例,长期未能跨过这道门槛。

求解MIP通常依靠Gurobi、COPT、CPLEX等专业求解器,通过分支定界、割平面等算法搜索方案并证明最优性。但一些困难问题仍需要研究者分析结构、设计针对性方法。这也引出一个问题:大模型能否参与这一过程,帮助求解器取得突破?

近期,斯坦福大学、上海财经大学、上海数学与交叉学科研究院(SIMIS)、杉数科技COPT团队共同启动了LLM4MIP项目:(https://llm4mip.github.io/)。

LLM4MIP项目从217个MIPLIB(v36)“open”实例中随机选取了 132 个例子,这些例子均尚未记录最优性或不可行性。他们让大模型(GPT5.6-sol)阅读问题信息、寻找问题背景、分析模型结构,并按需要调用COPT、Gurobi 等优化求解器。重点是利用大模型强大的发散思维和推理能力,寻找问题本身可利用的规律,再据此设计求解方法。大模型提出思路,求解器承担计算,最终结果通过外部检查确认,并进一步从中总结可能的skill,应用于新的问题求解。

结果是非常振奋人心的。LLM4MIP 在 132 个开放实例上中有77个取得了可验证的求解进展:32 个完成了求解最优性判定、2 个完成了不可行性证明、29 个实现了可行解提高,以及 66 个优于 COPT 10 小时基线的全局界。这些成果展示了大模型通过结构分析和针对性方法推进困难优化问题求解的潜力。部分结果已经在最新的MIPLIB求解网站上验证通过并公开出来:https://miplib.zib.de/CHANGELOG.html#2026。

132 个难问题上的可验证改进

衡量一个优化问题是否进展,主要体现在三个方面:证明最优性、找到更好的可行解,以及强化全局下界。可行解与全局下界之间的差距越小,离最优解的距离就越接近。

确定最优答案:32 个实例达到最优判定,另有 2 个证明不可行。
找到更好的可行解:相较于 MIPLIB v36,25 个实例改善已有可行解,4 个此前没有已知可行解的实例首次找到严格可行解,共更新 29 个实例的记录。
强化全局界:66 个实例的全局下界优于 COPT 运行 10 小时的结果,进一步缩小与最优值的差距。

从成果的覆盖范围来看,132 个实例中共有 77 个至少一项界得到改善:11 个仅改善可行解,48 个仅改善全局界,18 个同时改善两端。另一方面,32 个实例达到最优判定,2 个证明不可行。“

MIPLIB v37 榜单中,29 个问题首位解标注为 LLM4MIP

在 2026 年 9 月 24 日发布的 MIPLIB v37 榜单中,有 29 个问题的首位解标注为 LLM4MIP,全部达到当前官网最好目标值。其中,27 个明确领先于其他公开解或为唯一公开可行解,另有 2 个并列或近似并列。这次更新将项目中的可行解成果呈现在公共基准库中。完整的 29 个实例页面截图见网站。

大模型如何识别并利用问题的结构规律

一个直观案例来自图上的割打包问题:每个“割”把节点分成两组,希望选出尽可能多、又不共享边的割。LLM 分析图结构后,识别出可利用的规律:对于节点两两相连的“团”,任意两个穿过它的割都会共享边,因此不能同时选择。图中的红边就展示了这样的冲突。

利用这一结构构造有效不等式,强化全局界,再结合 SAT/LRAT 可验证证明闭合剩余间隙,两个实例最终达到最优:

全局下界提升:

graph40-40-1rand −68.96 → −9 Optimal

graph40-80-1rand −495.45 → −7 Optimal

这展示了结构识别的实际价值:从图中发现规律,将其转化为有效约束,并结合证明把界的改善推进到最优性判定。类似的进展也出现在其他实例中:allcolor58 通过目标值 42 的可行解和同为 42 的下界完成最优判定;nj1 则在MIPLIB没有公开可行解的情况下,得到了经过验证的可行解。

从求解一个问题到积累可复用的 skill

如何将一个问题上的成功经验用于其他问题? 他们从最初112个实例的研究中提炼共性的结构规律,将有效方法整理为两类可复用的技能:primal-skill 和 dual-skill。
Primal-skill 关注怎样构造、修复和改进可行解。例如,先保留已有方案中较好的部分,再集中调整造成冲突的少量变量。Dual-skill 则关注怎样建立更强的松弛、发现有效不等式,并验证全局界。两类skill分别指导大模型从“找更好的方案”和“证明不能更好”两个角度推进研究。

团队在同一组 20 个实例上测试了两类skill,每类skill处理实例的时间上限均为 150 分钟。相比未使用skill的大模型,10 个实例获得了更好的可行解;17 个实例的全局下界得到改善。

将两类skill得到的最佳可行解与全局界结合后,20 个实例中有 18 个最优性差距小于普通大模型,16 个小于求解器基线。这表明,将成功经验整理为可复用的skill,有助于大模型更有效地求解新问题。

大模型能替代求解器吗?

MIP 上的进展,是否意味着大模型已经能够替代成熟求解器?团队选取 Mittelmann 榜单的 40 个线性规划实例,比较LLM 自行寻优、LLM调用求解器寻优,以及求解器直接求解三种方式。

三种寻优方式的区别:受限LLM不能直接将完整模型或其等价形式交给求解器,多数实例LLM会自行编写内点法或 PDHG 算法求解。允许调用求解器时,LLM会自行选择算法与参数,再由求解器处理完整模型。纯求解器COPT则采用默认参数求解。

工作流 求解结果 用时*
受限LLM 16/40数值最优 60+分钟
LLM+求解器 40/40 数值最优 约 6 分钟
求解器COPT 40/40数值最优 8.17 秒

表 1|40 个 LP 实例的结果与用时。60+分钟为LLM整体平均求解时间,约 6 分钟采用的大模型 + 求解器整体平均用时估算;8.17 秒为求解器COPT时间几何均值。

从时间上看,受限的LLM整体用时超过60分钟,LLM+求解器整体求解用时估算约为每个实例6 分钟,而求解器COPT完成求解的平均时间为 8.17 秒。这一对比提醒我们:大模型参与分析和选择方法,也会带来额外时间成本。

所以,目前来看,大模型在个别线性规划实例上有帮助,但整体效果仍不理想,尚不能可靠替代专业求解器。它更有潜力承担的角色,是发现结构、提出方法,再与成熟算法协同工作。

LLM4MIP工作由上海财经大学博士生黄奕程、斯坦福大学博士生高文智,以及斯坦福大学 Madeleine Udell教授、叶荫宇教授(SIMIS)和杉数科技COPT团队的葛冬冬教授共同完成。

欢迎访问 LLM4MIP 项目网站(https://llm4mip.github.io/),查看完整结果、实例分析与代码,下载 primal-skill 和 dual-skill,探索大模型与数学优化结合的更多可能。

项目网站:https://llm4mip.github.io/

责任编辑:王力
您可以:
排行榜
  1. 小鹅通搭建心理咨询行业生态共创社群 促进行业经验互通共享
  2. 金蝶推出全新AI产品小K,开启企业管理智能共生新时代
  3. 对话Gian Paolo:SOLIDWORKS 2026创新密码与AI战略
  4. 智算时代,企业需要怎样的AI基础设施?
  5. 云栖大会上,我邂逅了一个“AI原生ERP”
  6. Eplan Platform 2026:标杆之作,焕新定义
  7. SAP Business Suite 整合 AI、数据和应用,驱动下一代企业转型
  8. ManageEngine卓豪:聚力IT管理革新,驱动企业数智升级
  9. 2025年第十六届德国工业4.0考察正式启航
  10. 泊松CAx+ AI 2025年度产品发布会圆满落幕!以AI洞见未来,用创新启航新程!
编辑推荐
• 厚积薄发:伯恩光学的数智化加速度
• 工信部印发《创新型产业集群建设管理办法》
• GoogleBook发布搭载英特尔Core Ultra系列3处理...
• 从港珠澳大桥到曙光8000,央视《超级工程》首...
• 阿里千问AI平台全面升级模型服务、Agent服务、...
• 阿里云未来一年将在8个国家和地区新增数据中心
• 从成本中心到价值引擎:ServiceMax的四个现场...
• 兆瓦级充电时代,为何亟需重构测试方法?
• 头部企业纷纷选择千问办公,金龙鱼、一汽丰田...
• 千问办公发布Agent硬件QwenNote
• 从专属钉到千问办公,传化集团的AI上岗记
• 千问办公发布企业上下文,让Agent懂企业、懂业...
文章推荐
• AI+CAD全球竞速:中国厂商如何回答这道必答题
• 不起眼的机器人皮肤,如何撑起百亿赛道?
• 从单点验证到规模应用,工业AI的落地卡在哪里?
• WMS不只是管仓库:它如何重塑供应链协同
• QMS数字化:从检验把关到质量预防的跨越
• 小型企业如何应用AI——以东洋重工机(大连)...
• MBD落地三道坎,跨过去才是数字主线
• 中国版“普罗米修斯”,雪浪云如何为制造业打...
• 年产50亿个!一颗小小开关,凭什么做到世界第...
• 从8000跌到800,ERP顾问的天塌了?
• 斯巴鲁矢岛工厂:老工厂的精益新生,多车型同...
• 十年深耕,梅卡曼德何以成为“具身智能眼脑手...

系列微信

数字化企业
观潮工业AI
e-works制信科技
具身智能一线
智能制造网博会
智能制造IM
ERP之家
智能工厂前线
MES百科
PLM之神
供应链指南针
© 2002-2026  武汉制信科技有限公司  版权所有  ICP经营许可证:鄂B2-20030029-1(于2003年首获许可证:鄂B2-20030029)
鄂公网安备:420100003343号 法律声明及隐私权政策     投诉举报电话:027-87592219

关于我们    |    联系我们    |    隐私条款

ICP经营许可证:鄂B2-20080078
(于2003年首获许可证:鄂B2-20030029)
鄂公网安备:420100003343号
© 2002-2026  武汉制信科技有限公司  版权所有
投诉举报电话:027-87592219

扫码查看