“几十年来，运筹学 (OR) 和机器学习 (ML) 已经发展成为两个相对独立的研究领域。数据科学和人工智能领域的专家可能对 ML 比对运筹学更熟悉，尽管每个 ML 从业者都应该至少了解一些优化技术，因为每个机器学习问题本质上都是一个优化问题。在本文中，作者将把运筹学和 ML 视为一个整体主题，从三个角度探讨了 OR 和 ML 之间的联系。OR 和 ML 本质上是紧密相连的，随着两个领域的发展，它们将齐头并进。未来 OR 和 ML 之间可能还会出现其他更有趣、更令人兴奋的协同作用。”

在人工智能的浩瀚星空中，运筹学（Operations Research, 简称OR）与机器学习（Machine Learning, 简称ML）犹如两颗璀璨星辰，虽各自闪耀，却也存在着微妙的联系。对于数据科学及人工智能领域的探索者来说，机器学习或许更为人所熟知，但不可忽视的是，每一个机器学习任务的背后，都隐藏着优化的身影。优化技术，作为机器学习不可或缺的一部分，其重要性不容忽视。本文将运筹学与机器学习视为一个整体进行探讨，旨在挖掘两者之间的内在联系，并分享两者协同作用的最新动态。通过整合运

作为预览，下图从三个角度说明了 OR 和 ML 之间的联系：OR 有助于训练 ML 模型，ML 为 OR 提供输入，ML 改进 OR 的解决方法。下文将分别阐述这三个角度。

说明 OR 和 ML 之间交互的图表（图片来自作者）

运筹学的精髓在于寻求最佳解决方案，即优化。运筹学领域的专家们已研发出多种技术手段，旨在确定决策变量的最优取值，从而实现目标函数的最小化或最大化。依据优化问题是否受条件限制，我们可将其划分为有约束优化和无约束优化两大类别。进一步地，根据目标函数及约束条件的数学表达形式，优化问题又可大致分为线性优化与非线性优化两类。在机器学习的广阔天地中，非线性优化问题尤为常见。这主要是因为，在监督学习场景下，无论是分类任务（如交叉熵损失）还是回归任务（如均方误差损失），其损失函数往往与机器学习模型的参数呈现出非线性关系。而基于梯度下降的算法，往往是解决这类问题的得力助手。当引入正则化项时，问题便转化为受约束的非线性优化，如岭回归、LASSO回归和支持向量机等。此时，我们通常会借助拉格朗日乘数法，对原始约束优化问题进行拉格朗日松弛处理，这是运筹学中一种经典的解决复杂约束问题的方法。以岭回归为例，其目标便是求解一个特定的优化问题：

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

进一步简化为：

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

机器学习的核心本质，归根结底，是围绕着优化问题展开的，其中，损失函数扮演着目标函数的角色，而模型参数则成为了我们需要精心调整的决策变量。从这个角度来看，运筹学（OR）为机器学习（ML）注入了强大的动力，因为更加高效且精准的非线性优化解决方案，无疑能够大幅度提升机器学习模型在训练过程中的准确性和效率。这一相互作用，在文章开篇的图表中，通过一条清晰的蓝色箭头得到了直观的展示。然而，在实际应用的场景中，运筹学所依赖的主流模型，却与机器学习中的应用存在着显著的差异。线性规划（LP）和混合整数线性规划（MILP）模型，成为了运筹学领域中的佼佼者。LP问题，是一个以线性目标函数和线性约束条件为特征的优化问题，其决策变量可以在连续的范围内取值。而MILP问题，虽然同样拥有线性的目标函数和约束条件，但其部分决策变量却必须取整数值。LP和MILP模型，凭借其广泛的应用领域，如供应链管理中的设施选址、生产计划制定以及车辆路线规划等，展现出了强大的生命力。在这些场景中，线性成本函数通常作为目标函数，同时伴随着大量的约束条件，如满足客户需求、确保资源利用最小化等。值得注意的是，运筹学的专家们往往更倾向于将实际问题转化为线性优化问题来处理，因为非线性优化问题的复杂性，尤其是在约束条件众多的情况下，会大大增加求解的难度。在这样的运筹学应用中，机器学习模型，特别是监督学习模型，通常扮演着为LP和MILP模型提供已知参数估计值的角色。以供应链管理为例，我们可以构建一个监督学习模型来预测客户的需求，这些预测结果随后会被用作LP和MILP模型中约束条件或目标函数的已知参数。这些客户需求的预测，可以是确定性的点估计，也可以是考虑概率分布的随机估计，这与确定性优化或随机优化问题的性质紧密相关。由于机器学习模型的质量直接影响着运筹学应用中输入参数的准确性，因此，机器学习模型的表现，也在一定程度上决定了运筹学应用的成功与否。这一相互作用，在文章开篇的图表中，通过一条醒目的绿色箭头得到了生动的诠释。

下面我将带您了解一个设施位置选择问题的简单示例，以说明 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和Xpress）以及非商业求解器（如SCIP）来解决。

运筹学（OR）与机器学习（ML）之间的相互作用日益显著。正如运筹学对机器学习模型的训练流程产生深远影响一样，机器学习也在运筹学模型的求解过程中发挥着越来越重要的作用。近年来，越来越多的研究工作聚焦于如何利用机器学习技术来增强求解混合整数规划（MIP）问题的分支定界算法的效率。分支定界算法，作为求解MIP问题的得力助手，其工作原理与树搜索算法有着异曲同工之妙。当面对一个最小化问题时，该算法首先会在根节点处对原始问题进行线性规划（LP）松弛处理，即暂时忽略MIP问题中的整数性约束，从而得到一个更为宽松的LP问题。随后，算法会从根节点出发，开辟出两条新的分支，并针对每个分支添加一个基于最接近整数值的附加约束。这一过程，犹如在知识的大树上不断延伸出新的枝桠，探索着问题的每一个角落。

