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

Question

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

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

Answer 1

简短的回答：没有。

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

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

我们需要对非基本变量添加约束：它们将处于边界。 IE。对于非负变量 x[i] 我们有

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

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

sum(i,xb[i]) = m

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

然后使用Cplex的解池枚举所有可能的可行基。 link 中显示了此方法的示例。 （这个特殊的例子枚举了所有的最优基，但是告诉 Cplex 枚举所有可行的基并不难）。