基于深度学习的线性规划求解

引言

线性规划（Linear Programming, LP）是优化领域中最基本且应用广泛的数学模型之一。典型的线性规划问题指在满足一组线性约束条件下，最大化或最小化一个线性目标函数。例如，可将约束集合表示为 ，若目标函数  是线性的，那么这个优化问题就是线性规划。自20世纪40年代以来，求解LP的问题得到了深入研究和显著发展。其中，Dantzig提出的单纯形法和之后发展的各种 内点法成为求解线性规划的两类主流算法。单纯形法通过在顶点间迭代地选主元 pivot来改进目标值，最终达到最优顶点；而内点法则在可行域的内部沿某种搜索方向迭代，逐步趋近最优解。这些经典算法在实践中非常高效，使得现代LP求解器能够可靠地处理大量工业级问题。然而，随着问题规模愈发庞大，经典方法在内存消耗和并行化方面面临挑战。例如，单纯形法和内点法都依赖于矩阵分解（如LU或Cholesky分解），当约束和变量数极多时会导致内存占用巨大，并且矩阵分解步骤难以充分利用GPU或分布式计算资源。

尽管如此，线性规划仍是众多实际决策和优化任务的基石，在制造、运输、网络等几乎所有需要“优化”的领域都有应用。特别是在机器学习和人工智能中，线性规划常常扮演底层子模块的角色。例如，在计算机视觉或图像处理中，LP用于图像重构、去噪、表面重建等问题；在图形模型中，用LP求解马尔可夫网络的推断；在生成式模型中，最优传输距离可建模为线性规划；又如Hinton等人提出的胶囊网络需要通过求解一个分配问题（assignment，可表示为线性分配LP）来实现低层实体到高层胶囊的匹配。因此，尽管深度神经网络在近十年主导了AI领域，线性规划模型仍作为约束推理的模块嵌入在许多机器学习流水线中。

传统上，机器学习和优化是分离的两步：先由学习模型预测参数（如LP的系数向量），再将这些预测值送入现有的LP求解器获取决策。但这样的“预测后优化”方式存在不协调之处：学习模型并未考虑最终优化决策的效果，因而所预测的参数未必对最终目标最优。近年兴起的一个重要趋势是将深度学习与优化求解紧密结合，形成“端到端”的决策管道。一方面，深度学习模型可用于直接求解线性规划或为传统算法提供策略指导；另一方面，优化过程本身可以被构造成神经网络的一层，从而允许梯度通过优化问题反传，使模型在训练时直接考虑决策的最终质量。采用深度学习技术来求解LP的动机包括：

• 实时决策和速度需求：在某些应用中需要反复求解规模相似的线性规划（例如实时控制、在线调度等），每次用通用求解器从零开始迭代计算代价较高。如果能用神经网络学习大量历史优化实例的模式，就有可能在新问题出现时瞬时推断出近似最优解，从而显著加速决策过程。例如，Wu和Lisser等研究者提出直接用前馈深度神经网络近似LP映射的方案，期望网络“一步”输出最优解或相关信息。这种“以算代搜”的想法在一定分布范围内显示出可行性。

• 端到端可训练性：将LP问题嵌入神经网络，可以实现可微分的优化层，让模型参数的学习直接针对最终决策的好坏进行调整。这对涉及预测和决策的组合任务特别重要。例如，在供应链管理中，需求预测模型若能感知库存优化（LP模型）的实际成本，将会调整自己的预测以最小化整体成本。这种端到端优化学习能够避免传统方法中“预测误差不等于决策误差”的不一致问题，被证明在某些情形下优于先预测再优化的分离式策略。

• 复杂约束的表达：深度网络层通常难以直接保证输出满足线性约束，而将优化问题作为网络层相当于显式硬编码了约束知识。这样，网络在推理过程中自然地服从这些可微分的约束，从而在结构化输出、可行解预测等任务中表现出色。Amos和Kolter指出，将一个QP/LP求解层嵌入网络，可以捕获传统卷积层或全连层难以表达的复杂依赖关系，并提高模型对硬约束的刻画能力。

