AI加速复杂场景下的问题解决

一种新的数据驱动方法可以为棘手的优化问题（例如全局包裹路由或电网运营）提供更好的解决方案。

Adam Zewe | 麻省理工学院新闻

2023 年 12 月 5 日

麻省理工学院和苏黎世联邦理工学院的研究人员开发了一种新的数据驱动机器学习技术，可应用于许多复杂的物流挑战，例如包裹路由、疫苗分发和电网管理。

虽然圣诞老人可能有一个神奇的雪橇和九只勇敢的驯鹿来帮助他运送礼物，但对于像联邦快递这样的公司来说，有效路由假期包裹的优化问题非常复杂，以至于他们经常使用专门的软件来寻找解决方案。

该软件称为混合整数线性规划 (MILP) 求解器，可将大规模优化问题分解为较小的部分，并使用通用算法来尝试找到最佳解决方案。然而，求解器可能需要数小时甚至数天的时间才能得出解决方案。

这个过程非常繁重，以至于公司经常必须中途停止软件，接受一个不理想但可以在规定时间内生成的最佳解决方案。

麻省理工学院和苏黎世联邦理工学院的研究人员利用机器学习来加快速度。

他们确定了 MILP 求解器中的一个关键中间步骤，该步骤具有如此多的潜在解决方案，需要花费大量时间才能解开，从而减慢了整个过程。研究人员采用过滤技术来简化这一步骤，然后使用机器学习来找到特定类型问题的最佳解决方案。

他们的数据驱动方法使公司能够使用自己的数据来针对当前的问题定制通用 MILP 求解器。

这项新技术将 MILP 求解器的速度提高了 30% 到 70%，且精度没有任何下降。人们可以使用这种方法更快地获得最佳解决方案，或者对于特别复杂的问题，在易于处理的时间内获得更好的解决方案。

这种方法可以用在任何使用 MILP 求解器的地方，例如乘车服务、电网运营商、疫苗接种分销商或任何面临棘手资源分配问题的实体。

“有时，在优化这样的领域，人们通常认为解决方案要么是纯粹的机器学习，要么是纯粹的经典。我坚信，我们希望两全其美，这是这种混合方法的一个非常有力的实例，”资深作者、土木与环境工程吉尔伯特·W·温斯洛职业发展助理教授 Cathy Wu 说道。 CEE），以及信息与决策系统实验室（LIDS）和数据、系统与社会研究所（IDSS）的成员。

Wu 与 IDSS 研究生 Sirui Li 和 CEE 研究生 Wenbin Ouyang 共同撰写了这篇论文；还有苏黎世联邦理工学院的研究生马克斯·保卢斯（Max Paulus）。该研究将在神经信息处理系统会议上发表。

很难解决

MILP 问题有指数数量的潜在解决方案。例如，假设一位旅行推销员想要找到访问多个城市然后返回其出发城市的最短路径。如果有许多城市可以按任意顺序访问，则潜在解决方案的数量可能比宇宙中原子的数量还要多。

“这些问题被称为 NP 难问题，这意味着不太可能有有效的算法来解决它们。当问题足够大时，我们只能希望实现一些次优的性能，”吴解释道。

MILP 求解器采用一系列技术和实用技巧，可以在易于处理的时间内获得合理的解决方案。

典型的求解器使用分而治之的方法，首先使用称为分支的技术将潜在解决方案的空间分成更小的部分。然后，求解器采用一种称为切割的技术来收紧这些较小的部分，以便更快地搜索它们。

切割使用一组规则来收紧搜索空间，而不删除任何可行的解决方案。这些规则由几十种算法（称为分隔符）生成，这些算法是为不同类型的 MILP 问题创建的。

吴和她的团队发现，确定要使用的分隔符算法的理想组合的过程本身就是一个具有指数级解决方案的问题。

“分离器管理是每个求解器的核心部分，但这是问题空间中一个未被充分认识的方面。这项工作的贡献之一是将分离器管理问题首先确定为一项机器学习任务，”她说。

缩小解决方案空间

她和她的合作者设计了一种过滤机制，将分隔符搜索空间从超过 130,000 个潜在组合减少到大约 20 个选项。这种过滤机制利用了边际收益递减原理，即最大的收益来自于一小组算法，并且添加额外的算法不会带来太多额外的改进。

然后，他们使用机器学习模型从剩下的 20 个选项中挑选出最佳的算法组合。