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