这是我在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%GAP
这是否意味着解决方案仍然存在这么小的差距,但事实证明它是最佳解决方案?我有(可能是错误的)想法,最优性通过0%的差距证明。
我不确定如何正确解释它。感谢您的帮助。
是的,你是对的。如果上限和下限评估相同的值,则证明最优性,即CPLEX可以证明0%的最优性差距。
由于CPLEX停止的解决方案间隙为0.57%,我认为您配置的MIP间隙<1%。如果您对已证明最佳的解决方案感兴趣,则应将MIPGap参数更改为零。另见here。
您对最佳约束的理解并非100%正确。根据求解器到目前为止发现的信息,您可以将最佳边界视为整数解决方案可能具有的最佳目标值。在你的情况下,实际上可能有一个比你找到的解决方案更好的解决方案,但如果存在,它将没有比435.6381更好的客观值。
对于尚未从搜索空间中消除的任何区域,最佳约束的最佳放松但区域约束的解决方案的技术定义更为技术性。像CPLEX这样的求解器通过将搜索空间划分为子区域然后排除不可能包含最佳整数可行解的子区域来搜索最优解。这些子区域被分成子子区域,依此类推。在每个区域内,修改原始问题以强制变量落入该区域。这个修改过的问题的轻松解决方案是该地区的最佳约束。这些区域特定最佳边界中最好的是整个问题的最佳界限。
排除区域的最佳约束变化。如果最佳约束不等于最佳解决方案,那么根据定义,除了持有当前在位者的区域之外,仍然存在至少一个可能存在更好解决方案的区域。探索其中一个区域可能会发现比现有现有区域更好的解决方案,或者可能导致该区域被排除在外。在探索该地区之前,您不知道哪个。只有当最佳解决方案等于最佳约束时,您才能确定没有更好的解决方案隐藏在剩余区域中。