Presolve incorrectly collapses objective value to exact zero

[baharev]

When running the attached model with presolve enabled (default), HiGHS incorrectly reports an optimal objective value of exactly 0. However, with presolve disabled, the solver identifies the expected optimal value of approximately 667,562,736.

While the model exhibits scaling issues in both the objective and constraint RHS, adjusting scaling parameters as suggested by the HiGHS logs does not resolve the behavior. The issue is only bypassed by disabling presolve entirely.

The discrepancy is reproducible across different operating systems and versions:

• Windows: HiGHS 1.13, NumPy 2.4, Python 3.14
• Linux: HiGHS 1.11, NumPy 1.24, Python 3.11
• Comparison: SCIP reaches the expected optimal value without issue.

Input file

dbg-presolve-1.lp.zip

Source code

from highspy import Highs

h = Highs()

h.readModel('dbg-presolve-1.lp')

# h.setOptionValue('user_objective_scale', -4)

# h.setOptionValue('user_bound_scale', -5)

# h.setOptionValue('presolve', 'off')

h.run()

Execution Logs

Presolve Enabled (Incorrect Result)

(dbgpresolve) PS C:\Users\Administrator\dbg_presolve> pip install highspy
Collecting highspy
  Using cached highspy-1.13.1-cp314-cp314-win_amd64.whl.metadata (11 kB)
Collecting numpy (from highspy)
  Downloading numpy-2.4.2-cp314-cp314-win_amd64.whl.metadata (6.6 kB)
Using cached highspy-1.13.1-cp314-cp314-win_amd64.whl (2.3 MB)
Downloading numpy-2.4.2-cp314-cp314-win_amd64.whl (12.4 MB)
   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 12.4/12.4 MB 75.4 MB/s  0:00:00
Installing collected packages: numpy, highspy
Successfully installed highspy-1.13.1 numpy-2.4.2
(dbgpresolve) PS C:\Users\Administrator\dbg_presolve> python dbg_presolve.py
Running HiGHS 1.13.1 (git hash: 1d267d9): Copyright (c) 2026 under MIT licence terms
MIP dbg-presolve-1 has 348 rows; 169 cols; 1334 nonzeros; 169 integer variables (169 binary)
Coefficient ranges:
  Matrix  [1e+00, 1e+08]
  Cost    [2e+02, 3e+08]
  Bound   [1e+00, 1e+00]
  RHS     [8e+06, 2e+07]
WARNING: Problem has some excessively large costs
WARNING: Problem has some excessively large row bounds
WARNING:    Consider scaling the objective by 1e-2, or setting the user_objective_scale option to -4
WARNING:    Consider scaling the    bounds by 1e-2, or setting the user_bound_scale option to -5
Presolving model
342 rows, 161 cols, 1211 nonzeros  0s
310 rows, 0 cols, 0 nonzeros  0s
0 rows, 0 cols, 0 nonzeros  0s
Presolve reductions: rows 0(-348); columns 0(-169); nonzeros 0(-1334) - Reduced to empty
Presolve: Optimal

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%   -0              -0                 0.00%        0      0      0         0     0.0s

Solving report
  Model             dbg-presolve-1
  Status            Optimal
  Primal bound      -0
  Dual bound        -0
  Gap               0% (tolerance: 0.01%)
  P-D integral      0
  Solution status   feasible
                    0 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.01
  Max sub-MIP depth 0
  Nodes             0
  Repair LPs        0
  LP iterations     0
(dbgpresolve) PS C:\Users\Administrator\dbg_presolve>

Presolve Disabled (Correct Result)

(dbgpresolve) PS C:\Users\Administrator\dbg_presolve> python dbg_presolve.py
Running HiGHS 1.13.1 (git hash: 1d267d9): Copyright (c) 2026 under MIT licence terms
MIP dbg-presolve-1 has 348 rows; 169 cols; 1334 nonzeros; 169 integer variables (169 binary)
Coefficient ranges:
  Matrix  [1e+00, 1e+08]
  Cost    [2e+02, 3e+08]
  Bound   [1e+00, 1e+00]
  RHS     [8e+06, 2e+07]
