jimmyresearch
Home/AI for Science/运筹学中的人工智能 — 学习型优化与求解器
中文↔English

运筹学中的人工智能 — 学习型优化与求解器

运筹学（Operations Research, OR）是数学优化的学科：路由、排程、资源分配，以及广义的 组合优化（combinatorial optimization, CO） 问题族。经典运筹学拥有数十年的成熟机制 ——分支定界、割平面、元启发式、混合整数规划（MIP）求解器。"运筹学中的 AI" 议题探问的是： 机器学习 能否 学习 出能适应问题结构分布的启发式、分支规则或整套求解策略，而不再依赖 人工设计的规则。本模块只关注 AI/ML 角度：学习如何嵌入运筹流水线、哪些方法真正有竞争力、 哪些仍是愿景。更广的框架见 ai-for-science，改进 ML 系统自身的 ML 见 aifs-ml-self。

贯穿全文的核心张力：学习型方法速度快、能在一个分布上摊销成本，但在真实、大规模、不规则的 实例上，经过良好调优的经典求解器仍然难以被超越 [9]。在下结论之前请先读"能打败经典运筹学吗？" 一节。

1. 神经组合优化（NCO）

最早也最受研究的一条路线，把 CO 视为序列生成或策略问题，训练神经网络去 构造 解。

  • 指针网络（Pointer Networks, Vinyals 等, 2015） 引入了一种注意力机制，其输出是指向输入 集合的指针，从而能产生可变长度的组合输出（例如 TSP 的城市排列），让端到端的神经 TSP 求解器 成为可能。
  • 路由问题的注意力模型 —— Kool、van Hoof 与 Welling，"Attention, Learn to Solve Routing Problems!"（ICLR 2019） [1] 用 Transformer 式的编码器/解码器替代循环结构，以 REINFORCE 加贪心回放基线训练。它成为 TSP、带容量车辆路径问题（CVRP）及其变体的经典构造策略基线。
  • POMO —— "Policy Optimization with Multiple Optima"（Kwon 等, NeurIPS 2020） [3] 利用 CO 解的对称性（一条回路有多个等价起点/顺序）。通过对每个实例进行多条轨迹回放并共享基线， POMO 在训练稳定性和最终解质量上都显著优于注意力模型，至今仍是 NCO 的强力骨干。

两类主要范式：

  1. 构造式（自回归）策略 —— 逐个 token 构建解（POMO、注意力模型）。
  2. 改进 / 搜索式启发式 —— 学习 编辑 已有解（2-opt 操作、神经局部搜索），或学习一张 "热图" 标出有前景的边，去引导经典局部搜索如 LKH [9]。

工具已趋于统一：RL4CO（Berto 等, 2023） [2] 是被广泛使用的开源基准/库，标准化了路由 CO 的 环境、基线（注意力模型、POMO 等）与训练流程。

2. 嵌入精确 MIP 求解器内部的 ML

这条路线不是替换求解器，而是学习分支定界（B&B）MIP 求解器的组件，在保留最优性保证的同时 试图缩短墙钟时间。

  • 学习分支 —— Gasse 等（NeurIPS 2019） 把变量选择框定为对（昂贵的）强分支 专家的模仿， 将 MIP 表示为二部"变量–约束"图，并学习一个 图卷积网络（GCNN） 分支策略。这是"学习分支"的 参照性结果，催生了大量后续工作（混合模型、节点选择、割选择）[10]。
  • 神经潜水 + 神经分支 —— Nair 等，"Solving Mixed Integer Programs Using Neural Networks"（DeepMind, 2020） [4]。神经潜水（Neural Diving） 学习一个对整数变量赋值的 生成模型，产生高质量的部分赋值；剩余未赋值变量构成的较小 MIP 由基础求解器（如 SCIP）完成。 神经分支（Neural Branching） 通过模仿学习分支策略。文中报告的增益基于 Google 生产 MIP 数据集。
  • 学习割平面 —— 选择添加哪些割平面也是可学习的决策；同样的图表示思想已被应用于割选择与分离 [10]。

集成目标是标准求解器：开源的 SCIP（因内部可访问，是常见的研究基底）与商业的 Gurobi （闭源；ML 通常通过回调/热启动 包裹 它，而非修改其内部）。

3. 求解器加速与混合方法

最务实的收益来自 ML 引导 经典搜索，而非完全取而代之。

  • 学习型大邻域搜索（LNS）—— "Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs"（DeepMind, 2021） [5]。神经潜水产生初始赋值；一个学习得到的 神经邻域选择 策略（通过模仿一个在算力充足时能选中包含最优下一赋值之邻域的目标策略来训练） 每轮选择要重新优化的变量，由 MIP 求解器搜索该邻域。文中报告在五个真实 MIP 数据集上达到或超过 基线，在其中三个数据集、长运行时间下，平均原始间隙（primal gap）比最佳基线好 2× 到 37.8× [5]。（这些数字应归于该论文的数据集，不要外推泛化。）
  • ML 引导热图 + LKH —— 用学习得到的边评分网络为 TSP 的经典 LKH 局部搜索播种或加偏置，是反复 出现的混合范式 [9]。
  • 热启动与配置 —— 在 OR-Tools / SCIP / Gurobi 之上预测好的初始解、求解器参数或运行哪个 启发式。

