glpk
来实现这个功能;我认为在实际情况中,任何真正的求解器都不可能实现这样的功能,因为它在实践中并不十分有用,而且这绝对不是一个简单的问题。n
;最优解集合S
是一个凸多面体,其维度m
可以是从0
到n-1
的任何值。你想要一种方法来列出问题的所有基本解,也就是S
的所有顶点:当m
大于2时,你需要仔细避免在从一个基本解移动到另一个基本解时出现循环。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
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
as the convex hull of its extreme points, which correspond to the BFSs you are looking for.
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.)