Infeasible MIP reports status optimal with presolve

[jens-diewald]

Hi everyone! Thank you for your work on this great project.

I have recently done some testing with HiGHS 1.7.0 on Windows. I ran into the issue, that for some infeasible MIPs, the solver reports ModelStatus optimal and HighsSolution::value_valid is true, when presolve is turned on.
When presolve is turned off, infeasible is reported and HighsSolution::value_valid is False, as expected.

This may be related to #942, as I get the same Warning from presolve?

I have attached a very small MPS file to reproduce the problem: dump.mps.txt
Python code and output demonstrating the problem:

>>> import highspy
>>> h = highspy.Highs()
>>> h.readModel("dump.mps")
Running HiGHS 1.7.0 (git hash: 50670fd4c): Copyright (c) 2024 HiGHS under MIT licence terms
Number of BV entries in BOUNDS section is 1
Number of UI entries in BOUNDS section is 4
<HighsStatus.kOk: 0>
>>> h.run()
Coefficient ranges:
  Matrix [1e+00, 2e+00]
  Cost   [1e+00, 1e+00]
  Bound  [1e+00, 3e+00]
  RHS    [2e+00, 3e+00]
Presolving model
3 rows, 5 cols, 11 nonzeros  0s
0 rows, 0 cols, 0 nonzeros  0s
Presolve: Optimal
WARNING: Solution with objective 2 has untransformed violations: bound = 0; integrality = 0; row = 1 (row 2[r0000002])

Solving report
  Status            Optimal
  Primal bound      2
  Dual bound        2
  Gap               0% (tolerance: 0.01%)
  Solution status   infeasible
                    2 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    1 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)
ERROR:   MIP solver claims optimality, but with num/max/sum primal(2/1/2) infeasibilities
<HighsStatus.kOk: 0>
>>> h.getSolution().value_valid
True
>>> h.clearSolver()
<HighsStatus.kOk: 0>
>>> h.setOptionValue("presolve", "off")
<HighsStatus.kOk: 0>
>>> h.run()
Coefficient ranges:
  Matrix [1e+00, 2e+00]
  Cost   [1e+00, 1e+00]
  Bound  [1e+00, 3e+00]
  RHS    [2e+00, 3e+00]

Presolve is switched off
Objective function is integral with scale 1

Solving MIP model with:
   3 rows
   5 cols (1 binary, 4 integer, 0 implied int., 0 continuous)
   11 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   0               inf                  inf        0      0      0         0     0.0s

Solving report
  Status            Infeasible
  Primal bound      inf
  Dual bound        inf
  Gap               inf
  Solution status   -
  Timing            0.02 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             1
  LP iterations     3 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)
<HighsStatus.kOk: 0>
>>> h.getSolution().value_valid
False

[jajhall]

Sorry for the previous comment: it was related to #1704

I've reproduced this, and it's for a shockingly small MIP - which makes working on it easier!

Maybe it's related to #942: I can live in hope!

[jajhall]

Note to @jajhall: It's caused by the last of 9 presolve reductions.

[jajhall]

After 8 reductions, problem is $$min\quad x\quad s.t. -1\le x \le-1; x \in[0,1,2]$$

Infeasibility is being detected when handling the singleton row, but not acted on

[jajhall]

Fixed by #1719