Incorrectly detected infeasibility when using presolve

[apfelix]

Hi,

the following model is incorrectly declared to be infeasible. If I turn off pre-solve a feasible solution is found. highs_model_for_debugging.mps.txt

Tested via highspy on versions 1.7.2 and branch latest.

PS: Sorry for the size of the problem. I didn't manage to reproduce it on a smaller instance. The model actually contains a lot of fixations via constraints of the form binary_var = 0 or binary_var = 1, which come from a specialised heuristic. Hence, presolve actually is quite important here and reduces the number of variables and constraint roughly by a factor of 6 or 7.

[fwesselm]

Couple of observations:

1. I can reproduce this on Windows with the latest branch.
2. When using presolve and setting mip_feasibility_tolerance to 1e-9, the problem is solved to optimality with optimal objective value 1.
3. When presolve is off and default mip_feasibility_tolerance is used, the problem is solved with optimal objective value 1 as well.
4. When presolve is off and mip_feasibility_tolerance is set to 1e-9, HiGHS reports an optimal objective value of 168 and the message: WARNING: MIP solver claims optimality, but with num/max/sum primal(113/4.85402e-08/7.14111e-07) infeasibilities

[apfelix]

@fwesselm Thanks for the analysis. I didn't expect that lowering the mip_feasibility_tolerance tolerance would resolve both this issues as well as #1959 . It also fixed all the other (unreported) instances with these two problems in our internal tests. Huge thanks for that hint, this is a proper lifesaver :)

[jajhall]

The only health warning is that 1e-9 is very small - 1e3 below the default - so there may be unintended consequences on other MIPs

[apfelix]

A short update: Some weeks ago, we updated the scaling of some of the constraints in the model generation for our application. On a larger test set of instances (400+) similar to the one reported here, this change really improved the results we got with HiGHS (v1.8.1, default settings): We didn't observe any unexpected claims of "infeasibility" anymore and could also improve the overall solver performance.

With the updated model, the instance of this issue is now successfully solved with HiGHS (v1.9.0).

So the numerics in the originally submitted .mps file are probably disadvantageous. The same holds for the models submitted in #1959 and #2033.

[jajhall]

That's good to hear. Better scaling is always a good idea, but it can be hard to achieve for some modellers, so we'll still have folk posting problems with the behaviour that you observed previously.