共同主线：ML 提供 先验（去哪搜、固定什么），经典求解器提供 正确性与精修。

4. 强化学习用于排程、路由、控制与芯片设计

强化学习已被应用到纯 CO 基准之外的序贯运筹式决策问题：

  • 芯片布图 / 宏单元布局 —— Google "AlphaChip"（Nature 2021；2024 年重新命名） 把宏单元 布局表述为 RL 问题，报告了与人类相当或更优的布局，并称这些布局已在多代 TPU 中流片 [6]。
    • 诚实说明 —— 可复现性争议。 该结果存在 争议。外部及部分内部的批评认为，相对经典布局器 的所谓优势不可复现；Google 反驳说失败的复现跳过了预训练、使用了远少的算力，或未训练到收敛 [6][7]。截至 2025 年底，尚无确认 Nature 论断的独立同行评审复现发表，而 Google 坚称该方法 已在生产中部署 [6]。请把"RL 打败经典芯片布局"这一标题性论断视为 有争议，而非已成定论。
  • 数据中心冷却 / 控制 —— RL 用于设施控制常被引用为运筹味的应用成功案例，但已发表、经审计的 细节比芯片布局案例更稀薄；对具体的节能数字应持谨慎态度。
  • 物流 / 动态路由 —— RL 构造策略（见第 1、5 节）是这里的研究载体。

5. 决策聚焦（端到端）学习

大多数落地运筹是 先预测后优化（predict-then-optimize, PtO）：模型预测不确定参数（需求、 行程时间、价格），求解器据预测进行优化。标准 ML 训练预测器去最小化 预测 误差，这与 决策 质量并不对齐。

决策聚焦学习（DFL） 训练预测器去最小化下游 后悔值（regret）——即其预测所导致决策的成本 [8]。 难点在于对 argmin 求导：

  • OptNet（Amos & Kolter, 2017） 把二次规划嵌为可微层，通过对 KKT 条件隐式求导回传梯度。
  • CVXPY 层 / cvxpylayers（Agrawal 等, 2019） 把上述推广到规范凸规划，使凸求解能位于网络 内部并传递梯度。
  • Smart "Predict, then Optimize"（SPO/SPO+） 及一族代理损失，为真实梯度几乎处处为零的 线性/MILP 目标近似决策损失 [8]。

近期工作（2024–2026）聚焦数据效率与代理损失质量——例如有限数据下的决策聚焦 微调 [8]、MILP 的代理建模，以及降低让 DFL 训练昂贵的逐步求解成本。诚实的告诫：每个训练步通常需要一次或多次求解器 调用，因此 DFL 算力消耗大，主要应用于凸问题或中等规模问题。

6. 大语言模型用于优化

更新的一条路线把大语言模型（见 aifs-ml-self）用作优化器或 建模者。

  • LLM 作为优化器 —— OPRO，"Large Language Models as Optimizers"（DeepMind, 2023/2024） [9-ref]。优化问题以 自然语言 描述；每一步把先前的解及其目标值展示给 LLM，请它提出更好的解。 OPRO 在小规模线性回归和 TSP 实例上做过演示，最具影响力的则是 提示词优化（报告在 GSM8K 上 比人类提示词最多提升约 8%、在 Big-Bench Hard 任务上最多约 50%）[9-ref]。注意：OPRO 是一种元 启发式，在真实 CO 上 打不过 专用求解器——它真正的强项是黑箱/文本型目标。
  • 智能体式运筹建模 / NL 转 MILP —— 用 LLM 把自然语言问题陈述翻译为可供 Gurobi/SCIP/OR-Tools 调用的形式化 MILP/LP 模型（目标、约束）。这降低的是建模门槛（运筹落地的历史瓶颈），而非改进 求解本身。其可靠性——正确的约束抽取、单位、不可行诊断——是开放问题，且此处基准尚不成熟。

7. 方法对照表

方法 问题类别 代表系统 / 论文 成熟度
指针 / 注意力构造 路由（TSP, CVRP） Kool 等注意力模型 [1] 成熟基线
对称感知 RL 构造 路由 CO POMO [3] 成熟基线
学习型局部搜索 / 热图 TSP、大规模 CO GNN 引导 LKH [9] 活跃研究
学习分支（GNN） MIP（精确） Gasse 等 GCNN [10] 渐成熟，见于研究求解器
神经潜水 / 神经分支 MIP（精确） Nair 等（DeepMind）[4] 研究，生产数据集
学习型 LNS MIP（启发式） DeepMind LNS [5] 研究，原始间隙强
可微优化层 先预测后优化 OptNet, cvxpylayers [8] 凸问题已成熟
决策聚焦 / SPO+ 线性/MILP 决策 SPO+, DFL 微调 [8] 活跃研究
LLM 作为优化器 黑箱 / 文本型 OPRO [9-ref] 小众（不适合硬 CO）
LLM NL 转 MILP 建模 任意（建模层） 智能体式运筹流水线 新兴

