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％差距证明。

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

- Riegsche

Answer 1

您对最优界限的理解不完全正确。可以将最优界限视为基于求解器目前已发现的信息，整数解可能具有的最佳目标值。在您的情况下，实际上可能会有比您找到的更好的解决方案，但如果有，它的目标值也不会比435.6381更好。

关于最优界限的更技术性定义是，在尚未从搜索空间中消除的任何区域中，最佳放松-但区域受限制的解。像CPLEX这样的求解器通过将搜索空间分成子区域并排除无法包含最优整数可行解的子区域来查找最优解。这些子区域被分割成子子区域等。在每个区域内，原始问题被修改以强制变量落在该区域内。该修改后问题的放松解是该区域的最佳界限。这些区域特定的最佳界限中的最佳界限是问题的全局最佳界限。

随着区域被排除，最佳界限会改变。如果最佳界限不等于最佳解，则根据定义，仍然存在至少一个区域除了持有当前incumbent的区域，该区域可能潜在地拥有更好的解决方案。探索其中一个区域可能会发现比当前的incumbent更好的解决方案，也可能导致该区域被排除。在区域被探索之前，您不知道哪个区域会发生什么。只有当最佳解等于最佳界限时，您才确切知道没有更好的解决方案隐藏在剩余的区域中。

- Darryl

---

很好的解释。 - denis

Answer 2

是的，你说得对。如果上界和下界计算出相同的值，即CPLEX可以证明最优性差距为0％，则优化性已被证明。

由于CPLEX停止时解决方案的差距为0.57％，我认为您配置了小于1％的MIP-gap。如果您对已经证明最优的解决方案感兴趣，则应将MIPGap参数更改为零。请参见此处。

- Berkan Erol

---

你好！请问能否更新一下你的回答中的链接？谢谢。 - Raquel Aguiar