高效地应对复杂的优化问题，从全球包裹路由到电力网管理，一直是一个持久的挑战。传统方法，特别是混合整数线性规划（MILP）求解器，一直是破解复杂问题的首选工具。然而，它们的缺点在于计算强度，往往导致次优解或长时间的求解。为了解决这些限制，麻省理工学院和苏黎世联邦理工学院的研究人员开创了一种数据驱动的机器学习技术，承诺彻底改变我们解决复杂物流挑战的方式。
在物流领域，优化是关键，挑战是令人生畏的。尽管圣诞老人可能有他神奇的雪橇和驯鹿，但联邦快递等公司需要处理迷宫般的节假日包裹路线。公司使用的软件骨干是MILP求解器，它采用分而治之的方法来解决庞大的优化问题。然而，这些问题的复杂性往往导致求解时间长达数小时甚至数天。由于时间限制，公司经常被迫中断求解器的中间过程，接受亚优解。
研究团队确定了导致求解时间延长的一个关键中间步骤，即分隔管理。分隔管理是每个求解器的核心方面，但往往被忽视。分隔管理负责识别理想的分隔算法组合，这是一个具有指数数量潜在解决方案的问题。研究人员认识到这一点，试图用数据驱动的方法重新激活MILP求解器。
现有的MILP求解器采用通用算法和技术来导航广阔的解决方案空间。然而，麻省理工学院和苏黎世联邦理工学院的团队引入了一个过滤机制，以简化分隔搜索空间。他们将庞大的13万个潜在组合减少到了约20个可管理的选项。这个过滤机制依赖于递减边际效益的原理，即最大的效益来自一小组算法。
创新之处在于将机器学习融入MILP求解器框架。研究人员利用一个在问题特定数据集上训练的机器学习模型，从缩小的选项中选择最佳算法组合。与具有预定义配置的传统求解器不同，这种数据驱动的方法允许公司通过利用自己的数据来针对特定问题定制通用的MILP求解器。例如，像联邦快递这样经常解决路由问题的公司可以使用过去的实际数据来优化和增强他们的解决方案。
这个机器学习模型基于上下文情境强化学习的形式。这个迭代学习过程包括选择一个潜在解决方案，获得有关其有效性的反馈，并在随后的迭代中对其进行优化。结果是将MILP求解器的求解时间大幅加快，从30%到令人瞩目的70%，而不影响准确性。
总之，麻省理工学院和苏黎世联邦理工学院之间的合作努力在优化领域取得了重大突破。通过将经典的MILP求解器与机器学习相结合，研究团队为解决复杂的物流挑战开辟了新的途径。加快求解时间并保持准确性为MILP求解器带来了实际优势，使其更适用于实际场景。这项研究对优化领域做出了贡献，并为在解决复杂实际问题中广泛整合机器学习铺平了道路。