A few crashes and correctness issues in HiGHS found by Flip

[zxt5]

Hi,

In response to @Opt-Mucca's request, this report summarizes several issues in HiGHS found with Flip.

For the wrong answer or wrong status issues, I only report representative cases since it's hard for me to deduplicate them from the solver outputs. Thanks.

1. 1.mps.txt This triggers a crash in HiGHS in default mode.

Running HiGHS 1.13.1 (git hash: b174cc934): Copyright (c) 2026 under MIT licence terms
Command line parsed using CLI11 2.5.0: Copyright (c) 2017-2025 University of Cincinnati
MIP 1 has 38 rows; 8 cols; 285 nonzeros; 8 integer variables (0 binary)
Coefficient ranges:
  Matrix  [4e-01, 5e+02]
  Cost    [2e+01, 3e+02]
  Bound   [1e+02, 1e+02]
  RHS     [3e+01, 2e+04]
Presolving model
38 rows, 8 cols, 285 nonzeros 0.000621s
38 rows, 8 cols, 285 nonzeros 0.000841s
Presolve reductions: rows 38(-0); columns 8(-0); nonzeros 285(-0) 
Objective function is integral with scale 100

Solving MIP model with:
   38 rows
   8 cols (0 binary, 8 integer, 0 implied int., 0 continuous, 0 domain fixed)
   285 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%   -145085         inf                  inf        0      0      0         0     0.0s
         0       0         0   0.00%   22971.131629    inf                  inf        0      0      4        16     0.0s
highs: /home/x27zhou/third_party/HiGHS/highs/presolve/HPresolve.cpp:4073: auto presolve::HPresolve::rowPresolve(presolve::HighsPostsolveStack &, HighsInt)::(anonymous class)::operator()(double, const HighsCDouble &, HighsCDouble &) const: Assertion `roundedRhs > 0.0' failed.
Aborted (core dumped)

2. 2.mps.txt HiGHS returns Infeasible in default mode, and reports Optimal with an solution with --presolve off.

$ highs 2.mps 
Running HiGHS 1.13.1 (git hash: b174cc934): Copyright (c) 2026 under MIT licence terms
Command line parsed using CLI11 2.5.0: Copyright (c) 2017-2025 University of Cincinnati
MIP 2 has 25 rows; 5 cols; 106 nonzeros; 2 integer variables (0 binary)
Coefficient ranges:
  Matrix  [4e-01, 5e+02]
  Cost    [9e+01, 3e+02]
  Bound   [1e+02, 1e+02]
  RHS     [1e+02, 4e+04]
Presolving model
25 rows, 5 cols, 106 nonzeros 0.000314s
25 rows, 5 cols, 106 nonzeros 0.000504s
Presolve reductions: rows 25(-0); columns 5(-0); nonzeros 106(-0) 

Solving MIP model with:
   25 rows
   5 cols (0 binary, 2 integer, 0 implied int., 3 continuous, 0 domain fixed)
   106 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%   -104645.158336  inf                  inf        0      0      0         0     0.0s
         0       0         0   0.00%   -39081.059315   inf                  inf        0      0      0         5     0.0s
         1       0         1 100.00%   inf             inf                  inf       13      2      2        12     0.0s

Solving report
  Model             2
  Status            Infeasible
  Primal bound      inf
  Dual bound        inf
  Gap               inf
  P-D integral      0
  Solution status   -
  Timing            0.01
  Max sub-MIP depth 0
  Nodes             1
  Repair LPs        0
  LP iterations     12
                    0 (strong br.)
                    7 (separation)
                    0 (heuristics)

$ highs --presolve off 2.mps 
Running HiGHS 1.13.1 (git hash: b174cc934): 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 2 has 25 rows; 5 cols; 106 nonzeros; 2 integer variables (0 binary)
Coefficient ranges:
  Matrix  [4e-01, 5e+02]
  Cost    [9e+01, 3e+02]
  Bound   [1e+02, 1e+02]
  RHS     [1e+02, 4e+04]

Presolve is switched off

Solving MIP model with:
   25 rows
   5 cols (0 binary, 2 integer, 0 implied int., 3 continuous, 0 domain fixed)
   106 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%   -111326.14      inf                  inf        0      0      0         0     0.0s
         0       0         0   0.00%   -39081.059315   inf                  inf        0      0      2         5     0.0s
 H       0       0         0 100.00%   -39018.855774   -39018.855774      0.00%        7      2      4        10     0.0s
         1       0         1 100.00%   -39018.855774   -39018.855774      0.00%        6      2      4        10     0.0s

Solving report
  Model             2
  Status            Optimal
  Primal bound      -39018.8557739
  Dual bound        -39018.8557739
  Gap               0% (tolerance: 0.01%)
  P-D integral      0
  Solution status   feasible
                    -39018.8557739 (objective)
                    0 (bound viol.)
                    9.97989928919e-07 (int. viol.)
                    0 (row viol.)
  Timing            0.01
  Max sub-MIP depth 0
  Nodes             1
  Repair LPs        0
  LP iterations     10
                    0 (strong br.)
                    5 (separation)
                    0 (heuristics)

3. 3.mps.txt This triggers a crash in HiGHS in default mode.

Running HiGHS 1.13.1 (git hash: b174cc934): Copyright (c) 2026 under MIT licence terms
Command line parsed using CLI11 2.5.0: Copyright (c) 2017-2025 University of Cincinnati
MIP 3 has 16 rows; 4 cols; 39 nonzeros; 3 integer variables (0 binary)
Coefficient ranges:
  Matrix  [3e-01, 5e+02]
  Cost    [1e+02, 4e+02]
  Bound   [1e+02, 1e+02]
  RHS     [2e+00, 7e+04]
Presolving model
13 rows, 4 cols, 35 nonzeros 0.000339s
2 rows, 3 cols, 5 nonzeros 0.000535s
Presolve reductions: rows 2(-14); columns 3(-1); nonzeros 5(-34) 

Solving MIP model with:
   2 rows
   3 cols (0 binary, 1 integer, 0 implied int., 0 continuous, 2 domain fixed)
   5 nonzeros
highs: /home/x27zhou/third_party/HiGHS/highs/mip/HighsMipSolverData.cpp:230: HighsModelStatus HighsMipSolverData::trivialHeuristics(): Assertion `legal_bounds' failed.
Aborted (core dumped)

