How is the feastol parameter used in inequalities?

Question

I'm solving a MIP for which SCIP prints the following after solving:

violation: right hand side is violated by 4.00681341261588e-06
best solution is not feasible in original problem

optimal solution found

Indeed there are some constraints that are violated in the output solution. I played with the following tolerances, as I read somewhere that this controls the violations:

numerics/feastol = 1e-9
numerics/lpfeastol = 1e-9
numerics/sumepsilon = 1e-9

However, it seems the constraint is always violated by about 1e-6, no matter what the above parameters are.

I would like to know more on how does this parameter is used for a constraint of the type A*x <= B. Is this used for precision, or accuracy? That is,

A* |x-tol| - B <= 0

or

A*x - B <= tol

or something else?

Thanks!

Answer 1

for linear constraints, the relative difference between the activity of the constraint (A*x) and the right hand side (B) is computed as

Changing numerics/feastol would require this difference to be closer to zero in order for a solution to be accepted.

However, in your case, the issue is that a solution is found that is feasible in the transformed problem (changed through presolving and various other fixings) but not in the original problem. This could either be a bug in SCIP (if you are able to share a file of your problem instance, I could look into this) or it could be due to aggregation of small numerical errors. What SCIP version are you using? (switching to a more recent one might also solve your problem)

If your problem is not very challenging you can try to solve it without presolving by setting

set presolving emphasis off

in the SCIP interactive shell.

Happy SCIPing, Leon