如何使用 GUROBI 在 LP 中找到所有可能的最优解

Question

我用 GUROBI 求解了一个 LP 模型，我知道这个模型有无限多个最优解。正如您在下面看到的，objective 函数和 constr 1 具有相同的斜率并且 constr 1 是绑定的。 GUROBI只显示一个最优解，如何找到所有可能的解（或范围）？如何在更复杂的 LP 模型中找到最优解的数量？

Maximize
   <gurobi.LinExpr: -1.0 x1 + 2.0 x2>
Subject To
   non negative x1 : <gurobi.LinExpr: x1> >= 0.0
   non negative x2 : <gurobi.LinExpr: x2> >= 0.0
   constr 1 : <gurobi.LinExpr: -1.0 x1 + 2.0 x2> <= 4.0
   constr 2 : <gurobi.LinExpr: x1 + x2> <= 5.0
   constr 3 : <gurobi.LinExpr: x1 + -1.0 x2> <= 3.0

Answer 1

所有最优 LP 解决方案是一个困难的概念。它们可能有无限多。 Gurobi 具有枚举所有最优整数解（解池）的工具，但这不适用于纯 LP。所以简短的回答是否定的。

可以枚举所有最优基，但这需要一些工作（基本上使用二进制变量对基进行编码：变量或约束是基本的或非基本的）。看到这个 link。这种方法可以通过添加额外的约束来实现，或者通过使用上述解决方案池来更有效地实现。尽管在概念上很有趣，但值得注意的是，这种方法对于大型问题并不实用。

如何使用 GUROBI 在 LP 中找到所有可能的最优解

How to find all possible optimum solutions in LP with GUROBI

python

linear-programming

gurobi