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:
http://www.gurobi.com/resources/faqs

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.