Incorrectly detected infeasibility for non-default parameters

[apfelix]

Hi,

I currently use highs with mip_feasibility_tolerance of 1e-09 as a work around for #1958 and #1959 and encountered some inconsistent behaviour for the attached model inconsistent_behaviour.mps.txt

In default settings, highs determines an optimal solution (in presolve). This is the result I expect for the model.

However, for a mip_feasibility_tolerance of 1e-09 presolve detects Infeasible. If I turn off presolve, HiGHS still detects Infeasible (in case of using the default mip_feasibility_tolerance as well as in the case of using 1e-09).

I tested this via highspy on versions 1.7.2, 1.8.0 and on latest.

Gurobi 11.0.3 confirms feasibility (also within presolve) with defaults settings as well as with an IntFeasTol of 1e-9. SCIP 9.1.0 also finds a solution (not within presolve).

[jajhall]

As I suggested previously, using 1e-9 as the 'integer_feasibility_tolerance' is asking for trouble.

Hence the error with 1e-6 as the 'integer_feasibility_tolerance' is the one to focus on

[odow]

Hi @apfelix, take a read of this tutorial I wrote for the JuMP documentation: https://jump.dev/JuMP.jl/stable/tutorials/getting_started/tolerances/

It includes an explanation for why you get inconsistent feasibility detection, including why presolve is important.

[apfelix]

Hi @odow, thanks for the link. From my point of view, a summary of the part relevant for this issue would be:

Tolerances and presolving may influence the feasibility/infeasibility of a given problem:

• Larger tolerances increase the feasible region and, as a consequence, may change the result from infeasible to feasible
• Presolving in general works with zero tolerances (at least for logical deduction based on binary variables). Therefore, it decreases the feasible region (compared to the original problem) and may change the result from feasible to infeasible if switched on

Given that summary, it makes sense if HiGHS reports for a given problem (like the one posted above) a feasible solution for the default tolerances and infeasible for a smaller tolerance. However, I don't see how turning off presolving should make the problem infeasible (at least from a theoretical point of view that disregards floating-point errors).

[jajhall]

Presolve uses nonzero tolerances.

[odow]

@apfelix did you write that quoted text or did you copy it from somewhere? That is not a summary to take from the JuMP tutorial.

My summary would be: there are models for which there is no simple answer as to whether the problem is feasible or infeasible (https://jump.dev/JuMP.jl/stable/tutorials/getting_started/tolerances/#Contradictory-results). And if you have such a problem, changing the tolerances (especially making the tolerances very tight like 1e-9) is not a magic panacea that will fix things. You need to reformulate your model to make it less susceptible to numerical issues. See the problem scaling section: https://jump.dev/JuMP.jl/stable/tutorials/getting_started/tolerances/#Problem-scaling

[jajhall]

The switch to 1e-9 was a lucky way of avoiding a bug in presolve when solving a problem that is numerically tricky. I warned @apfelix that it was likely to be a bad idea for other MIPs

Your advice is wise and welcome @odow

[rschwarz]

Just to clarify: "Numerically tricky" and "no simple answer as to [feasibility]" doesn't mean that the problem is "barely" feasible, right? ~This could be a local issue with some constraints/coefficients while the problem might actually have solutions that leave significant slack to both bounds and inequalities.~ (UPDATE: Never mind, the presence of equations in the formulation makes this question a bit silly in this context.)

We're aware of potential problems in particular with big-M constraints and have applied variable scaling based on change of unit, but there are still moderate ranges of coefficients in the problem.

Thanks for the help!