c++ - 具有相对间隙的 CPLEX MIP 提前终止，getBestObjValue 与 getObjValue

Question

我使用 C++ 通过 CPLEX 对(最大化)MIP 进行建模，并使用

指定相对间隙

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

我对两者之间的差异感到困惑

cplex.getBestObjValue();

和

cplex.getObjValue();

由于时间间隔而提前终止的情况。

如果我理解正确，getBestObjValue() 的值将始终对应于整数可行解决方案和较低的解决方案 绑定(bind)到最优值。另一方面，来自 getObjValue() 的值(可能？永远？)对应于一个不可行解决方案，并且是一个上层绑定(bind)到最优值。我的理解正确吗？

我还有另一个问题:在最大化问题的情况下，getBestObjValue() 返回的值是“所有剩余未探索节点的最大目标函数值”(来自 CPLEX 文档) 。有没有办法查询这些未探索节点的目标值？我这样问是因为我想获得满足我的相对差距的最小值，而不是最大值。

Answer 1

根据手册:

Cplex.GetBestObjValue Method:
It is computed for a minimization problem as the minimum objective function value of all remaining unexplored nodes. Similarly, it is computed for a maximization problem as the maximum objective function value of all remaining unexplored nodes.

For a regular MIP optimization, this value is also the best known bound on the optimal solution value of the MIP problem. In fact, when a problem has been solved to optimality, this value matches the optimal solution value.

它对应于目标值的上限(最大化时)，当您在达到最优之前停止求解器时会存在间隙。在MIP中，后面有分支定界树，随着探索的节点越多，上界就会减小。当您停在 epgap 处时，可能存在也可能不存在任何与上限匹配的解。

因此您的以下假设是错误的:

If I understand correctly, the value from getBestObjValue() will always correspond to an integer feasible solution.

另一方面，GetObjValue() 是当前最佳解决方案的目标值(对应于找到的可行解决方案)。这是一个下限，这是您要在第二个问题中使用的值。