虽然圣诞老人可能有一辆神奇的雪橇和九只勇敢的驯鹿帮助他送礼物，但对于像联邦快递这样的公司来说，高效路由假日包裹的优化问题非常复杂，他们通常使用专门的软件来找到解决方案。
这种软件被称为混合整数线性规划（MILP）求解器，它将一个庞大的优化问题分解成较小的部分，并使用通用算法尝试找到最佳解决方案。然而，求解器可能需要几个小时甚至几天才能得出解决方案。
这个过程非常繁琐，公司通常必须在中途停止软件，接受一个不理想但在一定时间内能够生成的最佳解决方案。
麻省理工学院和苏黎世联邦理工学院的研究人员利用机器学习加快了这个过程。
他们确定了MILP求解器中的一个关键中间步骤，该步骤有很多潜在解决方案，需要花费大量时间来解决，从而减慢整个过程。研究人员采用了一种过滤技术来简化这个步骤，然后使用机器学习找到特定类型问题的最佳解决方案。
他们的数据驱动方法使公司能够使用自己的数据来定制通用MILP求解器以解决手头的问题。
这种新技术将MILP求解器的速度提高了30%至70%，而且没有降低准确性。人们可以使用这种方法更快地获得最佳解决方案，或者对于特别复杂的问题，在可行的时间内获得更好的解决方案。
这种方法可以在使用MILP求解器的任何地方使用，例如打车服务、电网运营商、疫苗分发商或任何面临棘手资源分配问题的实体。
“有时，在优化这样的领域中，人们很容易将解决方案看作是纯粹的机器学习或纯粹的经典方法。我坚信我们想要兼顾两者的优点，这是这种混合方法的一个非常强大的实例，”高级作者Cathy Wu说道，她是土木与环境工程学院（CEE）的吉尔伯特·W·温斯洛职业发展助理教授，也是信息与决策系统实验室（LIDS）和数据、系统与社会研究所（IDSS）的成员。
Wu与共同主要作者李思睿（IDSS研究生）和欧阳文斌（CEE研究生），以及苏黎世联邦理工学院的研究生Max Paulus一起撰写了这篇论文。该研究将在神经信息处理系统会议上进行展示。
难以解决
MILP问题有指数级的潜在解决方案。例如，假设一个旅行推销员想找到访问几个城市并返回原始城市的最短路径。如果有很多城市可以以任何顺序访问，潜在解决方案的数量可能大于宇宙中的原子数量。
“这些问题被称为NP难问题，这意味着很难有一个高效的算法来解决它们。当问题足够大时，我们只能希望获得一些次优的性能，”Wu解释道。
MILP求解器采用一系列技术和实用技巧，在可行的时间内实现合理的解决方案。
一个典型的求解器使用分而治之的方法，首先使用一种称为分支的技术将潜在解决方案空间分割成较小的部分。然后，求解器使用一种称为剪枝的技术来收紧这些较小的部分，以便更快地搜索。
剪枝使用一组规则来收紧搜索空间，而不会删除任何可行解。这些规则由几十个算法生成，被称为分离器，用于不同类型的MILP问题。
Wu和她的团队发现，确定使用的分离器算法的理想组合的过程本身就是一个具有指数级解决方案的问题。
“分离器管理是每个求解器的核心部分，但这是问题空间中一个被低估的方面。这项工作的贡献之一是将分离器管理问题视为一个机器学习任务，”她说。
缩小解决方案空间
她和她的合作者设计了一个过滤机制，将这个分离器搜索空间从超过130,000个潜在组合减少到约20个选项。这个过滤机制利用了边际效益递减的原理，即最大的收益将来自一小组算法，添加额外的算法不会带来太多额外的改进。
然后，他们使用一个机器学习模型从这20个剩余选项中选择最佳的算法组合。
该模型是使用特定于用户优化问题的数据集进行训练的，因此它学会选择最适合用户特定任务的算法。由于像联邦快递这样的公司在过去解决过路由问题，使用从过去经验中获得的真实数据应该比每次从头开始更容易获得更好的解决方案。
该模型的迭代学习过程称为上下文强化学习，涉及选择一个潜在解决方案，获得关于其好坏的反馈，然后再次尝试找到更好的解决方案。
这种数据驱动的方法加速了MILP求解器的速度，提高了30%至70%，而且没有降低准确性。此外，当他们将其应用于一个更简单的开源求解器和一个更强大的商业求解器时，加速效果是相似的。
未来，Wu和她的合作者希望将这种方法应用于更复杂的MILP问题，其中收集标记数据以训练模型可能特别具有挑战性。她说，也许他们可以在较小的数据集上训练模型，然后调整它以解决更大的优化问题。研究人员还对解释学习模型以更好地理解不同分离器算法的有效性感兴趣。
这项研究得到了Mathworks、美国国家科学基金会（NSF）、麻省理工学院亚马逊科学中心和麻省理工学院研究支持委员会的部分支持。