深度学习与线性规划融合的方法

深度学习介入线性规划求解主要有几种途径：端到端的可微分优化层、直接的神经网络求解器、基于强化学习的优化算法策略，以及**优化算法的学习（L2O）**等。下面分别介绍各方向的思路和代表性研究。

端到端学习与可微优化层

端到端优化学习旨在将LP求解过程整合进神经网络，使整个决策管道可共同训练。核心是在网络中增加一个“优化层”，其输入是上一层神经元输出的某些参数（如目标系数、约束系数等），该层完成一次线性规划求解，将最优解或相关量作为下一层输入。由于LP解是先验定义的隐式函数，为了通过这种层进行反向传播，研究者应用了隐函数定理和KKT条件的显式微分等技巧。Brandon Amos和Kolter提出的OptNet是该方向的开创性工作之一。OptNet将一个二次规划（Quadratic Program, QP） solver嵌入到网络架构中，并展示了如何对这一层进行精确求导，从而实现端到端训练。他们开发了专门的GPU并行内点法求解这一层的QP，并利用对偶敏感性分析获取梯度，使得反传几乎无需额外开销。OptNet在玩迷你数独等任务中表现出优于普通神经网络的能力，能自动学会问题的硬约束规则。更令人瞩目的是，通过定制的批量内点算法，OptNet可以同时求解大量小规模QP，实现比通用求解器（如Gurobi、CPLEX）快两个数量级的速度。

随后，多项工作扩展了可微分优化层的理论和应用范围。例如，Agrawal等人发布了CVXPyLayers工具，将任何“学科化凸规划（DCP）”问题转换为可嵌入TensorFlow/PyTorch的可微层，使研究者无需手工推导KKT条件即可在网络中加入复杂凸优化模块。又如，孟子航等人受粘菌（Physarum）动态模型的启发，提出了一种高效且可微的线性规划求解层。该方法设计了模拟粘菌流动以寻优的迭代算法，能够在无需初始可行解的情况下快速逼近LP最优，并支持梯度回传。在视频分割和元学习实验中，他们的方法性能可媲美专用的投影梯度算法，在Few-shot元学习任务上甚至优于基于CVXPy-SCS的可微求解层。这些成果表明，通过定制优化算法并融合隐式梯度计算，LP完全可以作为深度模型中的一阶模块，用于约束推理、结构化预测等需要将先验约束融入网络的场景。

另一类端到端方法关注预测-优化问题中梯度的获取，被称为Decision Focused Learning或Predict-and-Optimize框架。代表性工作包括Elmachtoub和Grigas提出的SPO损失（Smart “Predict then Optimize”）以及Wilder等人的QPTL方法（Quadratic Programming Task Loss）等。SPO方法直接以优化问题最终的决策成本作为学习的目标，通过定义一种近似梯度（亚梯度）来训练预测模型，从而避免了优化非光滑函数的困难。Wilder等人则将原本非二次可微的LP目标稍作平滑，添加了一个二次正则项把线性规划变为二次规划（QP），然后利用OptNet的框架计算梯度。Mandi等人认为这种加二次项的方法不够“原生”，他们改用LP求解器中广泛使用的对数障碍（log-barrier）来构造可微的近似，并基于LP的同质自对偶形式推导梯度。他们的实验表明，该 内点可微化方法在性能上不逊于QPTL和SPO等现有最佳方案，部分情况下还有提升。总的来说，端到端的预测+优化学习通过各种技巧成功地将梯度从优化结果传播回预测阶段，实现了从数据直接学习最优决策的目标。

神经网络直接求解器