WARNING: Problem has some excessively large costs
WARNING: Problem has some excessively large row bounds
WARNING:    Consider scaling the objective by 1e-2, or setting the user_objective_scale option to -4
WARNING:    Consider scaling the    bounds by 1e-2, or setting the user_bound_scale option to -5

Presolve is switched off

Solving MIP model with:
   348 rows
   169 cols (158 binary, 0 integer, 0 implied int., 0 continuous, 11 domain fixed)
   1334 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

 z       0       0         0   0.00%   inf             -0                 Large        0      0      0         0     0.0s
         0       0         0   0.00%   668423012.948   -0                 Large        0      0      4        85     0.0s
 C       0       0         0   0.00%   667572101.7894  667562735.7937     0.00%      186     18      4       173     0.0s
         1       0         1 100.00%   667569371.3172  667562735.7937     0.00%      184     18      4       175     0.0s

Solving report
  Model             dbg-presolve-1
  Status            Optimal
  Primal bound      667562735.794
  Dual bound        667569371.317
  Gap               0.000994% (tolerance: 0.01%)
  P-D integral      1.07745534927e-08
  Solution status   feasible
                    667562735.794 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.04
  Max sub-MIP depth 0
  Nodes             1
  Repair LPs        0
  LP iterations     175
                    0 (strong br.)
                    88 (separation)
                    0 (heuristics)
(dbgpresolve) PS C:\Users\Administrator\dbg_presolve>

[jajhall]

Another badly-scaled MIP that has problems in presolve, @fwesselm. Is it useful to fix this?

[baharev]

While the model is poorly scaled, returning an exact 0.0 suggests a logic error in the presolve phase rather than simple numerical instability.

Applying the scaling suggested by HiGHS does not resolve this, yet the problem solves correctly with presolve disabled or when using SCIP.

This suggests a bug in the presolve logic rather than a standard numerical failure.

[jajhall]

This suggests a bug in the presolve logic rather than a standard numerical failure.

Possibly, but a single incorrect reduction in presolve can lead to the MIP being reduced to empty, and if the origin is feasible, it's possible that it will be returned as an optimal solution

[baharev]

Possibly, but a single incorrect reduction in presolve can lead to the MIP being reduced to empty, and if the origin is feasible, it's possible that it will be returned as an optimal solution

In the log I see "Reduced to empty", and the origin is indeed feasible, I can confirm that.

[fwesselm]

I will have a look as soon as possible.

[fwesselm]

Interestingly the issue persists when disabling all reductions (that can be controlled via presolve_rule_off):

Presolving model
Presolve rules not allowed:
   Rule  6 (set bit  6 =    64): Forcing row
   Rule  7 (set bit  7 =   128): Forcing col
   Rule  8 (set bit  8 =   256): Free col substitution
   Rule  9 (set bit  9 =   512): Doubleton equation
   Rule 10 (set bit 10 =  1024): Dependent equations
   Rule 11 (set bit 11 =  2048): Dependent free columns
   Rule 12 (set bit 12 =  4096): Aggregator
   Rule 13 (set bit 13 =  8192): Parallel rows and columns
   Rule 14 (set bit 14 = 16384): Sparsify
   Rule 15 (set bit 15 = 32768): Probing
   Rule 16 (set bit 16 = 65536): Enumeration
342 rows, 161 cols, 1211 nonzeros 0.006098s
Strengthened 71 coefficients
310 rows, 157 cols, 1144 nonzeros 0.022865s
Presolve reductions: rows 310(-38); columns 157(-12); nonzeros 1144(-190) 

The correct optimal objective value is found if the call to HPresolve::strengthenInequalities is commented out.

I'll continue investigating.

[fwesselm]

I found one potential improvement in presolve, but this did not resolve the issue. I will need much more time to debug this.