使用现有的线性规划工具找到所有替代的基本解决方案

Question

我必须找到一些微小的线性规划问题的所有基本解。

这是一个示例（lp_solve 格式）：

max: x1 + x2;
x1 + x2 <= 1;
x1 <= 0.8;
x2 <= 0.8;

所有 2 个基本解决方案：

当然 a way 可以找到替代解决方案，但我真的更喜欢使用现有库而不是编写自己的单纯形代码。

我正在使用 Python 作为我的编程语言，希望 lp_solve or GLPK 的 C API 中有一些方法可以做到这一点。

谢谢。

Answer 1

glpk 没有例程可以做到这一点；恕我直言，任何现实世界的求解器都不太可能实现类似的东西，因为它在实践中不是很有用，而且肯定不是一个简单的问题。

什么确实很容易找到一个其他基本解决方案一旦你用单纯形算法达到最优，这并不意味着很容易列出它们。

考虑一个 LP，其域的维度为 n；最优解的集合S是一个凸多面体，其维度m可以是0到n-1之间的任何值。你想要一个方法来列出问题的所有基本解决方案，即 S 的所有顶点：一旦 m 大于 2，你需要小心避免在移动时循环一个基本解决方案。

然而，（幸运的是！）无需编写您自己的单纯形代码：您可以使用 glpk 库访问当前基础的内部结构，也可能使用 lpsolve。

编辑：两种可能的解决方案

更好的方法是为此使用另一个库，例如 PPL。假设您遇到以下形式的问题：
```
min cx; subject to: Ax <= b
```
首先用 glpk 解决你的问题，这会给你问题的最优值 V。至此，可以使用PPL得到最优值多面体的描述：
```
cx = V and Ax <= b
```
作为其极值点的凸包，对应你要找的BFS。
您可以（可能）使用 glpk 单纯形例程。一旦你得到一个最优的BFS，你可以使用例程glp_get_row_dual获得与所有非基本列相关的降低的成本（变量的基本状态可以使用glp_get_row_stat获得），所以你可以找到具有零降低成本的非基本变量。那么，我觉得可以用函数glp_set_row_stat改变这个柱子的基础状态，让它进入基础。（然后，只要避免循环，就可以重复这个过程。）

请注意，我自己并没有尝试任何这些解决方案；我认为第一个是迄今为止最好的，尽管它需要您学习 PPL API。如果你想选择第二个，我强烈建议你给 glpk 维护者发一封电子邮件（或查看源代码），因为我真的不确定它是否会按原样工作。

Find all alternative basic solutions using existing linear-programming tool