CPLEX中的GAP解释 [英] Interpretation of GAP in CPLEX
问题描述
这是我从CPLEX 12.7.0中解决的小规模混合整数线性优化问题中获得的引擎日志输出的一部分
This is a part of the engine-log output that I get from a small-scale mixed integer linear optimization problem that I solved in 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作为最佳绑定解.
What I understand from this, is that the best integer solution (for the objective function) found has the value of 438.1448, whereas the relaxed solution (non integer values) has the value of 435.6381 as best bound solution.
(438.1448/435.6381)-1 = 0.57％GAP
( 438.1448 / 435.6381 ) - 1 = 0.57% GAP
这是否意味着解决方案仍具有很小的差距，但是事实证明它是最佳解决方案?我有一个(也许是错误的)想法，即0％的差距证明了最优性.
Does this mean that the solution still has that small gap, however it is proven to be the optimal solution? I had the (maybe wrong) idea that optimality is proven by a 0% gap.
我不确定如何正确解释它.感谢您的提前帮助.
I'm not sure how to interpret it correctly. Thanks for your help in advance.
推荐答案
您对最佳界限的理解不是100％正确.根据到目前为止求解器发现的信息，您可以将最佳界限视为整数解决方案可能具有的最佳目标值.在您的情况下，实际上可能有比您发现的解决方案更好的解决方案，但如果有的话，它的客观价值不会高于435.6381.
Your understanding of the best bound isn't 100% correct. You can think of the best bound as the best objective value an integer solution could potentially have, based on information the solver has discovered so far. In your case there might actually be a better solution than the one you found, but if there is, it won't have an objective value better than 435.6381.
对最佳界限的更技术定义是，对于尚未从搜索空间中消除的任何区域，最佳的放松但受区域约束的解决方案.像CPLEX这样的求解器通过将搜索空间划分为多个子区域，然后排除可能无法包含最优整数可行解的子区域来寻找最佳解决方案.这些子区域被分成子子区域，依此类推.在每个区域内，对原始问题进行了修改，以迫使变量落入该区域内.对此问题的轻松解决方案是该地区的最佳选择.这些特定于区域的最佳范围中的最佳范围是整个问题的最佳范围.
A more technical definition of the best bound is the best relaxed-but-region-constrained solution for any region that has not yet been eliminated from the search space. Solvers like CPLEX search for an optimal solution by splitting the search space into sub-regions and then ruling out sub-regions that can't possibly contain the optimal integer-feasible solution. These sub-regions get split into sub-sub-regions, and so on. Within each region, the original problem is modified to force variables to fall within the region. The relaxed solution to this modified problem is the best bound for the region. The best of these region-specific best bounds is the best bound for the problem as a whole.
排除了区域的最佳界限变化.如果最佳界限不等于最佳解决方案，那么根据定义，除拥有当前任职者的地区以外，至少还有一个区域可能会持有更好的解决方案.探索这些区域之一可能会发现比您当前任职者更好的解决方案，或者可能导致该区域被排除在外.在探索该地区之前，您不知道是哪个.只有当最佳解决方案等于最佳界限时，您才能确定剩余区域中没有更好的解决方案.
The best bound changes as regions are ruled out. If the best bound does not equal the best solution, then by definition, there is still at least one region other than the region holding the current incumbent that could potentially hold a better solution. Exploring one of these regions might uncover an even better solution than your current incumbent, or it might lead to the region being ruled out. You don't know which until the region is explored. Only when the best solution equals the best bound do you know for sure that there isn't a better solution hiding in a remaining region.
这篇关于CPLEX中的GAP解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
