CPLEX+Java | MAXIMIZATION 中的完整性差距漏洞？

Question

我尝试解决一个大型 MIP，其中 .如果不是最优解，则应return完整性差距（即最优整数解与线性松弛最优解之差）。 使用 Java+CPLEX 接口的 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。 我还测试了其他几个值（如果整数 objective 为正），并能够在示例中确认这一点。

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

谢谢:)

Answer 1

实际上，可调用库 (C API) 中 CPXgetmiprelgap 的 documentation 表示如下：

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，所以应该是一样的。感谢您报告此事。我会确保将它传递给可以修复它的人。