下图简要说明了分支定界算法中开发分支的过程。

用一个简单的图表来说明分支定界算法（图片来自作者）

以上图为例，如果在根节点（即 LP0）处原始问题的 LP 松弛的最优解中 x_1 = 2.5，并且我们选择在该节点上进行分支，我们将 x_1 ≤ 2 添加到第一个分支，将 x_1 ≥ 3 添加到第二个分支。然后，在每个新节点，我们用添加的约束求解由此产生的 LP 松弛问题。上述过程称为分支，我们在开发树时重复此过程。如果具有完整性约束的决策变量都是整数，我们将到达叶节点。

请注意，在搜索树时，每当我们在节点处遇到整数解时，我们都会更新当前最佳解决方案。当前最佳解决方案提供了 MIP 最佳目标值的上限。如果在特定节点处，LP 松弛的最佳目标值大于当前最佳解决方案，则无需进一步探索此节点，并且此节点将被修剪。这种修剪过程通过消除到达树的每个叶节点的必要性，大大有助于减少树搜索工作量。

然而，即使经过剪枝，实际问题通常都很大，以至于执行简单版本的分支定界算法仍然相当耗时。研究人员提出了几种改进分支定界算法的想法。一种想法是在某些节点对 LP 松弛添加切割。切割是可以排除非整数解但不是整数解的约束。通过在某些节点添加切割，我们可以缩小 LP 松弛的可行域，从而更容易通过求解 LP 松弛找到整数解。遵循这种想法的算法称为分支定界算法。

添加切分是个好主意，但有时找到好的切分本身就是一项不简单的任务。在这种情况下，将启发式方法应用于某些节点对于找到整数解非常有用。常用的启发式方法之一是松弛诱导邻域搜索 (RINS)。该启发式方法着眼于当前最佳整数解和当前节点的 LP 松弛的分数解，固定两个解一致的决策变量的值，并将其余决策变量作为子 MIP 求解。

请注意，每个整数解都为原始 MIP 的最优解提供了上限（假设解决最小化问题），而活动节点（未修剪的节点）处 LP 松弛的每个分数解都是原始 MIP 的最优解的下限。因此，添加切割有助于改善下限，而应用启发式方法有助于改善上限，这两者共同帮助分支定界算法更快地收敛。

回到OR与ML的交互，使用ML改进分支定界算法的核心思想是将ML应用于：

学会分支——在节点上根据哪个决策变量进行分支

学习剪辑——如何找到有效的剪辑来添加到 LP 松弛中

学会寻找好的启发式方法——帮助找到更好的整数解

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

通常需要大量的 MIP 来训练 ML 模型，然后 ML 模型将其学到的内容应用于感兴趣的特定 MIP 实例。

利用 ML 帮助解决 MIP 是一个新兴的研究课题，大部分工作都集中在理论研究上，而不是在商业或非商业 MIP 求解器中的实际实现。下面列出了一些有用的资源，可帮助您从这个角度了解更多内容。

ML4CO是一个与该主题相关的竞赛，致力于鼓励使用 ML 解决组合优化（与整数规划大致相同的概念）问题。本次竞赛向参赛者提出了三个任务：

原始任务、对偶任务和配置任务，每个任务侧重于分支定界算法的不同方面。

假设解决最小化 MIP，原始任务要求参赛者使用 ML 在根节点处找到更好的整数解，以降低最优解的上限。

对偶任务要求参赛者专注于如何使用 ML 做出分支决策，以提高最优解的下限。

最后，在配置任务中，参赛者尝试使用 ML 为非商业求解器 SCIP 找到更好的参数化来解决 MIP。

论文《组合优化的机器学习：方法论综述》对利用机器学习技术解决组合优化问题的尝试进行了综述。作者总结了使用机器学习解决组合优化问题的两个动机：

在寻找最优解时，从专家给出的演示中学习做出决策（例如，分支定界算法中的分支决策）；

从经验中学习，这可以导致探索新的决策策略（例如，分支决策），以推进最先进的技术。

第一个概念与模仿学习相吻合，第二个概念与强化学习相吻合。

本文开头给出的图中的红色箭头从这个角度说明了 OR 和 ML 之间的相互作用。

另一篇值得关注的论文是 Google DeepMind 团队撰写的“使用神经网络解决混合整数规划”，其中创建了 MIP 的图形表示，并使用神经网络为整数变量生成部分分配（神经分支）并学习做出分支决策（神经分支）。在使分支定界算法更加高效方面取得了有希望的结果。

4、总结

本文从三个角度探讨了 OR 和 ML 之间的联系。前两个维度在实践应用中已趋于成熟，而第三个维度虽然尚需更多科研探索以实现其实用性和可扩展性，但其蕴含的巨大潜力不容忽视。本质上，运筹学与机器学习相辅相成，共同进步，随着两个领域的持续演进，它们之间的协同作用愈发显著。我们有理由相信，在未来，运筹学与机器学习之间还将涌现出更多新奇且激动人心的交互方式。

Ray：为机器学习和大模型而生的分布式计算框架

全网最详解读专家混合大模型（MoE）：专家和路由器

大模型数据工程实战：ArenaLearning通过模拟LLM竞技场来构建大规模数据飞