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