Try our new documentation site (beta).

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:

<span>$</span>\begin{array}{rcl}
x - 6y &=&1\
0.333x - 2y &= & .333
\end{array}<span>$</span>
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:

<span>$</span>y := 0.1665x - 0.1665
<span>$</span>
When substituted into the first constraint, this yields
<span>$</span>\begin{array}{rcl}
x - 6\cdot(0.1665x - 0.1665) &=& 1\
\Leftrightarrow 0.001x &=& 0.001
\end{array}<span>$</span>
and thus <span>$</span>x = 1,\ y = 0<span>$</span> as the only solution.

If user had provided these two equations instead:

<span>$</span>\begin{array}{rcl}
x - 6y&=&1\
0.3333333333333333x - 2y&=&0.3333333333333333
\end{array}<span>$</span>
this would give:
<span>$</span>y := 0.1666666666666667x - 0.1666666666666667
<span>$</span>
which yields:
<span>$</span>\begin{array}{rcl}
x - 6\cdot(0.1666666666666667x - 0.1666666666666667) &=& 1\
\Leftrightarrow 2\cdot10^{-16} x + 1 + 2\cdot10^{-16} &\approx& 1
\end{array}<span>$</span>
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 <span>$</span>x = 6y + 1<span>$</span> 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 <span>$</span>1\approx 1+2\cdot10^{-16}<span>$</span>.

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License
Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Academic License
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Search

Gurobi Optimization