I am working on an implementation for the Revised Simplex Method. I am up to the stage where I need to find the entering variable (assume for this case that this iteration is not optimal and so has an entering variable). However the function does not explicitly take basic and non-basic variables (or their associated constraint sub-matrices as inputs.
Essentially, for inputs to the function, I have:
$A = $ The constraint matrix with dimensions $m,n$
$c =$ The cost coefficients vector
$\pi^T = $ the vector of duals transposed.
I understand that $\pi^T = c_B^TB^{-1}$ and in order to calculate the vector of reduced costs:
$rdcost = c_N^T - \pi^TN$
$rdcost = c_N^T - c_B^TB^{-1}N$
Where $B$ is the sub-matrix of A for basic variables and N is the sub-matrix of A for non-basic variables.
However, I do not know an efficient way to find what variables are basic and non-basic in order to partition $c$ and $A$ to find reduced costs. The only idea that comes to mind is to test every combination of $c_B^TB^{-1}$ and then equate that to $\pi$, yet I see issues with this method computationally and in the event different combinations result in the same value for $\pi$.
Thank you in advance for helping me out.
Fixed it. I have been allowed include information about the basic variables. The answer to this question is that it is not possible to split the A matrix with the information given, iterating through for each combination is an expensive approach, but only applies if combinations are non degenerate, that is each variable has a unique constraint vector so that $\pi^T$ is unique.