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.
I wonder if the integrality tolerance is applied to the presolved model rather than the original model?
ReplyDeleteI also wonder why solvers report fractional values, rather than rounding the final values of integer variables to the nearest integer and then recomputing objective values, slacks etc. Perhaps the latter is too much work on large models; but with a big-M constraint, 8e-6 can be substantially different from 0.
+Poul Rubin: One reason for not rounding the integer variables is if the optimal basis is very ill-conditioned, then the recomputed basis variable may be vastly outside their bounds. Users would not like that and it would be hard to explain them what wrong. Also as you say the objective gap may no longer be satisfied after rounding.
ReplyDeleteNote some optimizers (including MOSEK) can fix the integer variables at their optimal value and then reoptimize. Usually with the purpose so to get some dual variables. In our first implementation at MOSEK we rounded the integer variables but the problem in some ill-conditioned cases got infeasible. So we stopped doing that.
To clarify what I meant, I was thinking of rounding the solution passed to the user, not the solution to the presolved model. A typical user is going to look at epsilon or 1-epsilon and think 0 or 1 anyway, so why not display that value and the slacks etc. corresponding to that value? Speaking to Ed's point, if the solver finds a value that is 0 to within integrality tolerance but would cause bound violations if it were truly 0, reporting it as 0 with a caveat that it's actually not feasible (and with a little boilerplate explanation - this confuses a lot of users) would IMHO be preferable to reporting a "feasible" epsilon and letting the user make it 0 without realizing that causes the model (and possibly the universe) to implode.
DeleteIt's a very tricky issue. Consider the following constraint...
ReplyDelete100000 x = 1 (x binary)
This is of course infeasible if you insist on strictly integer values, and feasible if you allow x=1e-5. While you may have a clear sense of which answer is 'right' when the constraint is this simple, you often wind up with very similar types of constraints after applying presolve (particularly aggregation) to more complex constraints. The question of which answer is 'right' then becomes a lot more subtle.
In my experience, allowing the user to specify a 0 integrality tolerance gives false comfort. You often fail to actually deliver it, so why promise it?