8. 能打败经典运筹学吗？（诚实一节）

营销答案是"能"；审慎答案是"很少，且只在条件匹配时"。最严谨的近期证据：

  • FrontierCO（2025） [9] 是一个真实/大规模基准，正是因为多数 NCO 进展只在 小而合成 的实例上 度量才被构建。其结论：当经典求解器也在匹配的时间预算下以 快速启发模式 运行时，神经求解器在 竞赛级与工业级实例上仍明显逊于 LKH-3 等经过调优的经典方法 [9]。
  • 泛化是核心弱点。 在某一实例分布（规模、结构）上训练的神经 CO 启发式，在分布外实例上会退化； 只有当训练与测试分布对齐时，它们才能缩小与经典元启发式的差距 [9]。
  • 精确求解器内的 ML 更可信。 学习分支与学习型 LNS 位于 正确求解器内部，因此不会返回错误答案 ——问题只在速度，收益真实但因问题而异 [4][5][10]。
  • AlphaChip 仍是最高调的 有争议 的"RL 打败经典运筹"论断 [6][7]。

合理总结：ML 在运筹学中最清晰、最站得住脚的胜利，是作为经典求解器 内部的加速器与先验（分支、LNS、 热启动），以及作为 建模助手（NL 转 MILP）。端到端神经构造在真实大规模实例上 彻底打败 调优过的 LKH/Concorde/Gurobi，截至 2026 年年中 尚未被令人信服地证明。

9. 开放问题

  • 跨实例规模与结构的泛化。 在 n≈100 上训练、在 n≈10,000 上部署——当前 NCO 方法急剧退化； 规模无关的策略仍是开放问题。
  • 最优性保证。 构造策略不给出界。把学习得到的速度与能产生证书的精确方法耦合（求解器内部路线） 是更友好于保证的路径。
  • 公平的大规模评测。 FrontierCO 等基准揭示了此前多少"SOTA"只在合成数据上成立；该领域需要把匹配 时间预算与工业实例作为默认 [9]。
  • DFL 的训练成本。 可微优化要求训练循环内调用求解器；把 DFL 扩展到大规模 MILP 仍然昂贵 [8]。
  • 部署与信任。 将学习组件集成进商业求解器（闭源 Gurobi）、处理生产中的分布漂移、验证可行性， 都是现实障碍。
  • LLM 建模可靠性。 NL 转 MILP 必须保证模型正确、可行、符合本意，才能被运营流水线信任。

来源

  1. https://arxiv.org/abs/1803.08475 (2026-06-14) —— Kool, van Hoof, Welling, "Attention, Learn to Solve Routing Problems!"（ICLR 2019）。
  2. https://arxiv.org/pdf/2306.17100 (2026-06-14) —— Berto 等, "RL4CO: an Extensive RL for Combinatorial Optimization Benchmark"。
  3. https://proceedings.neurips.cc/paper/2020/hash/d1e946f4e67db4b362ad23818a6fb78a-Abstract.html (2026-06-14) —— POMO 与混合分支背景（NeurIPS 2020）。
  4. https://arxiv.org/abs/2012.13349 (2026-06-14) —— Nair 等（DeepMind）， "Solving Mixed Integer Programs Using Neural Networks"（神经潜水 / 神经分支）。
  5. https://arxiv.org/pdf/2107.10201 (2026-06-14) —— "Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs"（DeepMind, 2021）。
  6. https://en.wikipedia.org/wiki/AlphaChip_(controversy) (2026-06-14) —— AlphaChip / 宏单元布局可复现性争议综述。
  7. https://arxiv.org/html/2411.10053v1 (2026-06-14) —— "That Chip Has Sailed: A Critique of Unfounded Skepticism Around AI for Chip Design"（Google 回应）。
  8. https://arxiv.org/pdf/2501.01874 (2026-06-14) —— "DFF: Decision-Focused Fine-tuning for Smarter Predict-then-Optimize with Limited Data"（DFL / OptNet / cvxpylayers 背景）。
  9. https://arxiv.org/pdf/2505.16952 (2026-06-14) —— "FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization"。
  10. https://arxiv.org/pdf/2511.09209 (2026-06-14) —— 近期 MILP 学习工作，综述 Gasse 等 学习分支 / 割选择脉络。

[9-ref] https://arxiv.org/abs/2309.03409 (2026-06-14) —— Yang 等（DeepMind）， "Large Language Models as Optimizers"（OPRO）。

Related

ai-for-scienceaifs-ml-self
Last compiled: 2026-06-14