一些关于运筹学和机器学习之间协同作用的思考

几十年来，运筹学（OR）和机器学习（ML）一直作为两个相对独立的研究领域不断发展。数据科学和人工智能领域的专家可能更熟悉机器学习而不是运筹学，尽管每个机器学习实践者都应该至少了解一些优化技术，因为每个机器学习问题本质上都是一个优化问题。在本文中，我将把运筹学和机器学习视为一个整体话题，回顾它们之间的联系，并分享一些近些年这两个领域之间协同作用的最新进展，以充分发挥两个领域的优势。

 

下面的图示从三个方面说明了运筹学和机器学习之间的联系：运筹学帮助训练机器学习模型，机器学习为运筹学提供输入，机器学习改进运筹学的求解方法。接下来的段落将详细阐述这三个方面。

 

 

 

OR的核心是优化。OR学者已经开发出了许多技术来找到决策变量的最优值，以最小化或最大化优化问题的目标函数。根据优化问题是否有约束条件，优化问题可以分为有约束优化和无约束优化。根据目标函数和约束条件的形式，优化问题可以大致分为线性优化和非线性优化。

 

在ML中最常遇到的优化问题可能是非线性优化问题，因为在监督学习的分类任务和回归任务中，损失函数（例如交叉熵或均方误差）通常相对于ML模型的参数呈非线性形式。梯度下降算法通常能够有效地解决这些问题。如果存在正则化项，我们最终会得到一个带有约束的非线性优化问题（例如岭回归、LASSO、支持向量机）。在这种情况下，我们应用拉格朗日乘数并处理原始优化问题的拉格朗日松弛形式，这是一种典型的OR技术，用于解决复杂的约束。例如，在岭回归中，我们尝试解决以下问题：

 

 

其中，y是观测到的输出变量的向量，X是观测到的输入变量的矩阵，b是要拟合的系数向量，t是用于控制正则化程度的参数。直接解决这个公式并不容易，因此我们应用拉格朗日乘数λ，将原始公式转换为其拉格朗日松弛形式。

 

 

 

进一步化简后变为：

 

 

现在可以应用无约束优化技术来获得b的最优值。

 

每个ML问题本质上都是一个优化问题，其中损失函数是目标函数，ML模型的参数是决策变量。在这个意义上，OR技术支ML的发展，因为更好的非线性优化问题的解决方法肯定会提高ML模型训练过程的准确性和效率。这种OR和ML之间的相互作用如本文开头给出的图示中的蓝色箭头所示。

 

 

与OR技术在ML中的应用不同，现实世界应用中占主导地位的OR模型是线性规划（LP）和混合整数线性规划（MILP）模型。LP问题是一个具有线性目标函数和线性约束的优化问题，其中决策变量可以取连续值。而虽然MILP问题也具有线性目标函数和线性约束，但其中的一些决策变量必须取整数值。LP和MILP在各种行业中有广泛的应用。例如，在供应链管理中，MILP通常用于设施选址、生产计划和车辆路径规划等问题。这些问题通常具有线性成本函数作为目标函数，并有许多约束条件，如满足客户需求、确保资源的最小利用率等等。事实上，OR从业者往往不会将现实世界的问题表述为非线性优化问题，因为这些问题求解起来会更加复杂，特别是当存在许多约束条件时。

 

在这样的OR应用中，主要是监督学习模型提供LP和MILP模型中已知参数的估计值。例如，在供应链管理领域，我们可以建立一个监督学习模型来预测客户需求，这将成为LP和MILP模型中约束条件或目标函数中的已知参数。客户需求的预测可以是点估计或概率估计，取决于优化问题是确定性还是随机性。由于ML模型会影响OR应用的输入参数的准确性，因此ML模型的质量也会影响OR应用的成功。这种OR和ML之间的交互作用由图中的绿色箭头表示。

 

下面我将通过一个简单的设施选址问题的例子展示一个ML模型的输出是如何被应用为MILP的输入的。假设一家公司希望在I个候选站点中选择建立分销中心，向J个客户发送其成品。每个站点i都有不同的存储成品的最大容量，最多为m_i个产品单位。建立每个站点i需要一定的固定建设费用f_i。从站点i运输每个产品单位到客户j都会产生运输成本c_ij。每个客户j都有需求d_j，所有客户的需求必须得到满足。令二进制变量y_i表示我们是否在站点i建立设施，x_ij表示要从站点i运送到客户j的产品数量。优化问题的目标是最小化总成本，该问题可以表示为以下形式：

 

 

 

 

 

在这里，y_i和x_ij是表示我们需要做出决策的决策变量，在我们尝试解决问题之前是未知的。其他变量是已知参数，在我们尝试解决问题之前必须知道。ML在这个问题中的作用是可以提供需求预测，即d_j的估计值。需求预测属于时间序列预测的范畴，因为需求数据通常以时间序列的形式出现。可以应用各种算法，从传统的时间序列模型（例如ARIMA、指数平滑等）到ML模型（例如LightGBM、神经网络）来得到d_j的准确估计。ML模型也可以用于获得其他参数的估计，例如c_ij、f_i等，但以我个人经验，我在需求预测方面看到的应用更多。以上优化问题可以用任何商业求解器（如CPLEX、Gurobi和FICO Xpress）和非商业求解器（如SCIP）来解决。

 

 

 

