instance found to be infeasible but it isn't if run without presolve or run with cbc

[douglaswaynepotter]

HiGHS reports that the attached instance is infeasible, but if I run with the presolver off it finds the same optimal objective function value of -18 just like cbc.

The logs attached logs were produced by running:

highs --presolve on small_cost_model.mps > presolve_on.log
highs --presolve off small_cost_model.mps > presolve_off.log
cbc  small_cost_model.mps > cbc.log

I've reproduce this issue on the commit

Merge: f01e22887 0b0282155
Author: galabovaa <[email protected]>
Date:   Thu Dec 15 17:18:08 2022 +0200

    Merge pull request #1048 from ERGO-Code/revert-1041-fix-1038
    

and I've also seen it on 1.4.1. insstance_and_logs.zip

[jajhall]

Thanks. I've reproduced this behaviour. I'll ask the developer of our MIP presolve/solver to look into it.

[fwesselm]

Some of the equality constraints in the model are poorly scaled. I think this may lead the presolve code to fix variables to incorrect values. For example, equality constraint 'r726' in the MPS file looks as follows:

c78    1
c115   -1
c273   -499284000
c274   -499284000
c275   -499284000
c276   -499284000
c277   -499284000
c278   -499284000
c279   -499284000
c280   -499284000
c281   -499284000
c282   -499284000
c283   -499284000
c284   -499284000
c285   -499284000
c286   -499284000
c287   -499284000
c288   -499284000
c289   -499284000
c290   -499284000

c78 = c115 + 499284000 * c273 + 499284000 * c274 + ...

where 0 <= c78 <= 1296000000 and 0 <= c115 <= inf are continuous variables and the remaining variables are binary.

When the constraint is divided by 499284000 the coefficients of the two continuous variables get really small and may be interpreted as zero. Thus, the equality constraint may then effectively force all the binary variables to zero.

I am sure the code can be improved to detect large dynamism in constraints and avoid such numeric operations.

On my side the optimal solution is also found when I reduce the value for option 'small_matrix_value'.

[jajhall]

On my side the optimal solution is also found when I reduce the value for option 'small_matrix_value'.

That's interesting. This option was set up to filter small values from data supplied by users. However, I know that it's used in the presolve to take decisions on how small a value is, or how close to another value. At the very least we should have these uses controlled by independent option values.

Also, it would seem valuable to flag up instances of excessive scaling so that their consequences can be investigated.

@fwesselm I appreciate your contributions this week. As you can see in #1077, we no longer have our MIP presolve/solve developer and there are several outstanding issues (mainly in presolve) that will be hard to fix until someone can get to grips with the details of the MIP presolve/solver.

[douglaswaynepotter]

@fwesselm nice analysis. From a practical stand point, I used HiGHS successfully to solve very similar instances (also with similar differences in coefficient magnitudes) so I didn't work on improving the scaling. Maybe I missed some feedback about the scaling possibly affecting the presolver in the logs. If not, that would be a nice addition.

[jajhall]

I don't think that the presolve is looking at the consequences of poor scaling, so you've not missed anything @douglaswaynepotter, and I'm pleased to hear of your successful use of HiGHS. The MIP solver has been mainly developed in relation to the MIPLIB 2017 test set of 240 problems, and is very successful on them, so it's pretty robust.

I'll have a look at the behaviour identified by @fwesselm in due course, but I'm busy with creating documentation for HiGHS and teaching until Easter