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?

[senhalil]

I suspect my issue is related to @Opt-Mucca 's latest explanation, so sharing it here but let me know if it is not the case and I'll create a fresh issue.

I'm on the latest version (that poetry installs by default) and I have this relatively small MIP (mps attached) which gets stuck during presolve and it does not respect the time limit (300 seconds).

presolve="on" (Click to expand)

Running HiGHS 1.13.1 (git hash: 1d267d9): Copyright (c) 2026 under MIT licence terms
WARNING: Row    names are blank or not present: using names with prefix "r", beginning with suffix 0
Writing the model to /tmp/model.mps
MIP has 17922 rows; 8788 cols; 396685 nonzeros; 8785 integer variables (8785 binary)
Coefficient ranges:
  Matrix  [1e+00, 2e+05]
  Cost    [1e+00, 2e+05]
  Bound   [1e+00, 1e+00]
  RHS     [1e+00, 2e+05]
Presolving model
16047 rows, 7861 cols, 386655 nonzeros  0s
Presolve reductions: rows 14463(-3459); columns 6932(-1856); nonzeros 360564(-36121) 
Presolve: Time limit reached

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

        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   382.7s

Solving report
  Status            Time limit reached
  Primal bound      inf
  Dual bound        -inf
  Gap               inf
  P-D integral      0
  Solution status   -
  Timing            382.70
  Max sub-MIP depth 0
  Nodes             0
  Repair LPs        0
  LP iterations     0

If I switch off the presolve, the problem still takes more than the 300 seconds (and the solver stops due to the time limit) but in this case, it has a very high quality feasible solution (even though the optimality gap is high due to poor dual bound).

presolve="off" (Click to expand)

Running HiGHS 1.13.1 (git hash: 1d267d9): Copyright (c) 2026 under MIT licence terms
WARNING: Row    names are blank or not present: using names with prefix "r", beginning with suffix 0
Writing the model to /tmp/model.mps
MIP has 17922 rows; 8788 cols; 396685 nonzeros; 8785 integer variables (8785 binary)
Coefficient ranges:
  Matrix  [1e+00, 2e+05]
  Cost    [1e+00, 2e+05]
  Bound   [1e+00, 1e+00]
  RHS     [1e+00, 2e+05]

Presolve is switched off

Solving MIP model with:
   17922 rows
   8788 cols (7852 binary, 0 integer, 0 implied int., 3 continuous, 933 domain fixed)
   396685 nonzeros

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

        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%   -5453553        inf                  inf        0      0      0         0     0.3s
 R       0       0         0   0.00%   -3701480.5      -1637475         126.05%        0      0      0      5285     1.5s
         0       0         0   0.00%   -3565088.995525 -1637475         117.72%     5384    347      0      5483    12.7s
         0       0         0   0.00%   -3397002.650021 -1637475         107.45%    20429    750    124      7060    17.7s
         0       0         0   0.00%   -3306458.052088 -1637475         101.92%    14838   1121    124      8179    22.8s
         0       0         0   0.00%   -3169266.073296 -1637475          93.55%    13973   1327    124      9433    27.9s
 L       0       0         0   0.00%   -3135146.661079 -1663736          88.44%    20964   1432    124      9900    37.5s