4. 4.mps.txt HiGHS returns an objective value 1990.64 in default mode, while the optimal objective value should be 1938.13, which can be obtained with --presolve off.

$ highs 4.mps 
Running HiGHS 1.13.1 (git hash: b174cc934): Copyright (c) 2026 under MIT licence terms
Command line parsed using CLI11 2.5.0: Copyright (c) 2017-2025 University of Cincinnati
MIP 4 has 9 rows; 3 cols; 27 nonzeros; 2 integer variables (0 binary)
Coefficient ranges:
  Matrix  [6e+00, 1e+02]
  Cost    [2e+01, 3e+02]
  Bound   [1e+02, 2e+02]
  RHS     [3e+02, 1e+03]
Presolving model
9 rows, 3 cols, 27 nonzeros 0.000299s
9 rows, 3 cols, 27 nonzeros 0.000411s
Presolve reductions: rows 9(-0); columns 3(-0); nonzeros 27(-0) 

Solving MIP model with:
   9 rows
   3 cols (0 binary, 2 integer, 0 implied int., 1 continuous, 0 domain fixed)
   27 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            35778.2            Large        0      0      0         0     0.0s
         0       0         0   0.00%   1761.168333     35778.2           95.08%        0      0      1         5     0.0s
 C       0       0         0   0.00%   1838.44429      2024.521995        9.19%       10      5      2        12     0.0s
 H       0       0         0   0.00%   1920.142513     1990.642551        3.54%       20      8      2        18     0.0s
         1       0         1 100.00%   1990.642551     1990.642551        0.00%       20      8      2        19     0.0s

Solving report
  Model             4
  Status            Optimal
  Primal bound      1990.64255077
  Dual bound        1990.64255077
  Gap               0% (tolerance: 0.01%)
  P-D integral      0.00162207266373
  Solution status   feasible
                    1990.64255077 (objective)
                    0 (bound viol.)
                    4.97379915032e-14 (int. viol.)
                    0 (row viol.)
  Timing            0.01
  Max sub-MIP depth 0
  Nodes             1
  Repair LPs        0
  LP iterations     19
                    0 (strong br.)
                    13 (separation)
                    1 (heuristics)

$ highs --presolve off 4.mps 
Running HiGHS 1.13.1 (git hash: b174cc934): 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 4 has 9 rows; 3 cols; 27 nonzeros; 2 integer variables (0 binary)
Coefficient ranges:
  Matrix  [6e+00, 1e+02]
  Cost    [2e+01, 3e+02]
  Bound   [1e+02, 2e+02]
  RHS     [3e+02, 1e+03]

