数字难度

数字强调设置

数字精度强调参数控制模型优化期间使用的数字注意程度。

• Concert Technology 中的 C++ Name NumericalEmphasis

• Callable Library 中的 C Name CPX_PARAM_NUMERICALEMPHASIS

• Interactive Optimizer 中的 emphasis numerical

在其缺省设置情况下，CPLEX 对于处理其必须执行的计算的数字属性一般谨慎。 在可选设置情况下，CPLEX 极其谨慎。

此强调参数在样式方面与 CPLEX 中的各种容差参数不同。 强调参数的目的是使用户无需分析要尝试哪些容差或其他算法控件。 用户改为告知 CPLEX，已知即将求解的模型易于受到不稳定数字行为的影响，并且让 CPLEX 决定如何最佳进行处理。

可能要在求解速度和数字谨慎之间进行权衡。 如果您的模型按照此参数的可选设置进行求解速度不太快，那么您不应意外，因为每个迭代可能比缺省设置情况下显著更慢。 另一方面，如果数字难度导致优化器不太直接得出最佳解，那么可选设置可能会减少迭代数，从而导致更快求解。 当用户选择强调极端数字谨慎时，求解速度实际被视为不再是主要重点。

数字敏感数据

模型中的数据形式与问题造成的数字难度之间没有绝对关联。 但是，如何向 CPLEX 提供数据方面的某些选项可能具有不利影响。

为个别变量设置较大的上边界（例如，1e9 到 1e12 的邻域中）可能会在预求解期间产生困难。 如果意图使此类大边界表示“没有边界实际生效”，那么最好一开始就不要包含此类边界。

模型中任意位置的大系数同样可能在求解过程中的各个点造成问题。 即使系数的大小更适度，但如果在目标函数或右手边或者在矩阵的任何给定行或列中发现系数变化很大（例如，6 个或以上数量级），那么随着收敛的接近，在预求解（当系数进行替换）或在优化器例程（特别是 barrier 优化器）中可能会产生困难。

难度的相关来源是将分数表示为小数时的四舍五入的形式；在大体上将值计算为 16 位数的计算机上将 1/3 表达为 .33333333 可能会引入明显的“精确”值，该值将被视为已给定，但可能不表示您的意图。 如果类似或相关值在模型中的其他位置的表示略有不同，那么此难度为复合难度。

例如，假设约束为 1/3 x1 + 2/3 x2 = 1。 在完美算术中，它等同于 x1 + 2 x2 = 3。 但是，如果使用小数数据值来表达分数形式，那么无法避免要进行截断。 如果您碰巧将约束的已截断小数形式与某个不同截断形式甚至精确整数数据形式包含在同一模型中，那么容易出现意外结果。 考虑以下问题构造：

最大化
 obj: x1 + x2
Subject To
 c1: 0.333333 x1 + 0.666667 x2  = 1
 c2: x1 + 2 x2  = 3
End

在缺省数字容差情况下，这将提供最优解法 x1=1.0 和 x2=1.0，从而给定目标函数值 2.0。 现在，查看使用略微更准确的数据时发生的情况（就明确意图表示的分数值而言）：

最大化
 obj: x1 + x2
Subject To
 c1: 0.333333333 x1 + 0.666666667 x2  = 1
 c2: x1 + 2 x2  = 3
End

此问题的解法具有 x1=3.0 和 x2=0.0，从而给定最优目标函数值 3.0，该结果与第一个模型的结果有质的区别。 由于后一结果与通过从模型中完全移除约束 c1 将会获取的结果相同，因此这是更满意的结果。 此外，最优基的数字稳定性（如同条件数字所指示，将在下一节中进行讨论）大幅提高。

提高输入数据精度将使模型对于在有限精度计算机上求解问题的舍入错误或其他影响不太敏感，或者在极端情况下将更可能产生与意图模型保持一致的答案。 上述第一个示例是数据截断已从根本上曲解进行求解的问题的实例。 即使约束的精确整数数据形式与小数形式不存在，已截断小数形式也不再准确表示意图含义，如果与模型中的其他约束相结合，可能会给出在向优化器提供特定数据的上下文中“准确”的非意图答案。

请特别注意模型中已使用单精度（32 位）算术计算的数据（在您的程序中，或者通过输入文件从另一个程序传输到您的程序）。 例如，在 C 中，使用类型 float 而不是 double 可能会发生此情况。 此类数据将仅精确到大约 8 个小数位，因此（例如）如果打印数据，那么可能会显示类似于 0.3333333432674408 而不是 0.3333333333333333 的值。 CPLEX 在其计算中使用双精度（64 位），并且已截断的单精度数据具有将传达与用户意图不同的含义的风险。

本部分中所有谨慎背后的基本原理是，数据中包含的信息需要反映实际含义，否则优化器可能得到不稳定的解或遇到算法困难。

使用基础条件数字 kappa 测量问题敏感性

病态指标对于问题数据中的微小更改敏感。 即，在此类问题中，数据中的细小更改会导致报告的问题解法中发生巨大更改。 CPLEX 提供基础数字条件来测量线性系统对问题数据的敏感度。 您可能还将基础条件数字视为精度中可能丢失的位数。

例如，如果处于最优性的基础条件数字为 1e+13，那么单个矩阵系数中第 13 位（从右计数）中的更改可能会显著更改解法。 此外，由于许多计算机在双精度中提供大约 16 位精度，因此在此类解法中仅留三个精确位。 即使获取了答案，可能也只有前三位有效数字可靠。

