Avoid Rounding of Input

A common source of numerical issues is numerical rounding in the numbers that are used to represent constraint matrix coefficients. To illustrate the issue, consider the following example:

\[\begin{split}\begin{array}{rcl} x - 6y &=&1\\ 0.333x - 2y &= & .333 \end{array}\end{split}\]

It may be tempting to say that the two equations are equivalent, but adding both to a model will lead to an incorrect result. This is an important point for our users: Gurobi will always trust the input numbers that they provide, and will never change them unless the change can be shown to not affect the solution.

So, with this in mind, during presolve Gurobi can use the second constraint to determine:

\[y := 0.1665x - 0.1665\]

When substituted into the first constraint, this yields

\[\begin{split}\begin{array}{rcl} x - 6\cdot(0.1665x - 0.1665) &=& 1\\ \Leftrightarrow 0.001x &=& 0.001 \end{array}\end{split}\]

and thus \(x = 1,\ y = 0\) as the only solution.

If user had provided these two equations instead:

\[\begin{split}\begin{array}{rcl} x - 6y&=&1\\ 0.3333333333333333x - 2y&=&0.3333333333333333 \end{array}\end{split}\]

this would give:

\[y := 0.1666666666666667x - 0.1666666666666667\]

which yields:

\[\begin{split}\begin{array}{rcl} x - 6\cdot(0.1666666666666667x - 0.1666666666666667) &=& 1\\ \Leftrightarrow 2\cdot10^{-16} x + 1 + 2\cdot10^{-16} &\approx& 1 \end{array}\end{split}\]

Even with a very small threshold for treating a coefficient as zero, the result here is that the first constraint is truly redundant. Any solution with \(x = 6y + 1\) would be accepted as feasible.

The main point is that constraints that are exactly parallel, or linearly dependent (within double-precision floating-point and small tolerances) are harmless, but constraints that are almost parallel to each other produce tiny coefficients in the linear system solves and in preprocessing, which can wreak havoc on the solution process. In the next section, we expand on the limits double-precision floating-point numbers, and in particular why \(1\approx 1+2\cdot10^{-16}\).