How can I extract basic and non-basic variables from a linear programming problem using Simplex in Optimization Toolbox 3.1.1 (R2007a)?

I am trying to retrieve the basic and nonbasic variables using LINPROG with the Simplex method. I can not figure out how to do this, particularly when the problem has upper bound constraints.

Answer 1

[MathWorks Support Team]

The ability to output the basic and nonbasic variables using LINPROG is not available in Optimization Toolbox 3.1.1 (R2007a).

To work around this issue, our implementation of LINPROG can be adjusted to retrieve the indices of the basic and non-basic variables, although this has not been tested thoroughly. One has to add a line (namely, “restoreBasis = true;”) at the beginning of the 'simplexpresolve.m' and 'simplexpostsolve.m' files. The next step is to change the call to simplex.m from linprog (and also linprog output argument list) so that it can return the variables basicVarIdx and nonbasicVarIdx.

Another approach is to recover the optimal basis using the optimal primal and dual solutions. For more information on this method, refer to the paper by Nimrod Megiddo: 'On Finding Primal- and Dual-Optimal Bases', ORSA Journal of Computing, 3 (1991) 63–65.