Adding constraint makes problem feasible

[robertHowlett]

I have a problem which should be feasible, but isn't.

infeasible.mps.txt

Solver output

WARNING: There are empty or excessively-long column names: using constructed names with prefix "c"
WARNING: There are empty or excessively-long row names: using constructed names with prefix "r"
MIP  has 92 rows; 103 cols; 335 nonzeros; 26 integer variables (26 binary)
Coefficient ranges:
  Matrix [8e-04, 1e+02]
  Cost   [8e-01, 8e+01]
  Bound  [1e+00, 1e+00]
  RHS    [1e-01, 1e+03]
Presolving model
63 rows, 76 cols, 258 nonzeros  0s
44 rows, 55 cols, 198 nonzeros  0s
28 rows, 48 cols, 132 nonzeros  0s
28 rows, 15 cols, 40 nonzeros  0s
Presolve: Infeasible

Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic; L => Sub-MIP;
     P => Empty MIP; R => Randomized rounding; S => Solve LP; T => Evaluate node; U => Unbounded;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point; X => User solution

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

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

Solving report
  Status            Infeasible
  Primal bound      inf
  Dual bound        -inf
  Gap               inf
  P-D integral      0
  Solution status   -
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 0
  Nodes             0
  Repair LPs        0 (0 feasible; 0 iterations)
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

I can add an additional pair of constraints, which makes it feasible.

feasible.mps.txt

I am running WIndows 11 and using highspy 1.10.0 and pulp 2.9.0. The only option I'm specifying is gapRel=1e-4.

Any idea on how to fix this?

[jajhall]

Thanks, I've reproduced this. gapRel=1e-4 AKA mip_rel_gap=1e-4 is the default value

Interesting one @fwesselm: feasible.mps is reduced to empty so, since it's got two fewer constraints, infeasible.mps should also reduce to empty. However, presolve claims infeasibility when the reduced MIP is quite small.

[robertHowlett]

Now simplfied to 35 rows; 30 cols; 81 nonzeros; 2 integer variables (2 binary)

feasible_2.mps.txt

infeasible_2.mps.txt

[jajhall]

Now simplfied to a nearly minimal 35 rows; 30 cols; 81 nonzeros; 2 integer variables (2 binary)

Thanks: the smaller the better for debugging!

[fwesselm]

Now simplfied to a nearly minimal 35 rows; 30 cols; 81 nonzeros; 2 integer variables (2 binary)

Thanks: the smaller the better for debugging!

I would like to have a look, but I am away until April 28.

[jajhall]

Now simplfied to a nearly minimal 35 rows; 30 cols; 81 nonzeros; 2 integer variables (2 binary)

Thanks: the smaller the better for debugging!

I would like to have a look, but I am away until April 28.

Thanks, @fwesselm, I'll have a look myself then