Presolve times out for MILP problem - model solved in 4s when turning off presolver

[severinh]

We're using HiGHS heavily in our applicaiton and it works well for us. Huge thanks to the authors! We've now encountered a model where the presolver times out after 20 minutes. If we turn off the presolve, the solver solves the problem easily in 4s.

Steps to reproduce

1. Download the model.lp.zip
2. Run the model with default configuration: highs model.lp

Observed result: Presolve runs for about 20 minutes and eventually aborts with Presolve: Time limit reached. Full log:

% highs model.lp --presolve=on 
Running HiGHS 1.11.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option presolve to "on"
MIP  model has 132010 rows; 89748 cols; 320855 nonzeros; 42520 integer variables (42520 binary)
Coefficient ranges:
  Matrix [1e-01, 1e+00]
  Cost   [6e+02, 1e+08]
  Bound  [1e+00, 1e+00]
  RHS    [1e+00, 1e+00]
Presolving model
132010 rows, 89748 cols, 320855 nonzeros  0s
112115 rows, 69853 cols, 324946 nonzeros  0s
Presolve: Time limit reached

Context: I'm running this on a Macbook Pro, but also seeing the same behavior in Linux VMs.

3. Now run the model with presolve turned off: highs model.lp --presolve=off.

Observed result: HiGHS successfully solves the model in 4s. Full log:

% highs model.lp --presolve=off         
Running HiGHS 1.11.0 (git hash: n/a): Copyright (c) 2025 HiGHS under MIT licence terms
Set option presolve to "off"
MIP  model has 132010 rows; 89748 cols; 320855 nonzeros; 42520 integer variables (42520 binary)
Coefficient ranges:
  Matrix [1e-01, 1e+00]
  Cost   [6e+02, 1e+08]
  Bound  [1e+00, 1e+00]
  RHS    [1e+00, 1e+00]

Presolve is switched off

Solving MIP model with:
   132010 rows
   89748 cols (42520 binary, 0 integer, 0 implied int., 47228 continuous, 0 domain fixed)
   320855 nonzeros

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

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

 J       0       0         0   0.00%   -inf            2668081682.658     Large        0      0      0         0     0.8s
 R       0       0         0   0.00%   167412318.3895  167412318.3895     0.00%        0      0      0     22705     3.7s
         1       0         1 100.00%   167412318.3895  167412318.3895     0.00%        0      0      0     24851     4.1s

Solving report
  Model             model
  Status            Optimal
  Primal bound      167412318.39
  Dual bound        167412318.39
  Gap               0% (tolerance: 0.01%)
  P-D integral      2.79139360867
  Solution status   feasible
                    167412318.39 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            4.14 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 0
  Nodes             1
  Repair LPs        0 (0 feasible; 0 iterations)
  LP iterations     24851 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

Conclusion

Turning off the presolver for this particular problem works, but is a bandaid for us. The presolver is hugely beneficial for most other models.

We don't currently have a theory on what makes this model special. For our application, it's not a particularly hard, unusual or large model. Could someone from the HiGHS development team take a look and see what the presolver is doing here? We suspect this is a bug in the presolver. Does it enter an infinite loop of sorts? That would be greatly appreciated!

[jajhall]

We'll try to reproduce this

There are a couple of reasons why presolve can take an excessive amount of time.

One solution would be to have a separate time limit for presolve, but that would make the MIP solver non-deterministic in cases where the time limit causes it to stop early.

[Opt-Mucca]

Hey @severinh sorry for leaving this hanging for a while! (Got a bit obsessed with implementing some other other stuff). The instance you attached gets stuck while probing. So it's constantly checking "what happens if I set to x_i=0 and x_i=1 and propagate". The issue is that your instance is finding just the right the amount of information to avoid the stopping criteria and continue probing, e.g. some fixings, cliques, and implications. It therefore ends up probing on essentially all variables, collecting all this information that is ultimately not needed as the solve would be quick regardless. I need to think a bit on the stopping criteria (your instance should go back to being quick after we fix this). Currently they are set to be rather large as you'd maybe kneecap some other instances by lowering them. @fwesselm thoughts on adding an additional stopping criteria that kicks in after something like 1000 columns? Edit: Maybe after 1000 total useless columns all other checks get tightened or something?