A sequence of LP solves can confuse HiGHS into thinking the problem is cycling

[odow]

See the original discussion in jump-dev/HiGHS.jl#316

From the HiGHS developer call, we think what is happening is:

• HiGHS solves an LP, and stores a sequence of previously seen bases
• The user modifies the LP, then resolves
• Starting from the previous solution basis, HiGHS steps, hits a previous basis, and terminates because it thinks it is cycling

To fix, we need to throw away prior solution information and re-start the solve (probably only if we fail because of "cycling").

It's quite tricky to come up with a reproducible example for this issue.

Here's the log:

Running HiGHS 1.12.0 (git hash: 755a8e027): Copyright (c) 2025 HiGHS under MIT licence terms
LP has 34868 rows; 20424 cols; 76248 nonzeros
Coefficient ranges:
  Matrix  [2e-05, 1e+04]
  Cost    [3e-02, 8e+01]
  Bound   [1e+00, 1e+04]
  RHS     [1e-04, 2e+03]
Presolving model
10532 rows, 10640 cols, 35504 nonzeros  0s
7908 rows, 8016 cols, 33259 nonzeros  0s
Dependent equations search running on 1790 equations with time limit of 6.00s
Dependent equations search removed 0 rows and 0 nonzeros in 0.00s (limit = 6.00s)
7718 rows, 7918 cols, 31688 nonzeros  0s
Presolve reductions: rows 7718(-27150); columns 7918(-12506); nonzeros 31688(-44560)
Solving the presolved LP
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0     0.0000000000e+00 Ph1: 0(0) 0s
       7216     9.8156324683e+03 Pr: 0(0); Du: 0(1.34825e-12) 1s

Performed postsolve
Solving the original LP from the solution after postsolve

Model status        : Optimal
Simplex   iterations: 7216
Objective value     :  9.8156324683e+03
P-D objective error :  7.4771018698e-14
HiGHS run time      :          1.21
Running HiGHS 1.12.0 (git hash: 755a8e027): Copyright (c) 2025 HiGHS under MIT licence terms
LP has 34868 rows; 20424 cols; 76248 nonzeros
Coefficient ranges:
  Matrix  [2e-05, 1e+04]
  Cost    [3e-02, 8e+01]
  Bound   [1e+00, 1e+04]
  RHS     [1e-04, 2e+03]
Solving LP with useful basis so presolve not used
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -1.5149276219e+09 Pr: 6560(2.11687e+13); Du: 0(3.14271e-07) 0s
Model status        : Not Set
HiGHS run time      :          0.24