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