By Dr. Timo Berthold

Wow, already the fifth blog in this series…What is left to tell about numerics? Quite a bit, actually!

In my previous blogs, we have mainly concentrated on tiny (or not so tiny) violations in the feasibility of linear constraints and optimality conditions. In case you missed my previous posts, we have discussed:

• Where such inaccuracies come from and why some of them are unavoidable (to a certain extent)
• How we can recognize whether a model is prone to numeric errors
• How we can avoid many inaccuracies by automatically learned scaling operations
• How we can fix the remaining inaccuracies a posteriori by a refinement procedure

However, there is another place where a MIP solver can sneak in minor violations that we have not yet discussed: The integrality conditions.

As with many other decisions in numerical software, the judgment of whether a particular value should be considered integral or not is subject to a threshold. For the Xpress Optimizer, this is MIPTOL, which is set to 5e-6 by default. This threshold implies that, e.g., all values between 41.999995 and 42.000005 will be treated as if they were integral, given that they are at most 0.000005 away from an integer value, namely 42.

Figure 1.

Take a look at Figure 1 and judge for yourself. When zooming in on what seems to be an integer vertex of the polyhedron, should this point be considered a feasible solution (because the vertex should have been integer) or not (because the point is outside the polyhedron)?

You might wonder where such slightly off-integer solution values for integer variables might come from in the first place. Of course, when branching on integer variables, the solver will fix them to precise integer values. However, when an unfixed variable happens to be (almost) integer in an LP solution, the value might be slightly off. After all, the LP solver is agnostic to integrality information; the solution value is the result of resolving a system of equations that might involve values that had to be truncated due to floating-point representation.

In most situations, this is just fine, and the values can be safely rounded to an integer value afterward. But in some extreme cases, moving a variable by a tiny bit might introduce an infeasibility at another place….

To learn more about an example of this, read the full post of Numerics V: Integrality – When Being Close Enough is not Always Good Enough here.