Symmetry detection completed in 0.1s
Found 6 full orbitope(s) acting on 12 columns

         4       0         1  12.50%   -3135146.661079 -1663736          88.44%    21052   1413    413    133433    86.4s
       124      32        22  25.76%   -3134462.417709 -1663736          88.40%     9264   1572    535    148271   151.9s
       155      32        36  35.13%   -3134462.417709 -1663736          88.40%     9271   1572   1014    158630   157.0s
       165      30        42  63.26%   -3003919.010079 -1663736          80.55%     9276   1572   1059    165528   162.3s
       200      23        50  63.26%   -3003919.010079 -1663736          80.55%     8967   1736   1134    193899   172.5s
       326     119        69  66.14%   -2858169.888048 -1663736          71.79%     7694   1384   1462    204732   177.8s
       366     115        93  69.16%   -2842406.373181 -1663736          70.84%     7719   1384   1685    223192   182.9s
       509     227       104  69.39%   -2839261.777073 -1663736          70.66%    12908   1424   1784    235930   188.2s
       701     383       116  70.38%   -2757146.729207 -1663736          65.72%     9367   1464   1928    247650   194.3s
       848     486       131  70.71%   -2757146.729207 -1663736          65.72%     9243   1366   2084    257692   199.7s
       946     504       170  71.60%   -2733215        -1663736          64.28%    11925   1393   2205    270505   205.4s
       995     490       196  72.45%   -2687821.041667 -1663736          61.55%    11396   1321   2347    304164   222.5s
      1257     687       215  72.64%   -2669820.388796 -1663736          60.47%    11432   1321   2495    309329   227.5s

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

      1331     680       242  72.68%   -2669820.388796 -1663736          60.47%     9854   1361   2571    320141   232.5s
      1380     714       260  72.69%   -2584536.74801  -1663736          55.35%    10688   1406   2636    335075   238.2s
      1459     717       285  72.70%   -2584536.74801  -1663736          55.35%    10697   1406   2868    344672   243.3s
      1489     737       304  74.26%   -2557385.190994 -1663736          53.71%    10715   1406   2931    360370   248.3s
      1495     732       309  74.45%   -2557385.190994 -1663736          53.71%     6692   1419   2965    376140   254.1s
      1509     722       320  74.70%   -2556275.973081 -1663736          53.65%    10045   1461   2987    396271   261.7s
      1552     718       343  74.72%   -2524391.911277 -1663736          51.73%    10065   1461   3489    411390   266.7s
      1566     708       353  74.73%   -2524391.911277 -1663736          51.73%    10427   1402   3512    429238   272.3s
      1666     749       381  74.74%   -2507489.897723 -1663736          50.71%    10458   1402   3721    440932   277.4s
      1702     747       399  74.75%   -2507489.897723 -1663736          50.71%     7595   1464   3865    455229   282.4s
      1726     739       415  74.75%   -2423008.891063 -1663736          45.64%    10679   1426   3981    471849   287.7s
      1772     730       440  74.77%   -2376015.5      -1663736          42.81%    10704   1426   4112    486487   293.0s
      1791     711       459  74.77%   -2375968        -1663736          42.81%    10722   1426   4131    503127   298.1s
      1792     711       460  74.77%   -2359256.330295 -1663736          41.80%     5280   1468   4134    507983   300.1s

Solving report
  Status            Time limit reached
  Primal bound      -1663736
  Dual bound        -2359256.3303
  Gap               41.8% (tolerance: 1%)
  P-D integral      231.352162664
  Solution status   feasible
                    -1663736 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            300.11
  Max sub-MIP depth 2
  Nodes             1792
  Repair LPs        0
  LP iterations     507983
                    216122 (strong br.)
                    12173 (separation)
                    28182 (heuristics)

model.mps.txt

[jajhall]

Thanks, I'll leave @Opt-Mucca to consider whether presolve takes so long for the same reason as before, but I'm puzzled that the MIP solver doesn't just return when presolve times out. I'll look at that

[jajhall]

I see now that the time limit is only checked when enumeration or probing finish, so HiGHS can run rather longer than the limit. The MIP logging giving a time of 382.7s for a limit of 300s is just the "header" logging and final MIP logging, but no MIP solution operations take place.

Given that a particular call to enumeration and probing can take a long time, there needs to be a timeout check within these methods.

[senhalil]

Thanks for looking into it!

there needs to be a timeout check within these methods.

Happy to help if this is something an external contributor can do.

[jajhall]

#2861 may help you a lot - I'll test later today - and I've got code written for a logging and timeout facility for probing that I'll also test later.

Thanks for the offer, though

[fwesselm]

#2861 may help you a lot - I'll test later today - and I've got code written for a logging and timeout facility for probing that I'll also test later.

Thanks for the offer, though

I experimented a little bit and probing (presolve and implied bound cut separation) seems to be very time-consuming for this model. The latest version of enumeration seems to be OK.

[jajhall]

I suspect my issue is related to @Opt-Mucca 's latest explanation, so sharing it here but let me know if it is not the case and I'll create a fresh issue.

I'm on the latest version (that poetry installs by default) and I have this relatively small MIP (mps attached) which gets stuck during presolve and it does not respect the time limit (300 seconds).
presolve="on" (Click to expand)

If I switch off the presolve, the problem still takes more than the 300 seconds (and the solver stops due to the time limit) but in this case, it has a very high quality feasible solution (even though the optimality gap is high due to poor dual bound).
presolve="off" (Click to expand)

model.mps.txt

For this model, probing is still very time-consuming (as also observed by @fwesselm). With probing switched off presolve takes little time, but the solution time is still long. Ditto with presolve off completely.

For your original problem - with 132010 rows; 89748 cols; 320855 nonzeros; 42520 integer variables (42520 binary) - the solution time is about 4s with the probing of presolve switched off.