跳转到内容

GLPK/Scaling

来自维基教科书,开放的书籍,开放的世界

缩放是指对问题约束矩阵应用线性变换以改善其数值特性的过程。

在 GLPSOL 的情况下,可以使用命令行选项来控制要部署的缩放类型,或者在从程序直接调用 GLPK 时通过 GLPK API 来控制。


GLPK 中的缩放由以下函数管理glp_scale_prob. 此页面上的原始信息来自该函数及其子函数的源代码注释scale_prob, gm_scaling, gm_iterate,和eq_scaling. 关于这一点,GLPK 代码库有很好的注释,是一个查找详细信息的好地方。

GLPK 中的缩放可能包括以下步骤,以及相应的 按位或运算 缩放选项

  • 如果问题已良好缩放,则跳过 GLP_SF_SKIP
  • 执行迭代几何缩放 GLP_SF_GM
  • 执行均衡缩放 GLP_SF_EQ
  • 将缩放因子舍入到最接近的二的幂 GLP_SF_2N

默认缩放设置GLP_SF_AUTO按顺序执行前三个步骤GLP_SF_SKIP, GLP_SF_GM, GLP_SF_EQ. 使用 MIP 预求解器还可以添加GLP_SF_2N.

缩放通常也提供 终端输出. 更多详细信息可以在 官方文档 或直接从源代码中找到。

检查问题是否已良好缩放

[编辑 | 编辑源代码]

如果满足以下条件,则认为问题已良好缩放,

其中 是第 i 行和第 j 列的约束矩阵系数。

迭代几何缩放

[编辑 | 编辑源代码]

几何缩放可以平等地应用于行和列。几何缩放会对每行或每列进行缩放,使得最小值和最大值的绝对值的乘积为 1。

迭代几何缩放会交替地对行和列应用几何缩放,直到达到最大迭代次数或缩放没有显着改进。缩放质量 r 由以下公式定义

GLPK 默认使用 r 至少 10% 的逐轮改进,并在终止之前进行最多 15 轮。

均衡缩放

[编辑 | 编辑源代码]

均衡缩放可以应用于行和列。均衡缩放会将每行或每列除以该行或列中存在的最大绝对值。

均衡缩放使每行和每列的 无穷范数 等于 1。

最接近的二的幂缩放

[编辑 | 编辑源代码]

缩放可能会产生舍入误差。如果所有缩放因子都是二的幂,则可以避免这些误差,因为这只会影响 IEEE 754 表示的双精度数的指数部分,而不会影响尾数部分。

该算法首先遍历所有行,然后遍历所有列。将每行/列的缩放因子舍入到最接近的二的幂

重新计算

[编辑 | 编辑源代码]

如果您添加或删除行或列,或修改现有行/列,则需要调用glp_scale_prob再次。在修改的情况下,此调用还可能更改一些行和/或列缩放因子,从而更改基矩阵。这将使您在glp_prob对象中存储的单纯形求解器的当前基分解失效,因为分解是针对缩放矩阵而不是原始矩阵计算的。然而,这只是一个效率问题(而不是准确性或稳定性问题),因为如果基分解失效,单纯形求解器只会简单地计算一个新的基矩阵。

华夏公益教科书