Model status goes from infeasible to optimal when shutting down presolve

[lpierezan]

Description

The attached model is infeasible when run with a presolve and optimal when run without a presolve. This only happens when I lower mip_feasibility_tolerance. Is this a bug or would it be expected somehow? Thanks

(note: attached as txt to be uploaded) model_min_custo_1.txt

import highspy

for presolve in ['on', 'off']:
    h = highspy.Highs()
    h.setOptionValue('log_to_console', False)
    filename = 'model_min_custo_1.mps'
    h.readModel(filename)
    h.setOptionValue('mip_feasibility_tolerance', 1e-7)
    h.setOptionValue('presolve', presolve)
    h.run()
    print(f'Model with presolve {presolve} has status {h.getModelStatus()}')

gives

Model with presolve on has status HighsModelStatus.kInfeasible
Model with presolve off has status HighsModelStatus.kOptimal

System Information

• highspy version: 1.5.3 (with pip install)
• python version: 3.9.16
• operating system: win 11

[jajhall]

You've got a very large range in the matrix entries [2e-08, 4e+07]. If I remove just the matrix value -1.6421681309280297e-08 (five much smaller values are removed automatically when the MPS file is read in) then the optimal solution is obtained after running presolve.

If you've got matrix entries that are of the same order as the mip_feasibility_tolerance then you're taking a risk.

I don't think that it's a bug

[lpierezan]

Hi @jajhall , thanks for your time!

And what about this model:
model_min_custo_368.txt

The matrix coefficients are better.

Both Gurobi and SCIP returns optimal status, even with integer tolerance about 1e-7. HiGHS gives optimal solution only if presolve is disabled.

[jajhall]

Thanks for the instance. I can probably identify the presolve reduction that causes the problem

I can believe that SCIP is more robust. If this is more important than speed, then switch to SCIP.

[lpierezan]

Thanks for the instance. I can probably identify the presolve reduction that causes the problem

I can believe that SCIP is more robust. If this is more important than speed, then switch to SCIP.

Interestingly, for some instances HiGHS is consistent and SCIP is not: https://github.com/scipopt/PySCIPOpt/issues/778

There are also cases where running highspy through pyomo gives me an infeasible status, but when converting the pyomo model to mps and running highspy directly I obtain an optimal solution.

I'm working to make the model formulation more palatable.

[jajhall]

If you're on the edge of good/bad solver behaviour, rounding may play a part. Clearly there's no rounding when you avoid the use of an MPS file.

Improving the formulation of you model would seem wise but, as a solver developer, I would say that! :D

[jajhall]

With the MPS file from JuMP, it's solved fine with/without presolve, but with the .lp file from JuMP, I reproduce the issue.

Now I can investigate

[fortsnek9348]

Another example, with mostly small integer values as coefficients.

Civ4 30 turns.txt Civ4 100 turns.txt

Rename to "lp" files. The 30 turns variant is solvable with presolver on. The 100 turns variant is infeasible with presolver on and solved to optimality with presolver off.

Highs Log.txt

[jajhall]

It's a bug in presolve. Thanks for raising it

[fwesselm]

I think reduction number 5144 is causing this. The model is solved to optimality with reduction limit 5143:

highs.setOptionValue("presolve_reduction_limit", 5143);

But it is infeasible when setting it to 5144:

highs.setOptionValue("presolve_reduction_limit", 5144);

@jajhall, are you looking into this issue? If not, I could debug it, but I may be slow in doing so.

[jajhall]

I'm not looking into this at present, as I'm preparing to leave for ISMP. Once I'm back (on 29/07) I'll have a lot of time for MIP work.