5
一些关于运筹学和机器学习之间协同作用的思考 - 咖喱小蟹
source link: https://www.cnblogs.com/currycrab/p/17405336.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一些关于运筹学和机器学习之间协同作用的思考
几十年来，运筹学（OR）和机器学习（ML）一直作为两个相对独立的研究领域不断发展。数据科学和人工智能领域的专家可能更熟悉机器学习而不是运筹学，尽管每个机器学习实践者都应该至少了解一些优化技术，因为每个机器学习问题本质上都是一个优化问题。在本文中，我将把运筹学和机器学习视为一个整体话题，回顾它们之间的联系，并分享一些近些年这两个领域之间协同作用的最新进展，以充分发挥两个领域的优势。
下面的图示从三个方面说明了运筹学和机器学习之间的联系：运筹学帮助训练机器学习模型，机器学习为运筹学提供输入，机器学习改进运筹学的求解方法。接下来的段落将详细阐述这三个方面。
1. 运筹学帮助训练机器学习模型
OR的核心是优化。OR学者已经开发出了许多技术来找到决策变量的最优值，以最小化或最大化优化问题的目标函数。根据优化问题是否有约束条件，优化问题可以分为有约束优化和无约束优化。根据目标函数和约束条件的形式，优化问题可以大致分为线性优化和非线性优化。
在ML中最常遇到的优化问题可能是非线性优化问题，因为在监督学习的分类任务和回归任务中，损失函数（例如交叉熵或均方误差）通常相对于ML模型的参数呈非线性形式。梯度下降算法通常能够有效地解决这些问题。如果存在正则化项，我们最终会得到一个带有约束的非线性优化问题（例如岭回归、LASSO、支持向量机）。在这种情况下，我们应用拉格朗日乘数并处理原始优化问题的拉格朗日松弛形式，这是一种典型的OR技术，用于解决复杂的约束。例如，在岭回归中，我们尝试解决以下问题：
其中，y是观测到的输出变量的向量，X是观测到的输入变量的矩阵，b是要拟合的系数向量，t是用于控制正则化程度的参数。直接解决这个公式并不容易，因此我们应用拉格朗日乘数λ，将原始公式转换为其拉格朗日松弛形式。
进一步化简后变为：
现在可以应用无约束优化技术来获得b的最优值。
每个ML问题本质上都是一个优化问题，其中损失函数是目标函数，ML模型的参数是决策变量。在这个意义上，OR技术支ML的发展，因为更好的非线性优化问题的解决方法肯定会提高ML模型训练过程的准确性和效率。这种OR和ML之间的相互作用如本文开头给出的图示中的蓝色箭头所示。
2. 机器学习为运筹学提供输入
与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）来解决。
3. 机器学习改进了运筹学的求解方法
正如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之间的协同作用。
（本文由作者译自作者本人在Towards Data Science平台上发表的英文博客 “Some Thoughts on Synergies between Operations Research and Machine Learning" https://link.medium.com/RyIRzTxb0zb。欢迎关注作者的Medium平台账号以阅读有关运筹学与机器学习的最新英文博客。）
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK