高级 LP 解析

尽管 LP 技术已经成熟，但某些用例需要更高级的技术。例如，许多不同的 LP 算法和实现都可用，每种算法和实现都有优缺点。此外，数值不稳定可能会导致求解器速度变慢或无法求解某些模型。

本指南介绍了相关概念并提供了示例，可帮助您利用 LP 求解器实现最高性能和可靠性。

概念

本部分介绍了 LP 求解器高级使用的关键概念。我们假设读者熟悉 LP 中的双重性概念。

LP 算法系列

以下几类 LP 算法可通过 OR-Tools 访问。

  1. 单工算法是第一个实用的 LP 算法，并且仍然受欢迎。该算法沿着可行区域的顶点（角点）前进，以迭代方式改进目标函数的值，直到找到最佳解决方案。单工算法有两种类型：

    1. 主单元会沿着原始可行区域的顶点获取步数。此变体在解决一系列具有不同目标函数的 LP 问题（即原始可行区域是固定的）方面尤其有效。
    2. 双单工沿着双可行区域的顶点执行步数。此变体在解决双可行区域固定的一系列 LP 问题方面尤其有效，例如，当只有变量的边界发生变化时。因此，双单复用在 MIP 求解器中得到了广泛应用。

  2. 屏障或内点 方法是针对 LP 的第二个实用算法系列。 屏障式方法可将高效（多项式时间）收敛的理论保证与实际的可靠性能相结合。当单工算法性能不佳时，它们可以作为单纯算法的补充；例如，一些求解器提供同时运行单工和屏障的求解方法，从最先完成的算法返回解决方案。

  3. 一阶方法是一系列算法，专门使用梯度信息（即一阶导数）来指导迭代。梯度下降就是一个众所周知的例子。这些方法在非线性优化和机器学习中很常用。对于 LP，一阶方法可以扩展到比单工和屏障更大的问题，并且可能对内存的要求要小得多。另一方面，它们对数值问题更敏感，并且可能难以获得高度准确的解决方案。

下表列出了 OR-Tools 中提供的 LP 求解器，并指明在每个求解器中实现了三个算法系列中的哪一个。

求解器 单面 Barrier 第一订单
夹扣 X X
每位潜在客户费用 X X
GlopG X
GLPK X X
古罗比L X X
PDLPG X
XpressL X X

G 表示求解器是由 Google 开发的。L 表示求解器需要相应的第三方开发者颁发的许可。

如需查看有关应使用哪些求解器和算法的建议，请参阅建议。

“解决问题”究竟意味着什么？

为了充分利用 LP 求解器，请务必了解当求解器声称已找到 LP 问题的解决方案时的含义。本部分将介绍回答此问题所需的基本信息，尤其是给定解的数值不精确性和非唯一性。

公差

LP 求解器几乎总是使用浮点运算，因此其解决方案会受到数值不精确性的约束。考虑到这一点，并通过避免研究已经足够好的解决方案来提高性能，当这些解决方案满足特定“公差”的条件时，求解器会接受这些解决方案并声称解决了问题。

考虑线性规划问题

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

及其对应的对数问题

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

这对问题拥有 $ x_1 = 1、x_2 = 0 $ 和双解 $ y = -2 $ 的唯一最优原解。求解器会将哪些解视为最佳解？为了回答这个问题，我们定义了以下数量：

  • 二元性差距是原始目标值与双目标值之间的差值，在本例中为 $ |(-2x_1 - x_2) - y| $。
  • 基本不可行性是指违反基本约束条件，在本例中为 $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $。
  • 双重不可行性是指违反双重约束条件，在本例中为 $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $。

如果二元性差距、基本不可行性和双重不可行性均小于给定公差，则求解器声明解为最优解决方案。1

值得注意的是，由于各种求解器和算法的自然和特殊原因，对公差的应用情况会有所不同。例如，单工算法中的对二差距仅由数值不精确性驱动，而原数和对数不可行性即使是在精确算术中也存在。一些方法会直接执行有界限约束 $ x_1 \ge 0, x_2 \ge 0, $ 和 $ y \le 0 $，而另一些方法则区别对待违反线性约束条件和违反线性约束条件（如 $x_1 + x_2 \le 1$）的 $ x_1 约束条件。对于一些求解器，如果它们的求解能力均为绝对和求解的绝对有效性，则它们的

以公差效果为例，假设对上述原对对对应用 $ \epsilon = \frac{1}{2} $ 的绝对公差。求解 $ x_1 = 1.5、x_2 = 0、y = -3 $ 的二元性差距为零，并且不可行性均小于或等于 $ \epsilon $，因此求解器可能会声明此解为“最佳”。但是，它的目标值 (-3) 与真正的最佳目标值 (-2) 相差 1。$ \epsilon $ 的典型默认值介于 $10^{-6}$ 和 $10^{-8}$ 之间，这使得此类极端示例罕见但并非不可能。

解决方案类型

LP 问题可能有多个最佳解决方案，在考虑公差时更是如此。我们将简要讨论由上述三个不同 LP 算法系列返回的解决方案的属性。

单工算法始终会返回可行区域的顶点或角点。在某些情况下，首选这些解决方案，因为它们往往较为稀疏。

屏障线和一阶方法通常不返回顶点。（理论还提供了一些超出本指南范围的特征。）

由于历史原因以及顶点解具有吸引人的特性，因此默认情况下，求解器通常会应用交叉过程，从屏障算法找到的解中移至最佳顶点。目前不为通过一阶方法找到的解决方案提供交叉功能。

建议

我们针对 LP 求解器的高级用法提出以下建议。

问题数据的扩缩

由于数值问题，求解器可能会在模型上遇到收敛缓慢或失败的情况。导致此类问题的原因有很多；我们在这里举一个例子。

非常小或非常大的数字常量在 LP 模型中出现很常见。扩展上述示例，如果 \(x_1\) 和 \(x_2\) 表示分配给“提供方 1”或“提供方 2”的客户比例，如果我们希望最大限度地通过为这些客户提供服务获得收益，可以编写以下目标函数：

$$ \min -c_1x_1 - c_2x_2 $$

其中：

  • $ c_1 $ 是将客户分配给提供商 1 的好处
  • $ c_2 $ 是将客户分配给提供商 2 的好处

满足以下约束条件的对数被视为使用绝对公差 $ \epsilon $ 时可行：

  • $ y \le -c_1 + \epsilon $，
  • $ y \le -c_2 + \epsilon $。

如果 $ c_1 $ 和 $ c_2 $ 的效益单位是很小的小数值，并且这些小数值接近与 $ \epsilon $ 的尺度相同，则对数可行性条件会变得相当弱，因此，可能将非常不理想的原语声明为最优。

另一方面，如果收益单位是“微美元”（1 000 000 微美元 = 1 美元），那么会产生非常大的绝对值需要在解决方案中实现非常高的精度，考虑到浮点数的限制，可能非常高。如果问题是这样表达的，则求解器可能无法收敛。在构建合理放置问题的过程中，高级建模者应考虑问题数据的扩缩方式是否与其求解器的公差一致。

除了避免数值失败问题，还可以调整公差以获得更好的性能。单纯法和屏障方法对公差不太敏感，但如果观察到进展在求解结束时停止，则有时较大的容忍度可能会受益。另一方面，一阶方法通常更敏感。一阶方法的用户可因上下文允许而放宽容忍度，从更快的解决方案中受益。

如需了解 Glop 的公差，请参阅 GlopParameters 中的 primal_feasibility_tolerance、dual_feasibility_tolerance 和 solution_feasibility_tolerance。请注意，该算法中会使用 primal_feasibility_tolerance 和 dual_feasibility_tolerance，而在求解后会检查 solution_feasibility_tolerance 以标记数值问题。对于 PDLP，请参阅 eps_optimal_absolute 和 eps_optimal_relative。