Presolve is switched off

Solving MIP model with:
   9 rows
   3 cols (0 binary, 2 integer, 0 implied int., 1 continuous, 0 domain fixed)
   27 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            14111.501899       Large        0      0      0         0     0.0s
         0       0         0   0.00%   1761.168333     14111.501899      87.52%        0      0      1         5     0.0s
 H       0       0         0   0.00%   1863.389947     1990.642551        6.39%       19      9      3        19     0.0s
 H       0       0         0   0.00%   1863.389947     1987.319523        6.24%       19      9      3        19     0.0s
 H       0       0         0   0.00%   1863.389947     1938.133705        3.86%       20      9      3        19     0.0s
         1       0         1 100.00%   1938.133705     1938.133705        0.00%       26      3     14        41     0.0s

Solving report
  Model             4
  Status            Optimal
  Primal bound      1938.13370462
  Dual bound        1938.13370462
  Gap               0% (tolerance: 0.01%)
  P-D integral      0.00285195155862
  Solution status   feasible
                    1938.13370462 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.01
  Max sub-MIP depth 0
  Nodes             1
  Repair LPs        0
  LP iterations     41
                    3 (strong br.)
                    15 (separation)
                    14 (heuristics)

[Opt-Mucca]

@fwesselm I've dived into 3. It seems that a column's lower bound is updated to be above its upper bound in updateColImpliedBounds (following the call chain presolveColSingletons -> colPresolve -> singletonCol). So the problem should be marked as infeasible, but nobody actually ends up checking this and presolve ends. The MIP solver then assumes the domain to be feasible. Does the call need to be wrapped in something like HPRESOLVE_CHECKED_CALL or should a general check be done after presolve for column bounds?

[fwesselm]

@fwesselm I've dived into 3. It seems that a column's lower bound is updated to be above its upper bound in updateColImpliedBounds (following the call chain presolveColSingletons -> colPresolve -> singletonCol). So the problem should be marked as infeasible, but nobody actually ends up checking this and presolve ends. The MIP solver then assumes the domain to be feasible. Does the call need to be wrapped in something like HPRESOLVE_CHECKED_CALL or should a general check be done after presolve for column bounds?

Oh, well spotted, @Opt-Mucca. I will have a look shortly.

[fwesselm]

The root cause is that column bounds are updated before the implied bounds which means that the code may not mark a column as changed. Consequently, such columns are not checked for inconsistent bounds. I am working on a fix.

[fwesselm]

I investigated issue 2: A tableau cut has a violation of around 2.5e-7 with respect to an optimal solution (found without presolve) before postprocessing. The cut is then scaled with 4 and its violation exceeds the MIP feasibility tolerance. Finding the root cause will take more time.

[Opt-Mucca]

@fwesselm I followed up on 2. I don't think there is a fix (at least not on the cutting plane side). I couldn't find any incorrect operations in separateLiftedMixedIntegerCover, and playing around with HighsCDouble upgrades everywhere and larger tolerances still didn't change the failure. SCIP also produces an incorrect infeasible status.

[jajhall]

OK, we can safely forget about 2.

[Opt-Mucca]

The bug for 4.mps comes from extractCliquesFromCut in HighsCliqueTable.cpp.

HiGHS/highs/mip/HighsCliqueTable.cpp

Lines 1106 to 1123 in dcc2530

	for (HighsInt i = 0; i != len; ++i) {
	if (mipsolver.isColContinuous(inds[i])) continue;
	double boundVal = static_cast<double>((rhs - minact) / vals[i]);
	if (vals[i] > 0) {
	boundVal = std::floor(boundVal + globaldom.col_lower_[inds[i]] +
	globaldom.feastol());
	globaldom.changeBound(HighsBoundType::kUpper, inds[i], boundVal,
	HighsDomain::Reason::unspecified());
	if (globaldom.infeasible()) return;
	} else {
	boundVal = std::ceil(boundVal + globaldom.col_upper_[inds[i]] -
	globaldom.feastol());
	globaldom.changeBound(HighsBoundType::kLower, inds[i], boundVal,
	HighsDomain::Reason::unspecified());
	if (globaldom.infeasible()) return;
	}
	}

vals[0] is just above the 1e-6 threshold, and this results in the floor / ceil operation having slightly more room than feastol to play around. The function then tightens the domain by one too many. A quick solution would be to throw 10 * feastol in the floor / ceil operations for extra safety (works on this problem), although I need to think on whether that's worth it.