Documentation

Tolerances and user-scaling


Tolerances and user-scaling

Gurobi will solve the model as defined by the user. However, when evaluating a candidate solution for feasibility, in order to account for possible round-off errors in the floating-point evaluations, we must allow for some tolerances.

To be more precise, satisfying Optimality Conditions requires us to test at least the following three criteria:

IntFeasTol
Integrality of solutions, i.e., whether a integer variable $x$ takes an integer value or not. More precisely, $x$ will be considered integral if abs(x - floor(x + 0.5)) $\mathtt{\leq}$ IntFeasTol.
FeasibilityTol
Feasibility of primal constraints, i.e., whether $a \cdot x \leq b$ holds for the primal solution. More precisely, $a \cdot x \leq b$ will be considered to hold if (a * x) - b $\mathtt{\leq}$ FeasibilityTol.
OptimalityTol
Feasibility of dual constraints, i.e., whether $a \cdot y \leq c$ holds for the dual solution. More precisely, $a \cdot y \leq c$ will be considered to hold if (a * y) - c $\mathtt{\leq}$ OptimalityTol.
Note that these tolerances are absolute; they do not depend on the scale of the quantities involved in the computation. This means that when formulating a problem, these tolerances should be taken into account, specially to select the units in which variables and constraints will be expressed.

It is very important to note that the usage of these tolerances implicitly defines a gray zone in the search space in which solutions that are very slightly infeasible can still be accepted as feasible. However, the solver will not explicitly search for such solutions.

For this reason, it is actually possible (although highly unlikely for well-posed problems) for a model to be reported as being both feasible and infeasible (in the sense stated above). This can occur if the model is infeasible in exact arithmetic, but there exists a solution that is feasible within the solver tolerances. For instance, consider:

\begin{displaymath}\begin{array}{lll}
\min&0\\
s.t.&x \leq&0\\
&x\geq &10^{-10}\\
\end{array}\end{displaymath}



Subsections