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?