Suppose we have the following LP problem: $$min\ C^Tx $$ $$s.t. \ Ax = b $$ $$x>=0$$
I am trying to confirm that an optimal solution $x^*$ obtained from an LP solver for such a problem is optimal. To do so, I am calculating the reduced cost and checking it is non-negative. $$Reduced \ cost = C-\pi A$$ $$where \ \pi = C_bB$$ $ C_b$: entries in C corresponding to the basic optimal variables
$B$: the optimal basis (i.e., columns form A corresponding to the basic optimal variables)
As you see, to construct the basis matrix $B$, the basic optimal variables need to be identified. I am identifying the basic optimal variables as those variables in $x^*$ that are $ > 0$.
The issue is that sometimes, variables in $x^*$ that are $ > 0 $ are less than the needed number of basic variables (the needed number of basic variables is the number of constraints in the problem). Hence, some basic optimal variables $= 0$ in the optimal solution which indicates degeneracy. In this case, how can I build the matrix B to confirm optimality? Can I arbitrary chose any variable and consider it as a basic optimal variable?
Thank you.
