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() 是当前最佳解决方案的目标值(对应于已找到的可行解决方案)。这是一个下限，这是您要在第二个问题中使用的值。