如何解释 CPLEX 交互式优化器的输出？

Question

我一直在使用 CPLEX 交互式优化器来解决一些线性规划问题。我生成问题，使用 CPLEX 中的 read 命令，然后使用运行 optimize。对于某些问题，CPLEX 在一小时内生成解决方案，我使用 write <filename> sol 获得完整的解决方案。但是，对于某些问题，似乎 stuck 过了一点。我看到的输出如下所示：

       Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
    .        .        .        .        .        .        .        .        .
    .        .        .        .        .        .        .        .        .
    .        .        .        .        .        .        .        .        .
Elapsed time = 816.06 sec. (429933.56 ticks, tree = 8.58 MB, solutions = 13)
   2884  1809       87.6482 12159      201.6200       80.3540  2100428   60.15%
   2938  1863      102.4825 11621      201.6200       80.3540  2149201   60.15%
   3727  2616       93.1194 10858      201.6200       80.3540  2409711   60.15%
   3743  2632       92.6249 11845      201.6200       80.3540  2437316   60.15%
   3767  2656       91.7097 12044      201.6200       80.3540  2466252   60.15%
   3803  2692       91.8088 11972      201.6200       80.3540  2491113   60.15%
   3805  2694      101.4411 10242      201.6200       80.3540  2497951   60.15%
   3827  2716       91.7697 12003      201.6200       80.3540  2522926   60.15%
   3937  2826      102.6357  7167      201.6200       80.3540  2676145   60.15%
   4175  3056       94.0081  9159      201.6200       83.9275  2783878   58.37%
Elapsed time = 930.33 sec. (472066.00 ticks, tree = 20.04 MB, solutions = 13)
   4178  3059       88.0621 11735      201.6200       83.9275  2788962   58.37%
   4190  3071       87.5922 11461      201.6200       83.9275  2809216   58.37%
   4202  3083       87.7980 11585      201.6200       83.9275  2823899   58.37%
   4214  3095       87.9296 11733      201.6200       83.9275  2841065   58.37%
   4215  3096       92.6440 11647      201.6200       83.9275  2844197   58.37%
   4227  3108       94.0457 12069      201.6200       83.9275  2869047   58.37%
   4239  3119       93.3760 11843      201.6200       83.9275  2890566   58.37%
   4251  3131       94.2709 11724      201.6200       83.9275  2916710   58.37%
   4274  3153       92.6187 11640      201.6200       83.9275  2945659   58.37%
   4286  3163       91.6257 11632      201.6200       83.9275  2965344   58.37%
Elapsed time = 998.66 sec. (493988.99 ticks, tree = 20.09 MB, solutions = 13)
   4310  3186       91.8091 10453      201.6200       83.9275  3010401   58.37%
   4323  3199       96.4584 11813      201.6200       83.9275  3034842   58.37%
   4335  3211       96.1343 11849      201.6200       83.9275  3057500   58.37%
   4359  3234       96.8602 11609      201.6200       83.9275  3092422   58.37%

一开始，最后一列的数字较大（例如，99.92%），然后开始迅速下降。但是在某一点之后，最后的 gap 列继续显示 58.37% 而没有进一步减少。这个值代表什么？我的理解是，这是当前最优解和全局最优解之间的百分比差异。（即，x% 意味着如果我在此时停止优化，返回的解决方案可证明在全局最优的 x% 范围内）。

我的理解对吗？另外，如何才能理解和debug/get-around这种"getting stuck"的现象？

Answer 1

% 差距是最佳解决方案与解决方案的最知名边界之间的相对差异。这保证高于已知最佳解决方案与真正的全局最优解之间的差距。在您的情况下，最佳界限是 83.9275，最佳界限是 201.62，并且您正在最小化，所以差距是

1 - (83.9275 / 201.62)  =  .5837

您看到的 "stuck" 行为在解决复杂的混合整数问题时很常见。有可能您拥有的解决方案实际上接近最优，但界限并不严格，或者您的解决方案确实远非最优，但 CPLEX 无法找到更好的解决方案。有很多方法可以尝试解决这个问题。其中有

改进您的 MIP 公式
尝试不同的参数（调高切割、探测、切换到强分支，...）
查看其他求解器是否能更好地解决您的问题（gurobi 或 xpressmp）

如何解释 CPLEX 交互式优化器的输出？

How to interpret the output of the CPLEX interactive optimizer?

optimization

cplex