正如OR影响了ML的训练过程，ML也可以在OR模型的求解过程中发挥作用。近年来，人们越来越关注使用ML来提高解决混合整数规划（MIP）的分支定界算法的效率。分支定界是一种广泛用于解决MIP的算法，类似于树搜索算法。假设我们正在解决一个最小化问题。在根节点处，该算法先求解原问题的LP松弛问题（在MIP中放弃整数约束可将原问题转换为其LP松弛问题）。然后，该算法从根节点开发出两个分支，产生两个新节点，并使用最接近的整数向每个分支添加一个附加约束。下图简要说明了分支定界算法中开发分支的过程。

 

 

 

 

以上图为例，如果在原问题的线性规划松弛问题（即LP0）的最优解中，x_1 = 2.5，我们选择对它进行分支，那么我们将在第一分支中添加 x_1 ≤ 2 的限制，第二分支中添加 x_1 ≥ 3 的限制。然后，在每个新节点中，我们求解带有新添加的约束的LP松弛问题。以上过程称为分支，我们在开发树的过程中重复此过程。在某一节点上，如果带有整数约束的决策变量都是整数，则我们到达了一个叶节点。

 

请注意，在搜索树时，每当我们在一个节点上遇到整数解时，我们会更新当前最优解。当前最优解提供了MIP最优目标值的上界。如果在某个节点上，LP松弛问题的最优目标值大于当前最优解，则没有必要进一步探索此节点，该节点将被剪枝。这样的剪枝过程通过消除到达树的每个叶节点的必要性，显著减少了树搜索的工作量。

 

然而，即使进行了剪枝，实际问题通常也非常庞大，执行基本的分支定界算法仍然非常耗时。学者们提出了几种改进分支定界算法的思路。其中一个想法是在某些节点上为LP松弛问题添加割平面。这些割平面可以排除非整数解，但不能排除整数解。通过在某些节点为线性松弛问题添加割平面，我们可以缩小线性松弛问题的可行域，使通过求解线性松弛问题找到整数解更加容易。该算法被称为分支切割法。

 

添加割平面是一个好的想法，但有时找到好的割平面本身就是一项不容易的任务。在这种情况下，对某些节点应用启发式算法是寻找整数解非常有用的方法。其中一个常用的启发式算法是松弛导向邻域搜索（relaxation induced neighborhood search）。这种启发式算法查看当前最佳整数解和当前节点的LP松弛问题的非整数解，固定这两个解中取值一致的决策变量的值，再将其余决策变量作为子MIP求解。

 

在分支界定法中，每个整数解都为原始MIP提供了最优解的一个上界（假设我们解决一个最小化问题），而在活性节点上（未被剪枝的节点）的线性松弛问题的每个非整数解都是原始MIP最优解的一个下界。因此，添加割平面有助于改善最优解的下界，应用启发式方法有助于改善最优解的上界，这两者共同帮助分支定界算法更快地收敛。

 

回到OR和ML之间的相互作用，利用ML改进分支定界法的核心思想是将ML应用于：

1. 学习分支——即在节点上选择哪个决策变量进行分支，

2. 学习如何切割——即如何找到有效的约束条件添加到LP松弛问题中，

3. 学习如何找到好的启发式方法 - 帮助找到更好的整数解，

4. 学习如何配置优化求解器的参数——如何配置求解器（例如，终止准则，应用启发式算法的频率），以便更快地解决问题。

 

我们通常需要一个大型的MIP问题实例集来训练ML模型，然后该ML模型将把其学到的应用于特定MIP问题实例。

 

利用ML来帮助求解MIP问题是一个新兴的研究领域，大部分工作集中在理论研究方面，而不是在商业或非商业MIP求解器中进行实际实现。可通过以下一些有用的资源，进一步了解这一领域。

 

1. ML4CO是一个与此领域相关的比赛，旨在鼓励参赛者使用ML解决组合优化（与整数规划概念类似）问题。该比赛设置了三个任务：原始任务、对偶任务和配置任务，每个任务专注于分支定界算法的不同方面。假设我们求解一个最小化MIP问题，原始任务要求参与者使用ML在根节点找到更好的整数解，以降低最优解的上界。对偶任务要求参与者关注如何使用ML进行分支决策，以增加最优解的下界。最后，在配置任务中，参赛者尝试使用ML为非商业求解器SCIP找到更好的参数设置，以解决MIP问题。

 

2. “Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon” 这篇论文对利用ML技术来解决组合优化问题的尝试进行了概述。作者总结了使用ML解决组合优化问题的两个动机：从专家给出的示范中学习，在搜索最优解的过程当中以做出决策（例如分支决策）；从经验中学习，从而探索如何制定新的决策（例如分支决策）以推进最新技术。第一个概念符合模仿学习，而第二个概念更符合强化学习。本文开头给出的图示中的红色箭头展现了OR和ML之间这方面的相互作用。

 

3. 另一篇值得注意的论文是由Google DeepMind团队撰写的 “Solving Mixed Integer Programs Using Neural Networks”。该论文创建了一个MIP的图表示，并使用神经网络生成整数变量的部分赋值和学习如何做出分支决策。该论文在提高分支定界法的效率方面取得了有希望的结果。

 

在本文中，我从三个方面介绍了OR和ML之间的联系。虽然前两个方面已经有了成熟的技术在实际实现中，但是最后一个方面尽管非常有前途，仍然需要更多的研究努力来进行实际的可扩展的实现。OR和ML在本质上是密切相关的，并且随着两个领域的发展，两者将携手前进。也许将来还会有其他更有趣和令人兴奋的OR和ML之间的协同作用。