java - CPLEX+Java 中最大化的完整性差距漏洞？

Question

我尝试解决一个大型 MIP，其中 .如果没有最优解，则返回完整性差距(即最佳整数解与线性松弛最佳解之间的差值)。 使用 Java+CPLEX 接口(interface)的 getMIPRelativeGap 时，我有时会得到 1.0E11-1.0E13 范围内的值，这是没有意义的，因为完整性差距应该是 0 到 1 之间的百分比。我跟踪这些情况下来，发现如果最佳整数解决方案的值为 0，我会得到这些结果(我的内部问题是一个有利可图的旅游问题，因此，如果最佳路线不访问任何顶点)。完整性差距应该是 (bestobjective-bestinteger)/bestobjective ( https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.0/ilog.odms.cplex.help/refdotnetcplex/html/M_ILOG_CPLEX_Cplex_MIPInfoCallback_GetMIPRelativeGap.htm )，但是，它似乎是 (bestobjective-bestinteger)/bestinteger。 我还测试了几个其他值(如果整数目标为正)，并且能够在示例中证实这一点。

其他人可以重现此行为吗？这种行为对您来说有意义吗？

谢谢:)

Answer 1

确实，documentation对于可调用库 (C API) 中的 CPXgetmiprelgap 表示如下:

For a minimization problem, this value is computed by

(bestinteger - bestobjective) / (1e-10 + |bestinteger|)

where bestinteger is the value returned by CPXXgetobjval/CPXgetobjval and bestobjective is the value returned by CPXXgetbestobjval/CPXgetbestobjval. For a maximization problem, the value is computed by:

(bestobjective - bestinteger) / (1e-10 + |bestinteger|)

因此，Java API 的文档看起来有问题。 Java API 只是在底层调用 CPXgetmiprelgap，所以它应该是相同的。感谢您报告此事。我将确保将此问题转交给能够修复它的人员。