具体而言，1e+7 的阶数上的条件数字指示几乎没有病态可能性。 1e+8 到 1e+9 的阶数上的条件数字指示病态性机率极小，并且仅当模型同时还缩放不当或具有其他一些数字问题时才可能存在。 1e+10 到 1e+13 的阶数上的条件数字有可能存在病态性。 但是，由于条件数字提供对更改的敏感度的上边界，因此 CPLEX 使用此范围内的条件数字对模型求解通常不费力或非常顺利。 但是，当条件数字的数量级超过 1e+13 时，很有可能发生数字问题。

更普遍而言，针对可行性和最优性容差的给定数量级，将可行性容差除以机器精度将指定可能出现数字难度的条件数字阈值下限。 例如，凭借 CPLEX 的缺省可行性以及最优性容差 1e-6 和机器精度 1e-16，1e+10 是可能根据舍入错误制定算法决策的最小条件数字。 此计算会说明原因，在缺省参数设置情况下，1e+10 的条件数字定义可能出现病态性的阈值下限。

由于基础条件数字较大的矩阵的这一有效精度损失，CPLEX 可能无法选择最优基。 换言之，基础条件数字大使其无法找到解法。

• 在 Interactive Optimizer 中，使用命令 display solution kappa，以便查看常驻基矩阵的基础条件数字。

• 在 Concert Technology 中，使用以下方法：

  IloCplex::getQuality(IloCplex::Kappa) (C++)

  IloCplex.getQuality(IloCplex.QualityType.Kappa) (Java)

  Cplex.GetQuality(Cplex.QualityType.Kappa) (.NET)

• 在 Callable Library 中，使用例程 CPXgetdblquality 访问双精度变量 dvalue 中的条件数字，如下所示：

  
  status = CPXgetdblquality(env, lp, &dvalue, CPX_KAPPA);
  

重复的奇异性

只要 CPLEX 遇到奇异性，它就会从当前基中移除列并继续其工作。 CPLEX 将此类操作报告到日志文件（缺省情况下）和屏幕（如果您是在 Interactive Optimizer 中工作，或者如果用于屏幕切换的消息 CPX_PARAM_SCRIND 设置为 1（一））。 在这些情况下找到最优解法之后，CPLEX 将重新包含已废弃的列，以确保没有更好的解可用。 如果无法获取更好的目标值，那么问题即已求解。 否则，CPLEX 会继续其工作，直至达到最优性。

有时会出现新的奇异性，或者重现相同的奇异性。 CPLEX 遵守其容许的奇异性数量的限制。 参数 SingLim 指定此限制。 缺省情况下，限制为 10。 在遇到许多奇异性之后，CPLEX 将在内存中保存目前为止找到的最佳可因式分解基并停止其求解过程。 您可能希望将此基保存到文件中以供稍后使用。

要将目前为止找到的最佳可因式分解基保存到 Interactive Optimizer 中，请将 write 命令与文件类型 bas 配合使用。 当使用组件库时，请使用方法 cplex.writeBasis 或例程 CPXwriteprob 。

如果 CPLEX 在问题中遇到重复的奇异性，那么可能要尝试对问题进行备用缩放（而不只是增大 CPLEX 奇异性容差）。 缩放说明如何尝试备用缩放。

如果备用缩放没有帮助，那么要尝试的另一个策略是增大 Markowitz 容差。 Markowitz 容差控制允许的枢纽种类。 如果将它设置为接近其最大值 0.99999，那么它可以更慢但数字更稳定的方式进行迭代。 无法保持可行显示如何更改 Markowitz 容差。

如果这些构想都没有帮助，那么可能需要变更问题的模型。 考虑从模型中手动移除不良的变量，并且复审模型以查找表示这些变量的功能的其他方式。

由于简并而停顿

高度简并的线性程序在主单纯形法和对偶单纯形法优化器中易于停顿优化进度。 当主单纯形法优化器发生停顿时，CPLEX 自动扰动变量边界；当对偶单纯形法优化器发生停顿时，CPLEX 扰动目标函数。

在任一情况下，扰动都会创建不同但紧密相关的问题。 在 CPLEX 对扰动问题求解后，它通过将问题数据重置为其原始值来除去扰动。

如果 CPLEX 自动在求解过程早期扰动问题，那么您应考虑使用扰动自行启动求解过程。 （以此方式开始求解将节省首先允许优化停顿再让 CPLEX 自动扰动问题情况下会浪费的时间。）

要自行启动扰动，请将参数 PerInd 设置为 1 而不是其缺省值 0（零）。 扰动常量 EpPer 通常在其缺省值为 1e-6 时适合，但是可以设置为任意值 1e-8 或更大。

如果您注意到问题已多次扰动，那么扰动的问题可能与原始问题差异巨大。 在此类情况下，请考虑减小扰动常量扰动常量（Concert Technology 中的 EpPer 或 Callable Library 中的 CPX_PARAM_EPPER）的值。

无法保持可行

如果问题在阶段 II（即，CPLEX 已获取可行解法之后）中重复变为不可行，那么可能出现数字难度。 它在此类情况下有助于增大 Markowitz 容差。 缺省情况下，参数 EpMrk 的值为 0.01，并且合适值的范围介于 0.0001 和 0.99999 之间。

有时，阶段 I（CPLEX 计算第一个可行解法的时间段）中进度慢是由于数字难度相似，因未取得可行性且可行性丢失而不太明显。 在日志文件中报告的进度中，此情况的症状可能是不可行性的打印和增大。 如果是这样，那么有必要设置更高的 Markowitz 容差，就如同阶段 II 中数字难度的更明显情况一样。