CPLEX 中 GAP 的解释

Question

这是我在 CPLEX 12.7.0 中解决的小规模混合整数线性优化问题中获得的引擎日志输出的一部分

    Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0      280.0338    78                    280.0338       72         
      0     0      428.8558    28                    Cuts: 89      137         
      0     0      429.5221    34                     Cuts: 2      142         
      0     0      429.7745    34                  MIRcuts: 2      143         
*     0+    0                          460.9166      429.7745             6.76%
      0     2      429.7745    34      460.9166      429.8666      143    6.74%
Elapsed time = 0.49 sec. (31.07 ticks, tree = 0.01 MB, solutions = 1)
*    35     8      integral     0      438.1448      435.6381      211    0.57%

Cover cuts applied:  17
Implied bound cuts applied:  10
Flow cuts applied:  11
Mixed integer rounding cuts applied:  9
Gomory fractional cuts applied:  24

Root node processing (before b&c):
  Real time             =    0.45 sec. (31.09 ticks)
Sequential b&c:
  Real time             =    0.08 sec. (20.80 ticks)
                          ------------
Total (root+branch&cut) =    0.53 sec. (51.89 ticks)

据我了解，找到的最佳整数解（对于目标函数）的值为 438.1448，而宽松解（非整数值）的最佳边界解值为 435.6381。

( 438.1448 / 435.6381 ) - 1 = 0.57% 差距

这是否意味着该解决方案仍然有那么小的差距，但它被证明是最佳解决方案？我有一个（也许是错误的）想法：最优性是通过 0% 的差距来证明的。

我不确定如何正确解释它。提前感谢您的帮助。

Answer 1

您对最佳界限的理解并非 100% 正确。根据求解器迄今为止发现的信息，您可以将最佳界限视为整数解可能具有的最佳目标值。在您的情况下，实际上可能有比您找到的更好的解决方案，但如果有，它的客观值不会比 435.6381 更好。

最佳边界的更具技术性的定义是尚未从搜索空间中消除的任何区域的最佳松弛但区域约束的解决方案。像 CPLEX 这样的求解器通过将搜索空间拆分为子区域然后排除不可能包含最佳整数可行解的子区域来搜索最佳解。这些子区域被分成子子区域，依此类推。在每个区域内，修改原始问题以强制变量落在该区域内。这个修改后的问题的宽松解决方案是该区域的最佳边界。这些特定于区域的最佳边界中的最佳边界是整个问题的最佳边界。

随着区域被排除，最佳边界会发生变化。如果最佳边界不等于最佳解决方案，那么根据定义，除了拥有当前在职者的区域之外，至少还有一个区域可能拥有更好的解决方案。探索这些地区之一可能会发现比您当前的现任者更好的解决方案，或者可能会导致该地区被排除在外。在探索该地区之前，您不知道哪个。只有当最佳解决方案等于最佳界限时，您才能确定没有更好的解决方案隐藏在剩余区域中。

Answer 2

是的你是对的。如果上限和下限评估相同的值，则证明最优性，即 CPLEX 可以证明 0% 的最优性差距。

由于 CPLEX 停止并出现间隙为 0.57% 的解决方案，因此我假设您配置的 MIP 间隙 <1%。如果您对经过验证的最佳解决方案感兴趣，则应将 MIPGap 参数更改为零。另请参阅此处。