为什么缩放和几何体相关

本节提供了一个简单的示例，说明缩放问题如何减慢问题的解决速度，并在极端情况下导致意外的答案。考虑这个问题：

$ 美元(P) \马克斯\{残雪:Ax = b, l \ leq x \ leq u \} 美元$

,让

是对角矩阵，其中 $美元D_{ii}>0，\，\forall i$$ ．理论上,解决 $（P）$

应该等于解决了相关的问题吗 美元美元(P_D)

$ 美元(P_D) \马克斯\ {cD x”:广告x ' = b, D ^ {1} l \ leq x ' \ leq D ^ {1} u \} 美元$

然而，在实践中，这两种模型的行为非常不同。为了演示这一点，我们使用了一个简单的脚本rescale.py随机重新缩放模型列的。让我们考虑重新调整对问题的影响。pilotnov.mps.bz2.解决原始问题会产生以下输出：

使用许可证文件/opt/gurobi910/gurobi.lic从文件pilotnov.MPS.bz2读取MPS格式模型读取时间=0.01秒pilotnov:975行，2172列，13057非零gurobi优化器版本9.1.0构建v9.1.0rc0（linux64）线程数：6个物理内核，12个逻辑处理器，最多使用12个线程优化975行的模型，2172列和13057非零模型指纹：0xE6E7CF84系数统计：矩阵范围[1E-06，1E+07 ]目标范围[2E-03，1E+00 ]界限范围[5E-06，8E+4] RHS范围[1E-05，4E+04 ]警告：模型包含大矩阵系数范围考虑重新建模或设置数值聚焦参数以避免数值问题。预解算删除254行和513列预解算时间：0.01s预解算：721行，1659列，11455非零迭代目标原始信息双重信息时间0-3.2008682e+05 1.274630e+05 0.000000e+00 0s解包后额外单纯形迭代：1 1085-4.4972762e+03 0.000000e+00 0.000000e+00 0s在1085次迭代中求解，0.05秒最佳目标-4.497276188e+03 Kappa:1.841766e+07

注意日志中关于矩阵系数范围的消息(在本例中显示的范围是[1e-06, 1e+07])。

如果我们跑rescale.py - f pilotnov.mps。bz2 - s 1 e3获取（随机将列向上或向下缩放多达 $10^3$ )，我们获得：

使用许可证文件/opt/gurobi910/gurobi.lic从文件pilotnov.MPS.bz2读取MPS格式模型读取时间=0.01秒pilotnov:975行，2172列，13057非零gurobi优化器版本9.1.0构建v9.1.0rc0（linux64）线程数：6个物理内核，12个逻辑处理器，最多使用12个线程优化975行的模型，2172列和13057非零模型指纹：0x79ED9354系数统计：矩阵范围[6E-09，1E+10 ]目标范围[5E-06，9E+02 ]界限范围[5E-09，5E+4] RHS范围[1E-05，4E+04 ]警告：模型包含大矩阵系数范围考虑重构模型或设置数值聚焦参数以避免数值问题。预解算删除了100行和255列预解算时间：0.00s预解算：875行，1917列，11899非零迭代目标原始信息双重信息时间0-6.2390277e+32 7.095340e+31 6.239028e+02 0s解包后额外单纯形迭代：21141-4.4972762e+03 0.000000e+00 0.000000e+00 0s在1141次迭代中求解，0.05秒最佳目标-4.497276188e+03 Kappa:1.166265e+18

这一次，优化过程需要更多的迭代，同时，我们得到了一个额外的警告:

uncrush后额外的2个简单迭代,

这表明在未求解的模型上执行了额外的单纯形迭代。另外，请注意卡帕；它的含义将在这部分

如果我们跑rescale.py - f pilotnov.mps。bz2 - s 1 e6获取，我们获得：

使用license文件“/opt/gurobi910/gurobi”。lic从文件pilot . MPS中读取MPS格式模型。bz2读取时间= 0.01秒PILOTNOV: 975行，2172列，13057非零Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (linux64)线程数:6个物理核，12个逻辑处理器，使用多达12个线程优化一个有975行，2172列和13057非零的模型指纹:0xf2c9bd15系数统计:矩阵范围[9e- 12,1e +13]客观范围[2e-09, 1e+06]边界范围[6e- 12,4e +10] RHS范围[1e-05, 4e+04]警告:模型包含较大的矩阵系数范围警告:模型包含较大的边界考虑重新构建模型或设置NumericFocus参数以避免数值问题。preolve removed 101 rows and 255 columns preolve time: 0.00s preolved: 874 rows, 1917 columns, 11897 nonzeros Iteration Objective Primal Inf. Dual Inf. time 0 -6.8659608e+34 7.041252e+31 6.865961e+04 0s Extra simplex iterations after uncrush:47 1537 -4.4972762e+03 0.000000e+00 0.000000e+00 0s解决在1537迭代和0.07秒最优目标-4.497276188e+03 Kappa: 1.851538e+25

现在我们得到了更多的额外单纯形迭代，更令人不安的是，我们得到了一个关于结果解决方案质量的警告：

警告:未缩放的原始违反= 5.65274e-05，残余= 5.65274e-05,

此消息表示解算器难以找到满足默认公差的解决方案。手机万博登录

最后，如果我们逃跑rescale.py - f pilotnov.mps。bz2 - s 1 e8获取，我们获得：

使用license文件“/opt/gurobi910/gurobi”。lic从文件pilot . MPS中读取MPS格式模型。bz2读取时间= 0.01秒PILOTNOV: 975行，2172列，13057非零Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (linux64)线程数:6个物理核，12个逻辑处理器，使用多达12个线程优化一个有975行，2172列和13057非零的模型指纹:0xfea2a63e系数统计:Matrix range [3e- 13,1e +15] Objective range [6e- 11,2e +08] Bounds range [6e- 14,5e +12] RHS range [1e-05, 4e+04] Warning: Model contains large Matrix coefficient range Warning: Model contains large Bounds考虑重新构造模型或设置NumericFocus参数以避免数值问题。预解删除103行和258列预解时间:0.00s预解:872行，1914列，11795非零迭代目标原始Inf. Dual Inf. time 0 -9.3067584e+36 7.106821e+31 9.306758e+06 0s 1469次迭代，0.06秒解不可行模型

在这种情况下，优化运行几乎立即终止，但会出现意外情况不可行结果。

正如你所看到的，当我们进行越来越大的缩放时，我们继续获得相同的最优值，但有明显的迹象表明求解器在挣扎。手机万博登录我们看到警告消息，以及增加迭代计数、运行时和卡帕值。然而，一旦我们传递了一个特定的缩放值，求解器就不再能够求解模型，而是报告它能够手机万博登录不可行．

请注意，这不是Gurobi中的bug。它与根据数字的范围改变数字的含义、使用固定公差以及由于缩放而改变问题的几何结构有关。我们将在后面进一步讨论这个话题后面的一节．