Tuesday, November 6, 2012

Gurobi integer feasibility tolerance

The integer feasibility tolerance determines when a fractional variable can be considered “automatically” integer during the branch-and-bound search. Gurobi allows this to be set as tight as 1.0e-9 (option IntFeasTol). But a client gets the following:

> I still get binary variables like 0.000008 instead of 0.

I actually believe this is a valid question. This is about 1.0e-6. Unfortunately the answer from Gurobi support is somewhat dismissive:

> This is a natural consequence of integer programming, which solves models via a series of linear programs.  See FAQ 23:

Scaling can have notorious impact on LP feasibility tolerances (e.g. the scaled model can solve to optimality, but after unscaling become very infeasible). The LP feasibility tolerance controls how much a variable can be outside its bounds before becoming infeasible (or how much an equation can be violated before becoming infeasible – this is just how much a slack can be outside its bounds). I don’t think scaling has an effect on the integer feasibility tolerance.

Note that Cplex allows a integer feasibility tolerance of zero (parameter epint). At first this seems crazy, but actually works fine in models where we need variables to be really discrete. I guess Cplex may just need to do more work in this case: we may need to branch further when a binary variable that is still fractional assumes a value of 1.0e-9.

PS: See the comments for some interesting feedback. The real question remains: why if we request an integer feasibility tolerance of 1e-9 we observe fractional parts of 1e-6.