如需进一步了解这些类型的问题，请参阅 Gurobi 的数字问题准则。虽然这些准则是面向 Gurobi 用户编写的，但其中许多准则普遍适用。

求解器和算法的选择

我们首先举例说明了选择求解器和算法会产生多大的影响，然后介绍了选择 LP 求解器的指南。

实际中的可变性

我们比较了 Hans Mittelmann 对 Hans Mittelmann 用于进行基准化 LP 求解器的选定实例的求解时间，来说明不同 LP 算法和求解器的性能差异。这些实例经明确选择以显示相对性能的极端，并且不一定代表典型行为。

将 Glop 的原始单复用方法和双单工方法与 Gurobi 的屏障法（有及不交错，可找出顶点解）和 PDLP（高精度和低精确度）一阶方法进行比较。下表中的报告可计算以秒为单位的时间，上限为 20 分钟（1200 秒）。

实例 Glop
原初单工		 Glop
双单工函数		 Gurobi 屏障
与跨界车		 Gurobi 屏障
（无跨界车）		 PDLP
高精确度		 PDLP
低精确度
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3 >1200 252.8 144.6 3.2 1.1 0.9
savsched1 >1200 >1200 156.0 土耳其里拉 46.4 32.4
wide15 >1200 土耳其里拉 >1200 >1200 916.4 56.3
建筑能耗 178.4 267.5 12.8 12.3 >1200 157.2
S250R10 12.1 520.6 15.2 16.4 >1200 >1200
求解器版本 OR-工具 9.3 OR-工具 9.3 Gurobi 9.0 Gurobi 9.0 OR-工具 9.3 OR-工具 9.3
solver_specific_parameters （默认） use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

根据这些结果，我们得出结论。

  • 在单个实例上，算法和求解器的相对性能可能相差几个数量级。
  • 没有任何一种算法和求解器能够一律优于其他算法和求解器。
  • 交叉（默认启用）会增加求解时间，有时还会大幅增加求解时间。
  • PDLP 可以解决低精度问题，有时解决高精度问题的速度会快 10 倍。

LP 求解器选择简要指南

鉴于没有一种 LP 算法或求解器是最佳的，我们建议您按以下步骤操作，以发现最适合您的使用场景的 LP 算法或求解器。从第一步开始，如果性能不足，则继续执行下一步。

  1. 试试 Glop。原因：Glop 是 Google 内部实现原初和双单面方法的内部实现。Glop 是 Google 生产工作负载的开源版本，值得信赖。
    • 如果默认配置（原单工）效果不佳，请尝试使用 use_dual_simplex: true 切换到双单面模式。
  2. 如果有许可，请尝试使用商用求解器（CPLEX、Gurobi 或 Xpress）。尝试单工和屏障方法。原因：这些求解器是行业标准且经过高度优化。此外，屏障方法也是对 Glop 提供的单面算法的补充。
    • 如果使用分界线，则在不需要顶点解时停用“交叉”。
  3. 试试 PDLP。针对您的应用调整收敛容忍度。原因：PDLP 专为解决单工和屏障方法达到内存限制或速度过慢等最严重的问题而设计。当近似但快速的解决方案首选精确但缓慢的解决方案时，PDLP 的效果最佳。
  4. 如果您做到了，那么您现在已是高级 LP 用户！如需更多帮助，请参阅 OR-Tools 支持选项。

  1. 实际情况往往比这更复杂。求解器通常会针对问题的转换/简化版本（称为“已解决”问题）检查这些条件。在某些情况下，解决已解决问题的方法可能离解决输入问题的方法很远。这种情况可能会导致异常状态，例如 CPLEX 的 OptimalInfeas 或 Glop 的 IMPRECISE。↩