使用现有的线性编程工具查找所有替代基本解决方案 [英] Find all alternative basic solutions using existing linear-programming tool
问题描述
我必须找到一些微小的线性编程问题的所有基本解决方案.
I have to find all basic solutions of some tiny linear-programming problems.
这是一个示例(以lp_solve格式):
Here's an example (in lp_solve format):
max: x1 + x2;
x1 + x2 <= 1;
x1 <= 0.8;
x2 <= 0.8;
所有2种基本解决方案:
All 2 basic solutions:
- x1 = 0.2，x2 = 0.8
- x1 = 0.8，x2 = 0.2
当然，有找到方法其他解决方案，但我真的更喜欢使用现有的库，而不是精心设计自己的单纯形代码.
Of course there is a way of finding alternative solutions, but I really prefer using existing libraries instead of crafting my own simplex code.
我使用Python作为编程语言，希望 lp_solve 或<一个href ="https://www.gnu.org/software/glpk/" rel ="noreferrer"> GLPK 的C API可以做到这一点.
I'm using Python as my programming language, and hoping there's some method in lp_solve or GLPK's C API can do this.
谢谢.
推荐答案
没有使用glpk进行此操作的例程.和恕我直言，现实中的任何求解器都不太可能实现这样的功能，因为它在实践中不是很有用，而且肯定不是一个简单的问题.
There is no routine to do that with glpk; and IMHO it is very unlikely that any real-world solver implements something like that, since it is not very useful in practise and it is certainly not a simple problem.
一旦使用单纯形算法达到最优，那么找到一个另一个基本解决方案确实很容易，但这并不意味着容易列出所有这些解决方案.
What is indeed easy to find one other basic solution once you reached optimality with the simplex algorithm, which does not mean that it is easy to list them all.
考虑一个域的维度为n的LP；最优解的集合S是凸多面体，其维度m可以是从0到n-1的任何值.
您需要一种方法来列出问题的所有基本解决方案，即S的所有顶点:m大于2时，当您从一个基本解决方案移动到以下位置时，您将需要小心避免循环.另一个.
Consider a LP whose domain has dimension n; the set S of the optimal solutions is a convex polyhedron whose dimension m can be anything from 0 to n-1.
You want a method to list all the basic solutions of the problem, that is all the vertices of S: as soon as m is greater than 2, you will need to carefully avoid cycling when you move from one basic solution to another.
但是，幸运的是，不需要编写自己的单工代码:您可以使用glpk库以及lpsolve访问当前基础的内部结构.
However, there is (luckily!) no need to write your own simplex code: you can access the internals of the current basis with the glpk library, and probably with lpsolve too.
两种可能的解决方案
-
更好的方法是使用其他库，例如 PPL 为了这. 假设您遇到以下形式的问题:
The better way would be to use another library such as PPL for this. Assume that you have a problem of the form:
min cx; subject to: Ax <= b
首先使用glpk解决问题，这将为您提供问题的最佳值V.从这一点出发，您可以使用PPL来获取最佳值的多面体的描述:
First solve your problem with glpk, this will give you the optimal value V of the problem. From this point, you can use PPL to get the description of the polyedron of optimal values:
cx = V and Ax <= b
作为其极限点的凸包，对应于您要查找的BFS.
as the convex hull of its extreme points, which correspond to the BFSs you are looking for.
您可以(可能)使用glpk单工例程.一旦获得最佳的BFS，就可以使用例程glp_get_row_dual获得与所有非基本列相关的降低的成本(可以通过glp_get_row_stat获取变量的基本状态)，因此您可以找到非基本列成本降低为空的变量.然后，我认为您可以使用函数glp_set_row_stat更改此列的基础状态，以使其输入基础.
(然后，只要避免循环，就可以重复此过程.)
You can (probably) use the glpk simplex routines. Once you get an optimal BFS, you can get the reduced cost associated with all non-basic columns using the routine glp_get_row_dual (the basis status of the variable can be obtained with glp_get_row_stat), so you can find a non-basic variables with a null reduced cost. Then, I think that you can use function glp_set_row_stat to change the basis status of this column in order to have it enter the basis.
(And then, you can iterate this process as long as you avoid cycling.)
请注意，我自己没有尝试任何一种解决方案.我认为第一个到目前为止是最好的，尽管这需要您学习PPL API.如果您想进行第二篇文章，我强烈建议您向glpk维护者发送一封电子邮件(或查看源代码)，因为我不确定它是否能照常工作.
Note that I did not try any of those solutions myself; I think that the first one is by far the best, although it will require that you learn the PPL API. If you wish to go for the second one, I strongly suggest that you send an e-mail to the glpk maintainer (or look at the source code), because I am really not sure it will work as is.
这篇关于使用现有的线性编程工具查找所有替代基本解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
