java - 在 CPLEX 中获取线性规划的所有极值点

Question

我需要使用 Java 中的 CPLEX API 枚举对应于 LP 的所有极值点的所有基。不幸的是，我没有找到使用 CPLEX 执行此操作的任何方法。有解决办法吗？

如果没有，我会自己做，但我需要打基础。CPLEX 是否有任何简单的方法来枚举所有基础并检查基础是否是可行的解决方案？

Answer 1

简短的回答：不。

没有简单的方法可以做到这一点。一种可能但有点麻烦的方法是使用二进制变量对基进行编码。例如：

xb[i] = 1 for basic variables 
        0 for non-basic variables

我们需要对非基本变量添加约束：它们是有界的。即对于一个非负变量x[i]，我们有

xb[i]=0 => x[i]=0  

（这是一个指标约束）。此外，我们知道

sum(i,xb[i]) = m

（基本变量的数量等于模型中的行数）。

然后使用 Cplex 的解池来枚举所有可能的可行基。此链接中显示了此方法的说明。（这个特定的例子列举了所有的最优碱基，但告诉 Cplex 列举所有可行的碱基并不难）。