Confusing results of MIP solving with `FeasibilityTol=1e-9`

Hi,

I have a very simple MIP instance in .lp format:

\*  *\
Minimize
OBJ: 2.88 x0
Subject To
_C1: - 58.13 x0 <= 4350.27
_C2: - 17.74 x0 <= 0
_C3: 92.9 x0 - 81.99 x1 <= 1106.82
_C4: 84.26 x0 - 20.45 x1 >= 3153.64
_C5: - 59.68 x0 + 92.23 x1 <= 3828.06
_C6: 0.97 x0 + 59.48 x1 >= 4561.63
Bounds
 -200 <= x0 <= 200
 -200 <= x1
Generals
x0
x1
End

With the default setting, Gurobi returns with the optimal solution of:

x0 = 56
x1 = 76
objective = 161.28

Sometimes I tighten FeasibilityTol to get a solution with smaller constraint violations. For this case, if I set FeasibilityTol to 1e-09, Gurobi returns with:

x0 = 57
x1 = 76
objective = 164.16

I am confused by this result. I manually check the constraints in the model, but I cannot find any violations with either group of values of the variables (all constraints are strictly satisfied with the given variable values).

Considering the potential non-deterministic (e.g., solution paths), I repeated the solving with 1000 different seeds in each setting, but always met the same issue.

I am using Gurobi 12.0.2. And both my Ubuntu server and MacBook have this issue. The log on macOS:

$> gurobi_cl seed.lp
Set parameter Username
Set parameter LicenseID to value 2670279
Set parameter LogFile to value "gurobi.log"
Using license file /Users/zxt/gurobi.lic
Academic license - for non-commercial use only - expires 2026-05-24

Gurobi Optimizer version 12.0.2 build v12.0.2rc0 (mac64[arm] - Darwin 24.0.0 24A335)
Copyright (c) 2025, Gurobi Optimization, LLC

Read LP format model from file seed.lp
Reading time = 0.00 seconds
OBJ: 6 rows, 2 columns, 10 nonzeros

Using Gurobi shared library /Library/gurobi1202/macos_universal2/lib/libgurobi120.dylib

CPU model: Apple M2
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Optimize a model with 6 rows, 2 columns and 10 nonzeros
Model fingerprint: 0x805f2cc6
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:
  Matrix range     [1e+00, 9e+01]
  Objective range  [3e+00, 3e+00]
  Bounds range     [2e+02, 2e+02]
  RHS range        [1e+03, 5e+03]
Presolve removed 6 rows and 2 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 1 (of 8 available processors)

Solution count 1: 161.28

Optimal solution found (tolerance 1.00e-04)
Best objective 1.612800000000e+02, best bound 1.612800000000e+02, gap 0.0000%
$>
$>
$> gurobi_cl FeasibilityTol=1e-9 seed.lp
Set parameter Username
Set parameter LicenseID to value 2670279
Set parameter FeasibilityTol to value 1e-09
Set parameter LogFile to value "gurobi.log"
Using license file /Users/zxt/gurobi.lic
Academic license - for non-commercial use only - expires 2026-05-24

Gurobi Optimizer version 12.0.2 build v12.0.2rc0 (mac64[arm] - Darwin 24.0.0 24A335)
Copyright (c) 2025, Gurobi Optimization, LLC

Read LP format model from file seed.lp
Reading time = 0.00 seconds
OBJ: 6 rows, 2 columns, 10 nonzeros

Using Gurobi shared library /Library/gurobi1202/macos_universal2/lib/libgurobi120.dylib

CPU model: Apple M2
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads

Non-default parameters:
FeasibilityTol  1e-09

Optimize a model with 6 rows, 2 columns and 10 nonzeros
Model fingerprint: 0x805f2cc6
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:
  Matrix range     [1e+00, 9e+01]
  Objective range  [3e+00, 3e+00]
  Bounds range     [2e+02, 2e+02]
  RHS range        [1e+03, 5e+03]
Presolve removed 2 rows and 0 columns
Presolve time: 0.00s
Presolved: 4 rows, 2 columns, 8 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)
Found heuristic solution: objective 164.1600000

Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 1: 164.16

Optimal solution found (tolerance 1.00e-04)
Best objective 1.641600000000e+02, best bound 1.641600000000e+02, gap 0.0000%

Is this phenomenon expected?

Any suggestions or explanations are appreciated! Thanks!

Riley Clement

Gurobi Staff

2025年05月26日 00:55

Hi Xintong,

Tolerances are important since our machines use floating point arithmetic. Their calculations are not 100% accurate which is why 0.1 + 0.2 = 0.30000000000000004 (see https://0.30000000000000004.com/).

If I set Presolve=0 then we still get 161.28 with FeasibilityTol=1e-9.

If I look at the presolve model I can see the constraint x0 + x1 >= 133, which of course is not compatible with a solution of x0 = 56, x1=76.

I suspect that during presolve we deduce that

x0 + x1 >= 132 + epsilon

for some tiny value of epsilon with 1e-8 ≥ epsilon ≥ 1e-9. The epsilon arises as a tiny error in calculations.

We know that since x0 and x1 are integer we can round the RHS up. If FeasibilityTol=1e-8 then the RHS is considered close enough to 132, but with FeasibilityTol=1e-9 we determine the RHS to be bigger than 132 and so round up to 133.

In summary, we need tolerances to accommodate the weaknesses in floating point arithmetic. If tolerances are too tight we may lose some feasible solutions.

- Riley

Xintong Zhou

2025年05月26日 02:01

Hi Riley,

Thanks for your explanation!

Taking the presolved model into consideration makes more sense for this case. I see what's happening now. Thanks.

Confusing results of MIP solving with `FeasibilityTol=1e-9`

コメント

お探しのものを見つけられませんでしたか？