我需要使用Java中的CPLEX API枚举与LP的所有极值点相对应的所有基础。不幸的是,我没有找到任何方法与CPLEX这样做。有解决方案吗?
如果没有,我会自己做,但我需要发挥基础。 CPLEX是否有任何简单的方法可以枚举所有基础并检查基础是否是可行的解决方案?
简短的回答:没有。
没有简单的方法可以做到这一点。一种可能的方法,但有些麻烦,是使用二进制变量对基础进行编码。例如。:
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的解决方案池来枚举所有可能的可行基础。这个方法的插图显示在这个link中。 (这个特定的例子列举了所有最佳基础,但要告诉Cplex列举所有可行的基础并不困难)。