Incorrectly detected infeasibility with pre-solve turned off

[apfelix]

Hi,

as a workaround to #1958 I started using HiGHS with pre-solve turned off.

However, I found a model model for which infeasibility is reported when pre-solve is turned off: highs_model_for_debugging_infeasible_with_presolve_off.mps.txt Tested via highspy on version 1.7.2 and branch latest.

A solution is found by

• turning on pre-solve
• using SCIP
• using Gurobi

In contrast to #1958 I was able to find an instance with <1000 vars and constraints.

[fwesselm]

I can reproduce this using the latest branch. However, the problem is solved to optimality when I reduce the mip_feasibility_tolerance:

highs.setOptionValue("mip_feasibility_tolerance", 1e-09);

[apfelix]

@fwesselm Thanks for the check and also the tip with the feasibility tolerance. This helps a lot as a work-around!

[rschwarz]

To make sure I understand this correctly: Changing the feasibility tolerance from 1e-6 (the default) to 1e-9 actually means that HiGHS is more strict when evaluating solution candidates, right? So there are candidates that would be rejected with 1e-9 but accepted as feasible with 1e-6.

It is somewhat counter-intuitive to me that this change would help find a solution (and not declare the problem infeasible), but maybe some bound propagation steps (or similar) are performed in a more conservative fashion with the restrictive tolerance.

[jajhall]

Any perturbation to the MIP solver can change the way it behaves. It may well be that reducing the feasibility tolerance means that the state in which infeasibility was previously declared incorrectly doesn't occur.

Try running with different values of random_seed as an indication of how the code can run differently.

[Opt-Mucca]

For future reference: It seems the issue for this instance is that HiGHS finds the original root LP infeasible. That is at least not directly from bound changes or from cuts (don't even think a single one is applied). It is simply that the original LP is infeasible. Not sure why the LP then becomes feasible when mip_feasibility_tolerance is set to a smaller value......

Not sure on how to approach a fix because I can't figure out how to print the local model....... The error can consistently be recreated with hash b08c78434 for looking into this later.