Hidden feasibilityTol during solve, more strict than default?

[ChristianW]

Hello,

I was having trouble with infeasibility of some/most of my models (solving a series of LP in rapid succession for a simulation). Out of my colleagues, I was the only one experiencing this, even though we use exactly the same code for building and using the models. We might use different gurobi versions though, as I recently upgraded to Gurobi 8.0.1(Java, win64).

On detailed analysis with IIS, model.write() and adapting feasibilityTol I discovered a couple of things:

• My models do solve when I increase the feasibilityTol from the default to 10^-4 or sometimes 10^-5. From the Gurobi handbook I learned that the default value is 10^-6. 
  
• The models of my colleague appear to be the same as mine but he does not experience infeasibility with the default value. He does use an older version of Gurobi, specifically 6.5.2.
  
• When looking at the IIS-constraints in the model-printouts, there are in fact infeasible constraint combinations. However, the error in feasibility (i.e. "too stringent constraints") is only in the 7th or 8th digit behind the comma and should therefore be ignored due to the default feasibilityTol. There are more constraints that are incorrect at the 14th digit but these never trigger the IIS. (The constraint errors were probably caused by an unnecessary float-cast from a double. Taking this cast away reduces the error to the 14th digit or lower.)
  

--> Since my colleague’s model is exactly the same and is feasible, apparently the new Gurobi does not actually apply its default feasibilityTol while the old version did.

Does this make sense? Are there multiple feasibilityTol-values in use after Gurobi 6.5.2?

For completeness here is an example of the specs of an infeasible attempt as printed by gurobi:

Gurobi 8.0.1 (win64, Java) logging started 08/03/18 14:32:26


Academic license - for non-commercial use only

Optimize a model with 5169 rows, 2520 columns and 10080 nonzeros

Coefficient statistics:

  Matrix range     [1e+00, 7e+03]

  Objective range  [8e+03, 2e+05]

  Bounds range     [0e+00, 0e+00]

  RHS range        [1e-01, 1e+05]

Presolve removed 5082 rows and 1750 columns

Presolve time: 0.00s

Presolved: 87 rows, 770 columns, 1512 nonzeros



Iteration    Objective       Primal Inf.    Dual Inf.      Time

       0    9.7192584e+06   6.665029e+03   0.000000e+00      0s

Extra 24 simplex iterations after uncrush


Solved in 142 iterations and 0.02 seconds

Infeasible model

       0   -1.7774525e+34   1.333352e+32   1.777453e+04      0s


IIS computed: 25 constraints and 0 bounds

IIS runtime: 0.02 seconds

Thanks and best regards  

Christian

[Tobias Achterberg]

You have a misconception about what the feasibility tolerance means.

If you set the feasibility tolerance to some value, say eps, it does *not* mean that
constraint violations of up to eps should always be considered feasible. In other words,
for <= constraints using a feasibility tolerance of eps is *not* equivalent to just adding
eps to all right hand side values.

Instead, the feasibility tolerance defines a gray zone in which the solver can arbitrarily
declare a solution feasible or infeasible. In other words:

1. A solution that is feasible in exact arithmetics should always be declared feasible.
2. A solution that violates some constraint by more than eps should always be declared
infeasible.
3. A solution that is infeasible in exact arithmetics but has a maximum violation of at
most eps can either be declared feasible or infeasible.

If you are within the gray zone, then it greatly depends on where in the solving process
such a small infeasibility is encountered. For example, presolve reductions may declare a
model to be infeasible even though a solution with just a small violation exists. On the
other hand, the simplex algorithm will typically accept slightly infeasible solutions and
only declare a model to be infeasible if it is "really" infeasible.


With an infeasible model that is at the border of feasibility, you can experience
arbitrary different results if you change algorithmic settings (like changing the Gurobi
version number, or even just changing the random seed parameter). And the surprising fact
is: due to the definition of the feasibility tolerance, *both* answers are be correct. The
answer "infeasible" is correct, as the model is truly infeasible (in exact arithmetics).
The answer "feasible" is also correct, as there exists a solution that violates the
constraints by at most the feasibility tolerance.


Best regards,

Tobias