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:
- Integrality of solutions, i.e., whether a integer variable takes an integer value or not. More precisely, will be considered integral if abs(x - floor(x + 0.5)) IntFeasTol.
- Feasibility of primal constraints, i.e., whether holds for the primal solution. More precisely, will be considered to hold if (a * x) - b FeasibilityTol.
- Feasibility of dual constraints, i.e., whether holds for the dual solution. More precisely, will be considered to hold if (a * y) - c OptimalityTol.
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:
- Models at the edge of infeasibility
- Gurobi tolerances and the limitations of double-precision arithmetic
- Why scaling and geometry is relevant
- Recommended ranges for variables and constraints
- Improving ranges for variables and constraints
- Advanced user scaling
- Avoid hiding large coefficients
- Dealing with big-M constraints