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

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

该软件称为混合整数线性规划 （MILP） 求解器，它将大量优化问题拆分为更小的部分，并使用通用算法来尝试找到最佳解决方案。但是，求解器可能需要数小时甚至数天才能得出解决方案。

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

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

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

他们的数据驱动方法使公司能够使用自己的数据来定制通用的 MILP 求解器，以解决手头的问题。

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

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

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

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

难以解决

MILP 问题的潜在解决方案呈指数级增长。例如，假设一个旅行销售人员想找到最短的路径来访问几个城市，然后返回他们的原籍城市。如果有许多城市可以按任何顺序访问，那么潜在解决方案的数量可能大于宇宙中的原子数量。

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

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

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

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

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

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

缩小解决方案空间

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

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

该模型使用特定于用户优化问题的数据集进行训练，因此它可以学习选择最适合用户特定任务的算法。由于像 FedEx 这样的公司之前已经多次解决路由问题，因此使用从过去经验中收集的真实数据应该比每次都从头开始提供更好的解决方案。

该模型的迭代学习过程，称为上下文强盗，是强化学习的一种形式，包括选择一个潜在的解决方案，获得关于它有多好的反馈，然后再次尝试找到更好的解决方案。

这种数据驱动的方法将 MILP 求解器的速度提高了 30% 到 70%，而精度却没有任何下降。此外，当他们将其应用于更简单的开源求解器和更强大的商业求解器时，加速是相似的。

未来，Wu和她的合作者希望将这种方法应用于更复杂的MILP问题，其中收集标记数据以训练模型可能特别具有挑战性。她说，也许他们可以在较小的数据集上训练模型，然后对其进行调整以解决更大的优化问题。研究人员还有兴趣解释学习到的模型，以更好地理解不同分离器算法的有效性。

这项研究得到了Mathworks、美国国家科学基金会（NSF）、麻省理工学院亚马逊科学中心和麻省理工学院研究支持委员会的部分支持。