why do gurobi generate slack variables?

The problem is degenerate. There are multiple optimal bases that give the same primal solution. In other words, some variables are basic at bound. This happens a lot in practice and you should not worry about that.

To make things more complicated: there are also multiple optimal primal solutions; so we say that we have both primal and dual degeneracy.

My question is, why Gurobi generates slack variables even with rank(A)=4?

The LP problem, for solvers like Gurobi (i.e. not a tableau solver), has n structural variables and m logical variables (a.k.a. slacks). The slack variables are implicit, they are not “generated” (in the sense that the matrix A is physically augmented with an identity matrix). Again, this is not something to worry about.

And how to get an optimal base that contains only the original variables (variables from x0 to x7)?

Well, this is an optimal basis. So why would Gurobi spend time and do more pivots to try to make all slacks non-basic? AFAIK no solver would do that. They treat structural and logical variables as equals.

It is not so easy to force variables to be in the basis. A free variable will most likely be in the (optimal) basis (but no 100% guarantee). You can also specify an advanced basis for Gurobi to start from. In the extreme: if this advanced basis is optimal (and feasible) Gurobi will not do any pivots.

I believe this particular problem has 83 optimal (and feasible) bases. Only one of them has all slacks NB. I don’t think it is easy to find this solution, even if you would have access to a Simplex code and can change it so (after finding an optimal solution) it continues pivoting slacks out of the basis. I think you would need to enumerate optimal bases (explicitly or implicitly).

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top