NFL 如何在安排所有常规赛季比赛的同时，避免比赛场地与 Beyoncé 音乐会的时间发生冲突？
医生如何利用单个捐赠的肾脏启动一系列移植，并构建尽可能长的移植链，以挽救更多患者？
航空公司如何在满足乘务员休息要求和机组人员调配的前提下，优化航班乘务员排班，同时有效控制酒店费用与运营成本？
这类问题可通过优化方法求解，优化作为应用数学的一个分支，常采用线性规划（LP）和混合整数规划（MIP）来寻找理想解决方案。然而，求解过程并不容易，因为这些问题通常包含数百万个变量和约束条件，可能导致计算速度显著下降。虽然有时能够快速获得近似解，但要获得高精度的解往往需要更长的计算时间。
NVIDIA cuOpt 是一个开源的 GPU 加速库，用于求解优化问题。新版 cuOpt 引入了一个基于屏障法的全新线性规划求解器，进一步丰富了现有的 cuOpt LP 求解器功能，使工程师、研究人员和开发者能够更快速、更精确地处理大规模线性规划问题。
内部基准测试显示，与主流开源 CPU 求解器相比，cuOpt 屏障在平均性能上可实现超过 8 倍的加速；在大型线性规划问题的公共测试集上，相较于广泛使用的商用 CPU 求解器，平均性能提升超过 2 倍（图 1）。
在并发模式下，当 cuOpt Barrier 与 cuOpt PDLP 结合使用时，其性能在开源求解器中位居首位，并在包含 11 个求解器的公开基准测试中位列第二（检索于 2025 年 10 月 20 日）。 public benchmarks
本文将介绍线性规划的基础知识，阐述 cuOpt 新的 GPU 加速求解方法，并深入分析相关的性能基准测试数据。
什么是线性规划与混合整数规划？
线性规划是一种用于解决优化问题的技术，通过线性约束条件对线性目标函数进行最小化。该方法可应用于多个领域，例如食品与化学品生产中的配比问题、运输与网络流问题，以及金融投资组合的优化等。
线性规划在混合整数规划中发挥着至关重要的作用，混合整数规划是一种用于求解优化问题的技术，其中部分变量需取整数值。作为运筹学领域的重要工具，混合整数规划使从业者能够处理涉及离散决策的复杂问题。该方法具有广泛的应用，包括：
如何求解线性规划问题？
求解线性规划的主要方法有三种：单纯形法、PDLP 和屏障法。
- 单纯形：求解线性规划的经典算法是单纯形法，由 George Dantzig 于 1947 年提出。该方法至今仍被广泛使用，cuOpt 也实现了其中的双单纯形算法。
- PDLP：近期出现了一种利用 GPU 的一阶方法，称为线性规划的原始-对偶混合梯度法（Primal-Dual Hybrid Gradient for Linear Programming，PDLP）。
- 屏障：20 世纪 90 年代，出现了一类新的线性规划算法，称为屏障法或内点法。这类方法在理论上能够在多项式时间内求解线性规划问题。Sanjay Mehrotra 提出的预测-校正算法，已被应用于多种开源和商业求解器中。在实际应用中，无论问题规模大小，这些方法通常需要 20 到 200 次迭代才能收敛，而每次迭代都涉及求解多个稀疏线性方程组。
每种方法在不同问题和不同用例中均表现出优异的性能（表 1）。
| 方法 | 何时使用 |
| Simplex | –适用于中小型线性规划问题 –需要分解以适应内存 –生成高精度的解 –解位于可行区域的顶点 |
PDLP |
–在大型线性规划问题上求解速度快 –无需分解 –可接受较低精度的解 |
| Barrier | –在大型线性规划问题上求解速度快 –需要分解以适应内存 –生成高精度的解 |
cuOpt 如何求解线性规划问题？
使用 cuOpt 时，您无需手动选择求解线性规划的方法。系统默认会同时运行全部三种算法，并以最先完成的结果提供解决方案。
cuOpt 包含一种 PDLP 实现，能够以较低精度快速求解线性规划问题（例如，相对容差为 1e-4 到 1e-6）。然而，许多线性规划的应用场景需要更高精度的解（例如，相对容差为 1e-8 或绝对容差为 1e-6）。
以前，当 cuOpt 用户需要高精度解决方案时，只能依赖单纯形算法。尽管单纯形算法在处理中小规模线性规划问题时表现良好，但在应对大规模线性规划问题时可能面临挑战。
随着新屏障方法的推出，cuOpt 将其高性能 GPU 加速 LP 求解器拓展至需要高精度的大规模线性规划问题。
cuOpt 中 GPU 加速的障碍求解器的工作原理是什么？
cuOpt 屏障方法采用的是研究人员在上世纪 90 年代开发的、经过充分验证的预测-修正器算法，该算法与《Primal-Dual Interior-Point Methods》以及《On Implementing Mehrotra’s Predictor-Corrector Interior-Point Method for Linear Programming》中所述的方法密切相关。
predictor-corrector 方法在每次迭代中都需要求解多个稀疏线性方程组系统。过去，这些问题通常通过 CPU 上的多线程算法来解决。随着 NVIDIA cuDSS（NVIDIA GPU 加速的稀疏直接求解器库）的发布，这一状况发生了改变。cuDSS 在性能上显著优于传统的 CPU 算法，使得 cuOpt 团队能够将 Mehrotra 预测校正算法成功迁移至 GPU 上运行。
cuDSS 0.7 版本包含一些专为 cuOpt 开发的增强功能：
- 更快的符号分解: 在平均情况下，符号分解的速度较优化矩阵测试集提升了 2.5 倍。
- 支持停止 cuDSS 重排序和符号分解阶段的选项: 该功能在与 PDLP 和单纯形法等算法并行运行时尤为实用。
- 确定性模式: cuDSS 0.7 引入了逐位确定性模式，确保 cuOpt 在相同输入条件下输出一致的结果，提升可重复性。
除了 cuDSS，cuOpt 还利用 cuSPARSE 在 GPU 上高效地执行稀疏矩阵乘法和稀疏矩阵-向量乘法。
cuOpt 的屏障方法与开源及商用 CPU 求解器相比表现如何？
新的 cuOpt 屏障方法的性能在一个公开可用的测试集上进行了评估，该测试集包含由亚利桑那州立大学 Hans Mittelmann 维护的 61 个线性规划问题。更多详细信息请参阅优化软件基准测试。
该测试集中的线性规划问题规模较大。图 2 展示了这些问题在变量和约束数量上的分布情况，其中每个点代表一个线性规划问题。该测试集中有十几个问题的变量和约束均超过 100 万个。
实验性设置
将 cuOpt 的屏障方法与多个 CPU 求解器的运行时间进行了对比。所有求解器均在配备 72 个 3.4 GHz CPU 核心、500 GB RAM 和 480 GB VRAM 的 NVIDIA GH200 Grace Hopper 机器（搭载 NVIDIA H200 GPU）上运行。每个求解器均配置为在不启用交叉操作的情况下运行屏障方法，其余设置均保持默认。所有测试问题的求解时间上限为一小时，若求解器未能在规定时间内完成求解，则其运行时间记为一小时。
cuOpt 的屏障方法与开源 CPU 求解器相比表现如何？
在测试集中，cuOpt 解决了 61 个问题中的 55 个，而开源求解器解决了其中的 48 个。与开源求解器相比，cuOpt 在测试集上的平均（几何平均）求解速度提升了 8.81 倍。
图 3 展示了在基于 NVIDIA GH200 的 Mittelmann 测试集的 61 个问题上，cuOpt 的屏障方法相较于开源求解器的加速效果。每个柱形图表示开源求解器的运行时间除以对应问题上 cuOpt 的运行时间。柱形图值大于 1 的（绿色）表示 cuOpt 在该线性规划问题上速度更快；小于 1 的（灰色）表示开源求解器在该问题上速度更快。
与商用 CPU 求解器相比，cuOpt 的屏障方法表现如何？
cuOpt 还通过两家领先的商业求解器进行了测试。实验设置与此前所述相同：所有求解器均采用屏障方法运行，不启用交叉，且使用默认参数设置。
商用 CPU 求解器 A
对于测试集中的 31/ 61 个问题，cuOpt 的求解速度优于商用求解器。在 7 个问题上，cuOpt 的速度达到商用求解器的 5 倍以上，最高可达商用求解器的 17 倍。然而，从整体测试集的几何平均值来看，商用求解器 A 的求解速度比 cuOpt 快 1.5 倍，这可能得益于其采用了更为复杂的 presolve 方法，而 cuOpt 在 presolve 方面的功能尚不完善。此外，商用求解器 A 能够成功求解测试集中的 60/ 61 个问题。
商用 CPU 求解器 B
cuOpt 的表现优于另一款广受关注的商用 CPU 求解器 B。在测试集上，cuOpt 的平均求解速度（几何平均值）达到商用求解器 B 的 2 倍。
该商用求解器解决了测试集中的 58 个问题，共 61 个。
开始使用 NVIDIA cuOpt 的屏障方
cuOpt 开源求解器有助于高效精准地求解大规模线性规划问题。现在，您可以在极具挑战性的大型线性程序上运行单纯形法、PDLP 和屏障法。
要开始使用，请访问 cuOpt Barrier Notebook，了解如何安装 cuOpt 25.10、运行新的屏障方法，并配置预解析和折叠等关键设置。
下载 cuOpt 25.10 并在具有挑战性的线性规划问题上运行，观察其与其他求解器的性能对比情况。
