4

我在 C++ 中使用 CPLEX 来解决集线器位置问题,即 MIP,并且我最近发现了一组非常精确的输入,CPLEX 认为这些输入是不可行的(即 CPXMIP_INFEASIBLE),即使该问题肯定是可行的。在 MIP Presolve 期间,CPLEX 中的问题似乎出现了分歧;通常在这一点上问题被简化为空问题,但不是在不可行的输入集中。

我发现对输入数据进行几乎任何轻微调整都可以切换 CPLEX 找到解决方案的能力。例如,将 250.242566 更改为 250.242567,或者甚至只是将每个输入值四舍五入到最接近的整数,都会给我一个完全有效的解决方案。

软化我拥有的两个松弛约束也将允许一个解决方案,但考虑到输入数据,这些约束不应该被打破。求解后这些约束变量的值近似为 0,但略为负,例如 -0.7e-10。(这是可疑的,因为值应该大于 0。)

到底是怎么回事?我一无所知。我尝试调整一些与精度相关的 CPLEX 变量(即 CPX_PARAM_NUMERICALEMPHASIS、CPX_PARAM_EPOPT、CPX_PARAM_EPMRK、CPX_PARAM_EPRHS),但没有任何帮助。输入数据本身对精度的要求并不高——输入中的最小值为 1.412,最大值为 1520.984907。

我将不胜感激任何意见或建议!


更新:

我注意到在 MIP 的 Presolve 期间,不可行问题与可行问题有所不同。

检查 CPXgetprestat 是否存在这两个问题,我可以看到这两个问题之间的一个显着区别是在 pcstat 向量中,一个变量不能在不可行集中聚合出来(即,在不可行问题中的值为 0,而在可行问题中为 -4) .

此外,CPXgetprestat 的 ocstat 和 orstat 向量在不可行问题中各有一个非零值(可行问题没有,因为它已被简化为空问题),但我不确定如何处理这两个值。如果 orstat[0] == 7 和 ocstat[0] == 1,这是否意味着在 Presolve 之前的第 7 行和问题的第一个变量中有一些值得注意的地方?我将如何检查这个?

我已经比较了两个问题中 CPXwriteprob 的输出,除了我将输入值更改了 0.0001 以使问题不可行之外,没有什么不同。

4

1 回答 1

1

也许尝试设置EpInt = 0?所以整数确实是整数。

从手册复制:

价值观

从 0.0 到 0.5 的任意数字;默认值:1e-05。

于 2012-08-03T04:13:48.377 回答