Find all alternative basic solutions using existing linear-programming tool

Question

I have to find all basic solutions of some tiny linear-programming problems.

Here's an example (in lp_solve format):

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

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.

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.

Thanks.

Answer 1

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.

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.

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.

Edit: two possible solutions

1. 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.

2. 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.)

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.