Unexpected rouding errors

[Michael Holzhauser]

Hello everyone,

I'm currently struggling with an big-M constraint that seems to be ignored by Gurobi (6.0.4 with Python 2.7) in some cases.

The constraint has the form

x <= M * y

where x is a non-negative continuous variable, M a large number and y a binary variable. The binary variable y should be 1 whenever x is positive.

The problem is that for small but significant values for x, Gurobi computes solutions with y=0.

In particular, in my case, M = 4519.5036. For values like x=0.032939, x=0.029578, or x=0.026255, everything works fine and Gurobi sets y=1. However, for values like x=0.0229317, x=0.0196083, or x=0.016617, Gurobi computes solutions with y=0. So the error already occurs in the 2nd decimal digit.

I assume that Gurobi is struggling with precision at this point. After optimization, it outputs the following warning:

Warning: max constraint violation (3.4856e-02) exceeds tolerance (possibly due to large matrix coefficient range)

which may explain the error. Before I reformulated several constraints, Gurobi also printed out a warning that the matrix coefficient range is very large:

Warning: Model contains large matrix coefficient range. Consider reformulating model or setting NumericFocus parameter to avoid numerical issues.

The current stats of the model look as follows:

Optimize a model with 647954 rows, 406705 columns and 5730415 nonzeros

Coefficient statistics:

 Matrix range    [4e-06, 4e+05]

 Objective range [2e-01, 1e+00]

 Bounds range    [1e+00, 2e+04]

 RHS range       [7e-04, 1e+05]

As suggested in the warning message, I tried to set NumericFocus to the maximum of 3. However, besides an increased running time, there was no difference in the result.

So, do you have any suggestions on how to avoid these numerical issues?

Thanks in advance.

P.S.: A dirty workaround like 100*x <= 100*M*y leads to correct results.

[Renan Garcia]

Note that y can be as large as 1e-5 while still considered integral and "zero", due to the default setting for the IntFeasTol parameter (see http://www.gurobi.com/documentation/6.0/refman/intfeastol.html). Therefore, x can actually be as large as 0.045196036 in your case without violating the default value for the FeasibilityTol parameter, which is 1e-6 (see http://www.gurobi.com/documentation/6.0/refman/feasibilitytol.html).

If you need better precision, some workarounds include decreasing M (if possible), decreasing IntFeasTol, or switching to an SOS formulation to handle the constraint with branching. For example, you could introduce a new binary variable, z, and represent your constraint as

  x <= M

  y = 1 - z

  SOS1: x, z

--

---
You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.