另一种思路是训练一个专门的神经网络来直接近似线性规划的解映射，即输入问题描述，输出最优解或相关特征。这类似于用深度学习方法替代传统的求解算法。由于线性规划解空间的复杂性，直接回归最优解向量相当困难（解可以是连续值）。因此，大部分研究集中在预测LP解的某些结构信息或辅助决策上。例如，Natdanai Kafakthong等人提出了LPNet模型，通过卷积神经网络来预测LP最优解对应的基（basic variables 基础解）或活跃约束集合。他们将LP的约束矩阵预处理为统一尺寸的矩阵形式，输入卷积层提取“行-列”特征，再经全连接网络输出每个约束成为最优绑定约束（binding constraint）的概率。实验证明LPNet在很多情况下能够准确识别最优基的组成：对随机生成的测试集以及经典Netlib基准集，LPNet对单个最优绑定约束的预测准确率达99%，并且有80%的测试LP，其全部最优绑定约束都被LPNet正确检出。更重要的是，由于神经网络推理非常快，在这些数据上LPNet求解用时低于CPLEX等商业求解器的优化时间。这表明，在分布固定且结构相似的问题批次中，深度学习有潜力以极低延迟提供接近最优的解或解结构，从而加速求解过程。

除了LPNet，还有一些早期神经网络求解思路值得一提。早在20世纪80年代，研究者就尝试用Hopfield网络等模拟物理系统的方法来求解优化问题。Hopfield和Tank在1986年提出可以将线性规划映射为一组电路方程，让电路收敛到最优解对应的稳定状态。虽然这些模拟退火或连续动力系统方法在精度和可靠性上未能超越数值优化算法，但它们奠定了“用连续网络求解组合优化”的思想基础。近年来，随着图神经网络（GNN）的发展，一些工作利用GNN直接对特定类型的优化问题进行近似求解或决策推荐。例如，对于网络流、匹配、装箱等可以表示成图结构的线性规划问题，GNN模型可以学习问题实例的图特征并输出可行解或启发式指导。然而，这类工作多数针对NP难的组合优化（如整数线性规划）问题，在纯线性规划上，由于有多项式时间精确算法，完全替代求解器的需求不如在NP难问题上强烈。因此，神经网络直接求解LP目前多用于辅助传统算法（例如提供初始解、指导变量选取）或者在特定场景下寻求加速，而尚未成为通用的独立求解手段。

强化学习辅助求解

深度强化学习（RL）为优化问题引入了一种不同于监督学习的思路：不直接学习解映射，而是学习在求解过程中如何选择操作以加速达到最优。在线性规划领域，RL主要被用于改进既有算法的决策策略。例如，在单纯形法中，每次迭代需要选择入基和出基变量（pivot变量），不同的选取规则会影响算法的迭代次数。传统上有Dantzig规则、最陡梯度规则等人工设计的策略。近期有研究使用强化学习自适应地选择枢轴规则，期望找到比人工启发式更高效的策略。Zhao等人提出了“RL-Simplex”方法，将单纯形法的可选枢轴决策建模为一个马尔可夫决策过程，由RL智能体学习选择。他们以不同规模的旅行商问题（TSP）的LP松弛为训练环境，让深度Q网络学会在不同迭代阶段选哪个变量入基。结果显示，RL-Simplex能显著减少单纯形迭代次数，在这些特定问题上总迭代步数远低于传统规则。更令人惊讶的是，经过良好训练的RL策略在TSP测试集上的表现超越了业界最优求解器（如Gurobi）的内建策略，以更少迭代实现了同样的最优解。

类似的方法也被应用于混合整数规划（MILP）的分支定界算法中，例如利用RL或模仿学习来选择分支变量或剪枝节点，从而加速求解。虽然MILP超出了纯线性规划的范围，但这些工作体现了一个共同点：学习算法策略而非直接学习解。对于LP问题，由于本身可多项式时间求解，强化学习更主要用于加速求解器在特殊分布上的性能，或在资源受限场景中实现折中。例如，在实时优化中，可训练一个RL代理根据问题特征选择求解方法或调整容差参数，以期在精度和速度间取得最优平衡。此外，RL还可用于启发式算法设计，如结合深度网络改进局部搜索的扰动策略（一些研究将这种用深度学习改进优化过程的范式称为“DeepOpt”机制）。总体而言，强化学习为传统确定性优化算法注入了经验学习能力，在特定任务上展现出降低计算代价的潜力。

优化算法的学习 (L2O)

