Presolve worsens solution and hangs

[igofunke]

Hi team!

I bring you an instance of a model that seems to give a bit of trouble to HiGHS with presolver (Gap worsens and the solver hangs). When I switch off the presolver it seems to work fine.

I would appreciate it if someone could have a look and advise us further, as turning off the presolver is a workaround but not the ideal solution. Thanks in advance!

To reproduce:

1. Download model model.lp.zip.
2. Execute with presolve on. Note how Gap increases instead of decreasing. HiGHS seems to hang after 189.7s (execution was in reality stopped after 30+ min but logging stopped earlier)

% highs ./model.lp
Running HiGHS 1.14.0 (git hash: n/a): Copyright (c) 2026 under MIT licence terms
Command line parsed using CLI11 2.5.0: Copyright (c) 2017-2025 University of Cincinnati
MIP model has 17658 rows; 17228 cols; 50676 nonzeros; 10988 integer variables (10988 binary)
Coefficient ranges:
  Matrix  [8e-02, 3e+04]
  Cost    [9e+03, 6e+10]
  Bound   [1e+00, 1e+00]
  RHS     [1e+00, 1e+00]
WARNING: Problem has some excessively large costs
WARNING:    Consider scaling the objective by 1e-5, or setting the user_objective_scale option to -16
Presolving model
16890 rows, 16448 cols, 48340 nonzeros 0s
14381 rows, 14909 cols, 48639 nonzeros 0s
Presolve reductions: rows 14381(-3277); columns 14909(-2319); nonzeros 48639(-2037) 

Solving MIP model with:
   14381 rows
   14909 cols (10393 binary, 0 integer, 103 implied int., 4413 continuous, 0 domain fixed)
   48639 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

 J       0       0         0   0.00%   -inf            3.06920187e+11     Large        0      0      0         0     0.1s
         0       0         0   0.00%   -1.51989001e+12 3.06920187e+11   595.21%        0      0    264         0     0.5s
 L       0       0         0   0.00%   -1.51989001e+12 3.05865744e+11   596.91%        0      0    264         0     3.4s
 L       0       0         0   0.00%   -1.51989001e+12 2.98040913e+11   609.96%        0      0    264      3217     4.7s
       406     405         1   0.00%   -1.51989001e+12 2.98040913e+11   609.96%        0      0    264      6235    18.4s
 L     406     404         1   0.00%   -1.51989001e+12 86054888781.02  1866.19%        0      0    264      6235    20.3s
       928     837        28  12.50%   -1.51989001e+12 86054888781.02  1866.19%        0      0    326      9434    38.2s
      1359    1224        42  24.22%   -1.51989001e+12 86054888781.02  1866.19%        0      0    403      9434    53.1s
      1795    1609        63  26.17%   -1.51989001e+12 86054888781.02  1866.19%        0      0    464      9434    68.2s
      2321    2028       102  26.37%   -1.51989001e+12 86054888781.02  1866.19%        0      0    529      9434    85.9s
      2743    2413       116  26.89%   -1.51989001e+12 86054888781.02  1866.19%        0      0    603      9434   100.5s
      3162    2801       127  26.99%   -1.51988557e+12 86054888781.02  1866.18%        0      0    652      9434   114.8s
      3398    3001       137  26.99%   -1.51988557e+12 86054888781.02  1866.18%        0      0    725      9434   122.8s
      3838    3407       149  27.04%   -1.51988557e+12 86054888781.02  1866.18%        0      0    771      9434   137.8s
      4301    3810       173  27.14%   -1.51988557e+12 86054888781.02  1866.18%        0      0    823      9434   153.3s
      4755    4213       189  27.15%   -1.51988081e+12 86054888781.02  1866.18%        0      0    875      9434   168.7s
      5354    4765       206  27.29%   -1.51988081e+12 86054888781.02  1866.18%        0      0    930      9434   189.4s

Restarting search from the root node
Model after restart has 12495 rows, 13979 cols (10373 bin., 0 int., 97 impl., 3509 cont., 0 dom.fix.), and 49863 nonzeros

      5354       0         0   0.00%   -1.51988081e+12 86054888781.02  1866.18%        0      0      0      9434   189.6s
      5354       0         0   0.00%   -1.51988081e+12 86054888781.02  1866.18%        0      0      9      9434   189.7s
^C

3. Execute with presolve off. Model finishes with optimality in less than 13s.

% highs --presolve off ./model.lp
Running HiGHS 1.14.0 (git hash: n/a): Copyright (c) 2026 under MIT licence terms
Command line parsed using CLI11 2.5.0: Copyright (c) 2017-2025 University of Cincinnati
Set option presolve to "off"
MIP model has 17658 rows; 17228 cols; 50676 nonzeros; 10988 integer variables (10988 binary)
Coefficient ranges:
  Matrix  [8e-02, 3e+04]
  Cost    [9e+03, 6e+10]
  Bound   [1e+00, 1e+00]
  RHS     [1e+00, 1e+00]
WARNING: Problem has some excessively large costs
WARNING:    Consider scaling the objective by 1e-5, or setting the user_objective_scale option to -16

Presolve is switched off

