AI如何给传统算法“开挂”

工业界和日常商业运转中，大厂们每天要面对无数个极其复杂的“选择题”：物流公司如何规划成百上千辆货车的行驶路线？电商仓库如何把不同体积的商品最省空间地装进纸箱？工厂的流水线应该如何排班才能让效率最高？

这些在现实中让人抓狂的调度问题，有一个统一的名字——混合整数规划（Mixed Integer Programming，简称 MIP）。这类问题折磨人的地方在于决策变量必须是整数。比如，你可以派出2辆货车或3辆货车，但绝对派不出“2.5辆货车”；你可以打包10个包裹，但不能打包“10.3个包裹”。这类问题在理论上被证明是 NP-hard 的，这意味着随着问题规模的扩大，计算量会呈指数级爆炸。

长期以来，人类科学家设计了各种精妙的启发式算法来求解这类问题，但它们高度依赖良好的人工初始解，且极其消耗算力。为了拯救这个“算力黑洞”，这篇论文提出：让机器学习（ML）化身军师，通过学习历史数据的规律来帮传统数学算法“抄近道”。了解 AI 如何介入之前，先看传统数学家是如何“死磕”混合整数线性规划（MILP）的。标准的 MILP 数学模型通常长这样：

解开这个模型最经典的算法叫分支定界法（Branch-and-Bound，简称 B&B）。核心思想是“分而治之”和“及时止损”。算法先不考虑整数限制（这叫线性规划松弛，LP Relaxation）得出一个好算的底线方案。如果算出来的变量不是整数（比如变量等于2.5），算法就会像画树状图一样，把问题无情地拆成两个分支：一边是“变量 ≤ 2”，另一边是“变量 ≥ 3”。

这是一个典型的分支定界树。顶端的根节点是不考虑整数限制的松弛问题，算出来的最优解包含小数。系统顺着箭头向下分叉（Branching），把可行域切成一个个小碎块。在搜索过程中，如果发现某个分叉的“最好可能性”（下界）比已经找到的某一个可行方案（上界）还要差，AI 或者算法就会果断把这个分叉给“切掉”（Prune/Fathomed），不再做无用功。最终，在第4个节点找到了完美的整数最优解。虽然分支定界法一定能找到完美答案，硬伤在于成千上万次的分叉决策，如果选错了一个变量进行分叉，整个搜索树的体积就会瞬间翻倍，让计算陷入泥潭。 既然人类科学家没办法摸透每一次分叉的规律，AI又是如何帮忙的？AI在这里扮演的是“领路人”的角色，在不破坏数学严谨性的前提下，教传统算法怎么走得更快：

智能变量挑选（BVS）：在传统方法中，有一种叫“强分支（Strong Branching）”的规则挑选变量极准，但每一次挑选都要做一堆复杂的矩阵运算。用模仿学习（Imitation Learning），让神经网络学习强分支规则的决策结果，从而用极低的计算成本复制出大师级的变量挑选眼光。

将变量关系看作“社交网络”：AI 怎么看懂复杂的数学公式？论文介绍了一种方法-把 MIP 变成图神经网络（GCN）能读懂的二部图（Bipartite Graph）或三部图（Tripartite Graph）。

如图2所示，复杂的变量（Variables）和约束条件（Constraints）被分别放在了天平的两侧，错综复杂的系数连接变成了一条条边。图3进一步加入了目标函数（Objective）。通过这种转换，AI 就可以像分析社交网络里的“网红大 V”一样，揪出对全局影响最大的关键变量，优先对其进行分叉！

除了分叉，传统算法还擅长通过增加“割平面”（如图 4 所示的线性约束）来切掉不包含整数解的废弃区域，从而缩小搜索树。AI 利用强化学习（RL）在与环境的反复博弈中，能够高效挑选出最锋利、最能一刀切中要害的割平面。

在商业大促或紧急调度的真实场景中，大厂等不及传统算法花费几个小时去算一个完美答案。它们需要的是“在数秒钟之内给出一个能拿去用、且质量高”的及格方案。这类场景下，近似求解的启发式算法就成了主力军。

大邻域搜索（LNS）：这种方法就像是在一片广阔的迷宫里找出口，先定一个初始位置，然后每次在周围一大片区域（邻域）里搜寻有没有更好的方案。但邻域太大会导致计算爆炸，太小又容易坐井观天。AI 通过强化学习，能够根据当前搜索的进度，自动、动态地调整“搜索探测器的半径大小”，甚至直接预测变量的初始值，带算法直接跳过大片迷宫。

可行性泵（Feasibility Pump）：这是一种反复在“满足约束条件”和“满足整数要求”之间横跳、投影并相互拉近的算法（见图 5）。传统方法在横跳时容易陷入死循环，而“聪明版可行性泵（Smart FP）”引入了强化学习智能体，教算法在陷入僵局时如何做出扰动，快速跳出死循环，直奔可行解。

作者简介：严骏驰，上海交通大学人工智能学院教授（兼计算机科学与工程系），主要从事机器学习及其与组合优化、图学习、计算机视觉等方向的交叉研究。曾在 IBM Research（IBM研究院）任研究员/首席研究员多年，长期致力于将学习方法与组合优化、图匹配等问题相结合。

ORCID：0000-0001-9639-7679

DOI：10.1016/j.neucom.2022.11.024

已收藏 0

点赞 0