1

这是这个问题的后续问题：解释 CPLEX 中的 GAP

我在优化（最小）问题开始时使用了以下表达式：

execute gapTermination {
    cplex.epgap = 0.00; // result at gap of 0%  
   }

这是引擎日志的一部分：

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

      0     0      560.7929   100                    560.7929      115         
      0     0      742.1396    57                   Cuts: 121      214         
      0     0      744.3119    61                    Cuts: 10      226         
      0     0      747.2193    61                    Cuts: 10      233         
      0     0      747.2797    61                      MCF: 1      234         
*     0+    0                          916.3811      747.2797            18.45%
      0     2      747.2797    61      916.3811      747.2797      234   18.45%

Elapsed time = 0.13 sec. (49.77 ticks, tree = 0.00 MB, solutions = 1)
*   916   755      integral     0      778.9609      753.8931     7249    3.22%
*  4739  1918      integral     0      771.9166      759.5332    25884    1.60%

Cover cuts applied:  5
Implied bound cuts applied:  8
Flow cuts applied:  27
Mixed integer rounding cuts applied:  36
Multi commodity flow cuts applied:  1
Gomory fractional cuts applied:  22

Root node processing (before b&c):
  Real time             =    0.11 sec. (49.41 ticks)
Parallel b&c, 16 threads:
  Real time             =    0.38 sec. (202.30 ticks)
  Sync time (average)   =    0.07 sec.
  Wait time (average)   =    0.07 sec.
                      ------------
Total (root+branch&cut) =    0.49 sec. (251.71 ticks)

如您所见，似乎找到了“最佳”解决方案，但仍有 1.60% 的差距。

如何解释这个？我的想法是，我找到了最佳整数解决方案（没有一个更好的整数解决方案），但非整数值实现了更好的结果，降低了 1.60%（最小化问题）。

如果我的想法是正确的，那么这意味着只有当松弛解（通常是非整数）的最优值恰好是整数值时，才能实现 0.00% 的差距。

如果有人可以在这里帮助我，我将不胜感激。提前致谢。

4

0 回答 0