CPLEX MIP提前终止,具有相对间隙,getBestObjValue与getObjValue



我使用C++对CPLEX的(最大化)MIP进行建模,并使用指定相对间隙

cplex.setParam(IloCplex::EpGap, gap);

我对之间的区别感到困惑

cplex.getBestObjValue();

cplex.getObjValue();

以防因间隙而提前终止。

如果我理解正确,getBestObjValue()的值将始终对应于整数可行解,并且下限绑定到最优值。另一方面,来自getObjValue()的值(可能?将始终?)对应于不可行的解,并且是最优值的上界。我的理解正确吗?

我还有另一个问题:在最大化问题的情况下,getBestObjValue()返回的值是"所有剩余未探索节点的最大目标函数值"(来自CPLEX文档)。有没有一种方法可以查询这些未探索节点的目标值?我这么问是因为我想得到满足我的相对差距的最小值,而不是最大值。

根据手册:

Cplex.GetBestObjValue方法:
对于最小化问题,它被计算为所有剩余未探索节点的最小目标函数值。类似地,对于最大化问题,它被计算为所有剩余未探索节点的最大目标函数值

对于常规MIP优化,该值也是MIP问题的最优解值的最已知界。事实上,当一个问题被求解到最优性时,这个值与最优解的值相匹配。

它对应于目标值的上限(当最大化时),当你在达到最优性之前停止求解器时,会有一个间隙。在MIP中,后面有分枝定界树,随着节点的探索,上界减小。当你在epgap停下来时,可能有也可能没有任何解决方案与上限相匹配。

因此,您下面的假设是错误的:

如果我理解正确,getBestObjValue()的值将始终对应于整数可行解

另一方面,GetObjValue()是当前最佳解的目标值(对应于找到的可行解)。这是一个下界,这是你想在第二个问题中使用的值。

最新更新