8

这是我从 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% 的差距证明。

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

4

2 回答 2

7

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

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

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

于 2019-03-22T23:56:30.797 回答
2

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

由于 CPLEX 以间隙为 0.57% 的解决方案停止，因此我假设您配置了 MIP 间隙 <1%。如果您对已证明最优的解决方案感兴趣，则应将 MIPGap 参数更改为零。另请参见此处。

于 2017-03-31T09:38:50.817 回答