在CPLEX中获取线性程序的所有极端点

Question

我需要枚举与Java中的CPLEX API相对应的所有基础。不幸的是，我找不到使用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的解决方案池枚举所有可能的可行基础。此方法中显示了此方法的插图。（这个特定的例子列举了所有最佳基础，但是不难告诉CPLEX枚举所有可行的基础）。