Recover linear programming basis

Question

Given a basic solution (regardless of whether it is feasible or not, optimal or not) in linear programming, how do I recover the set of basic variables? Please notice that this is not as simple as identifying nonzero variables in the solution, because there are so-called degenerate cases where some basic variables are zero.

I'm asking this question because I'm using the software Mathematica, which has a function called LinearProgramming that implements the simplex method to find an optimal basic feasible solution. If the input has only rational coefficients, the function returns exact symbolic values for the variables (like 5/3 instead of 1.66667). The problem, though, is that the function doesn't tell which set of variables it has determined as the basis in the optimal basic feasible solution it returns (which is weird, because it must internally do it, because it implements simplex; so the problem really is simply that Mathematica hasn't added any option for the function to return that internally saved information).

I need to identify the set of basic variables in a linear programming problem because it corresponds to the set of basic variables in a related linear programming problem that cannot be solved directly because it involves symbolic values in a limit. More specifically, I'm implementing a method to find the sequential equilibria of a game.

If one proceeds directly from the formula for determining the basic solution that corresponds to a choice of basic variables, one gets a trial-and-error method which is exponential and in the worst case no better than the method of enumerating all basic solutions (which was used as the only systematic method to solve linear programs before the simplex method was devised). Is there any faster way?

Answer 1

Let M' denote the transpose of a matrix M. Let the linear programming be in the standard form

max  c'x
s.t. Ax=b
     x>=0

where A is a full-rank m by n matrix with m<=n (yes, every linear programming problem can be brought to this form by converting some equality constraints to double inequality constraints and adding slack variables). So, in every basic solution, n-m variables (the non-basic ones) are set to zero. Given a basic solution, let A_basic be the submatrix of A corresponding to the basic solution (that is, take the columns of A indexed by the indices of the basic variables).

Now, given a basic solution (whose set of basic variables is not known), a choice of n-m variables that have zero value in that solution as being nonbasic (and the rest as being basic) is valid if and only if A_basic corresponding to that choice is invertible.

So, here's a method.

1. Given a basic solution.
2. Pick n-m variables that have zero value in that solution. Designate them as being nonbasic (and the rest as being basic).
3. Construct A_basic that corresponds to this choice of basic variables.
4. If A_basic is invertible, then Success. A set of basic variables that corresponds to the given basic solution has been identified.
5. If A_basic is not invertible, then Failure.

Sadly, there really are choices in (2) that leads to failure in (5)... Trying all possibilities in (2) leads to an exponential algorithm.

EDIT: I have found it!

Finally, I have found an answer to my own problem without help from anybody in this forum. It turns out to be very simple. The key insight is in using the fact that any linearly independent set of columns of A can be extended to a 'basis' of R^m (here, it means that an invertible A_basic can be found by extending any set of columns that is already linearly independent). Of course, the set of columns of the whole matrix A itself is already guaranteed to span R^m, because if not, then there would be no such thing as an invertible A_basic (implying that Simplex doesn't always terminate successfully, which we know is not true).

Only step (2) in my method above needs to be modified. Pick all variables that have nonzero value in the given solution. If there are m variables in this set, then it is the set of basic variables, and we are done. If not, at least we have a guarantee that the set of columns of A indexed by the indices of the variables in this set is linearly independent (because if not, then it cannot be part of any invertible A_basic, contradicting the fact that the given solution is basic). We can extend this set to become a set of basic variables in a fairly straightforward 'linear' (well, actually, only polynomial) way:

1. Pick any column of A that is not yet currently indexed by an index of a variable in our set.
2. Check whether the column just picked is in the space spanned by the currently 'chosen' columns. If it is, go back to (1) (that is, try another column). If it is not, add the variable indexed by the index of the column to our set of variables.
3. A new set of linearly independent columns of A has been constructed (corresponding to our newly constructed set of variables). Repeat this process until we have m columns, that is, invertible A_basic. The corresponding set of variables is the set of basic variables.

This algorithm is polynomial, because there is never any need to 'backtrack' in the choice of basic variables. Once a variable is chosen, it remains chosen until the set has been completed.