Solving MIP model with:
   17658 rows
   17228 cols (10409 binary, 0 integer, 0 implied int., 6039 continuous, 780 domain fixed)
   50676 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

 J       0       0         0   0.00%   -inf            3.07370277e+11     Large        0      0      0         0     0.1s
         0       0         0   0.00%   8898270007.613  3.07370277e+11    97.11%        0      0      1      2266     0.1s
 C       0       0         0   0.00%   9023732377.602  2.99441231e+11    96.99%     4711   1072      6      4208     0.6s
 L       0       0         0   0.00%   10893121945.48  16087059494.14    32.29%     9143   1271      6      5551     3.5s
 B      23       0         2   0.00%   10893359805.96  12295611701.27    11.40%     9252    970     22     29024     5.8s
 T      23       0         2   0.00%   10893359805.96  12294273921.83    11.39%     9253    970     22     29024     5.8s
 B      25       0         4   0.00%   10893359805.96  12292981944.38    11.39%     9260    970     38     29074     6.0s
 T      42      16         5   0.20%   10894865697.21  10943299083.9      0.44%     6650    973    121     30034     8.7s
 T      65      16         6   0.20%   10894865697.21  10940122442.38     0.41%     6651    973    121     31052     8.7s
 T      66      16         7   0.20%   10894865697.21  10937542490.14     0.39%     6653    973    124     31053     8.7s
 T      67      16         8   0.20%   10894865697.21  10934608021.59     0.36%     6655    973    127     31068     8.8s
 B      68      16         9   0.20%   10894865697.21  10933319006.54     0.35%     6656    973    127     31083     8.8s
 B      81      25        10   0.27%   10894865697.21  10911676717.16     0.15%     4525   1080    224     32304    10.4s
 T      82      32        10   0.29%   10895534078.29  10910048398.26     0.13%     4473   1084    488     32366    11.2s
 B      89      32        11   0.68%   10895534078.29  10908472125.5      0.12%     4477   1084    496     32984    11.3s
 T      90      26        11   3.52%   10895534078.29  10903269421.83     0.07%     4353   1085    679     33023    11.7s
 T      95      22        12  10.74%   10895534078.29  10901755553.03     0.06%     4357   1085    730     33293    11.8s
 T     102      15        14  17.24%   10895534078.29  10900070853.35     0.04%     4364   1085    776     33661    12.2s
 T     112      10        16  25.20%   10895534078.29  10899050049.51     0.03%     4123   1104    820     34039    12.7s
 T     119       3        19  77.38%   10895534078.29  10896759614.21     0.01%     4128   1104    872     34200    12.9s

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

       123       0        23 100.00%   10895898207.05  10896759614.21     0.01%     4129   1104    872     34270    12.9s

Solving report
  Model             model
  Status            Optimal
  Primal bound      10896759614.2
  Dual bound        10895898207
  Gap               0.00791% (tolerance: 0.01%)
  P-D integral      4.41366038989
  Solution status   feasible
                    10896759614.2 (objective)
                    0 (bound viol.)
                    3.08197911636e-13 (int. viol.)
                    0 (row viol.)
  Timing            12.91
  Max sub-MIP depth 5
  Nodes             123
  Repair LPs        0
  LP iterations     34270
                    5001 (strong br.)
                    3750 (separation)
                    21917 (heuristics)

[jajhall]

I've reproduced the behaviour.

The problems are due to the excessively large costs in your model - something about which HiGHS warns you. The nonzero costs are in the interval [9e+03, 6e+10] and you can't expect to solve problems with such large costs, since you're expecting dual values of order 1e10 to be satisfying a tolerance of 1e-6 and machine precision only gives 16 digits of accuracy.

By scaling the costs down by 2^(-16) = 1.5e-5 (as suggested) the the problem solves satisfactorily with presolve on or off, so I strongly recommend that you do this.

The gap increases (suddenly) because the primal and dual bounds have different signs (and the primal bound drops significantly).

Whatever caused the assert appears to have corrupted the presolved MIP - something that shouldn't happen. Please would you look at this @fwesselm

[fwesselm]

@jajhall, sure, I can have a look.

[fwesselm]

@jajhall, I see that HighsLpRelaxation::run returns Status::kError many times. Now, HighsLpRelaxation::resolveLp does not set objective in the default branch (reached if there is an error), so it may contain old/stale values. Is this OK?

      case Status::kInfeasible:
        objective = kHighsInf;
        break;
      default:
        break;

[jajhall]

@jajhall, I see that HighsLpRelaxation::run returns Status::kError many times. Now, HighsLpRelaxation::resolveLp does not set objective in the default branch (reached if there is an error), so it may contain old/stale values. Is this OK?

      case Status::kInfeasible:
        objective = kHighsInf;
        break;
      default:
        break;

I think that it's OK, but I can't run in debug, as the assert in presolve stops the code from reaching this point. What I did see is that when HighsLpRelaxation::resolveLp is used to re-solve the LP after HighsLpRelaxation::run returns Status::kError there are many occurrences of Status::kError:. The ridiculously large costs mean that the dual simplex solver fails repeatedly. It's the model that needs fixing, not the solver!