Free Vars and Dense Cols

[Rolando Bettancourt]

Hi all,

Could you please explain a bit further about Free Vars and Dense Cols and how to deal with them? I'm using Barrier as I have multiple cores. The info in the Gurobi reference manual about this is really really brief.

Is there any relationship with PreSolve?

Thanks!

-Rolando

[Rolando Bettancourt]

By the way, my model only contains binary variables.

Thanks,

-Rolando

[Robert Luce]

Hello Rolando,

normally neither free variables (variables lb==-inf and ub==inf) nor dense columns (columns of the constraint matrix A with "many" nonzero elements) present a problem that you should be worried about too much.  We include these two pieces of information in the barrier statistics output only for informational purpose, and to aid debugging unusual performance behaviour of the barrier algorithm.

The background of these two particularities is related to the algorithmic core of the barrier algorithm, and it is rather technical. In brief, the KKT system stemming from primal, dual, and complementarity considerations suggests solving a linear system with the matrix A*A'.  Now if A has a dense column, the latter matrix will have a dense submatrix, which makes solving the linear system costly. Free variables, make it difficult to assert positive definiteness of A*A'.

Gurobi has some algorithmic machinery in place to deal automatically with dense columns and free variables. If you observe unsusual performance patterns of the barrier algorithm, the shown statistics on free variables and dense columns are simply gentle reminders that these could play a role.

As said initially: usually you won't have to worry about them!

Robert

[Rolando Bettancourt]

Thank you Robert,

Any chance you can help me take a look at the MIP I'm working on? After the last Gurobi's "numerical issues" webinar. I was in contact with Daniel Espinoza who previously mentioned something about free variables, but he went on vacation and he could not look further. The link is still up on the "Numerical Issues and Presolve" question I asked a few weeks ago.

Thanks again,

-Rolando