Get all extreme points of Linear Program in CPLEX

Question

I need to enumerate all basis corresponding to all extreme points of a LP with the CPLEX API in Java. Unfortunately I did not find any way to do this with CPLEX. Is there a solution ?

If not, I will do this myself but I will need to play with basis. Is any simple way with CPLEX to enumerate all basis and check if a basis is a feasible solution ?

Answer 1

The short answer: no.

There is no easy way to do this. One possible approach, but somewhat cumbersome, is to encode the basis using binary variables. E.g.:

xb[i] = 1 for basic variables 
        0 for non-basic variables

We need to add constraints on non-basic variables: they will be at bound. I.e. for a non-negative variable x[i] we have

xb[i]=0 => x[i]=0  

(this is an indicator constraint). Furthermore we know that

sum(i,xb[i]) = m

(the number of basic variables is equal to the number of rows in the model).

Then use Cplex's solution pool to enumerate all possible feasible bases. An illustration for this approach is shown in this link. (This particular example enumerates all optimal bases, but it is not difficult to tell Cplex to enumerate all feasible bases).