“学习优化”（Learning to Optimize, L2O）指利用深度学习来自动构建或加速优化算法，属于元优化范畴。与上一节中RL直接决策算法步骤略有不同，L2O更强调以神经网络参数化优化迭代过程本身，并通过训练使其在一类问题上收敛更快或效果更佳。一个经典例子是Andrychowicz等人提出的用LSTM来模拟梯度下降优化器，对神经网络训练进行加速（这属于连续优化的L2O）。在线性规划或一般的凸优化中，L2O可以体现在学习迭代求解器的部分计算。例如，Interior Point Method (IPM)每步需要解一系列线性方程组，Gao等人提出利用LSTM神经网络来近似求解这些方程，从而减少每步的计算开销。他们将该LSTM嵌入内点法流程，构成一种学习辅助的内点算法（IPM-LSTM）。在求解二次规划等测试中，这种方法相比标准内点法**减少了60%的迭代步数，整体求解时间缩短约70%**。换言之，通过学习线性方程求解的隐含结构，神经网络替代了通用线性代数方法，极大加速了优化过程。

另一种L2O思路是展开（unroll）传统优化算法的固定迭代，并将其视为一个具有可调参数的深度模型。例如，可以将几步单纯形法或坐标下降法展开成一个有限深度的网络，将某些启发式规则替换为可学习的参数，然后利用监督数据或RL训练这个“优化网络”。这样做的初衷是用训练好的网络实现比原算法更快的收敛。虽然对于线性规划这方面工作尚不多见，但在相关领域已有成功案例（例如将启发式的迭代加法算法展开并学习，用于求解子模块优化问题）。总体而言，L2O提供了一种数据驱动的方法来发现优化算法的新变体，有望用于开发面向特定领域的高效LP求解器。

值得注意的是，L2O和强化学习等方法通常并非要完全取代经典算法，而是可以融合 进现有框架以提升性能。例如，可训练网络产生单纯形或内点法的初始可行解（warm start）以减少迭代，或者学习一个模型在不同问题实例间迁移求解经验。随着研究深入，我们有望看到更多这类将优化算法本身作为学习对象的工作，使得“解优化问题”也能从历史数据中受益。

参考文献：

Vlastelica, Marin, et al. "Differentiation of Blackbox Combinatorial Solvers." AAAI, 2020, pp. 3243–3250. (Enforcing Hard Linear Constraints in Deep Models)

Amos, Brandon, and J. Zico Kolter. "OptNet: Differentiable Optimization as a Layer in Neural Networks." ICML, 2017, pp. 136–145.

Meng, Zihang, et al. "Physarum Powered Differentiable Linear Programming Layers and Applications." AAAI, vol. 35, no. 10, 2021, pp. 8939–8949.

Zhao, Guantao, et al. "RL Simplex: Bringing Computational Efficiency in Linear Programming via Reinforcement Learning." ICLR (under review), 2024.

Kotary, James, et al. "End-to-End Constrained Optimization Learning: A Survey." IJCAI, Survey Track, 2021, pp. 4475–4482.

Mandi, Jayanta, and Tias Guns. "Interior Point Solving for LP-based Prediction+Optimisation." NeurIPS, 2020.

Lu, Haihao, and David Applegate. "Scaling up Linear Programming with PDLP." Google AI Blog, 20 Sept. 2024.

Gao, Xi, et al. "IPM-LSTM: A Learning-Based Interior Point Method for Solving Nonlinear Programs." NeurIPS, 2024 (to appear).

Amos, Brandon, and J. Zico Kolter. OptNet: Differentiable Optimization As A Layer in Neural Networks. arXiv preprint arXiv:1703.00443, 2017.

Agrawal, Akshay, et al. "Differentiable Convex Optimization Layers." NeurIPS (Tutorial), 2019. (LocusLab Blog)

Kafakthong, Natdanai, and Krung Sinapiromsaran. "Primal-Optimal-Binding LPNet: Deep Learning Architecture to Predict Optimal Binding Constraints of a Linear Programming Problem." IJACSA, vol. 14, no. 5, 2023, pp. 1055–1062.

Ibid. (LPNet article DOI:10.14569/IJACSA.2023.01405109, Abstract Section).