Cycling or infinite loop in presolve

[odow]

Here's an MPS that does not terminate when presolve is active: bug.mps.txt

Found by @Rose-max111 in jump-dev/HiGHS.jl#221

With presolve=off I get:

julia> HiGHS_jll.highs() do exe
       run(`$exe bug.mps --presolve=off`)
       end
Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
LP   bug has 63 rows; 21 cols; 672 nonzeros
Coefficient ranges:
  Matrix [2e+00, 2e+00]
  Cost   [1e+00, 1e+00]
  Bound  [0e+00, 0e+00]
  RHS    [1e+00, 1e+00]
Solving LP without presolve, or with basis, or unconstrained
Using EKK dual simplex solver - serial
  Iteration        Objective     Infeasibilities num(sum)
          0    -1.0000000000e+03 Ph1: 29(192000); Du: 1(1) 0s
         43    -2.5000000000e-01 Ph1: 0(0); Du: 1(0.25) 0s
         58    -2.5000000000e-01 Pr: 0(0); Du: 2(0.5) 0s
Model   status      : Unbounded
Simplex   iterations: 58
Objective value     : -2.5000000000e-01
HiGHS run time      :          0.00
Process(`/Users/oscar/.julia/artifacts/3bde9ba757de2f9d934f7d672bf7fd55418a93ce/bin/highs bug.mps --presolve=off`, ProcessExited(0))

With presolve on, it stalls at:

julia> HiGHS_jll.highs() do exe
       run(`$exe bug.mps`)
       end
Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
LP   bug has 63 rows; 21 cols; 672 nonzeros
Coefficient ranges:
  Matrix [2e+00, 2e+00]
  Cost   [1e+00, 1e+00]
  Bound  [0e+00, 0e+00]
  RHS    [1e+00, 1e+00]
Presolving model
31 rows, 20 cols, 320 nonzeros  0s
^CERROR: InterruptException:

[jajhall]

Exciting: I'll try to reproduce it

[exaexa]

Hello, just +1ing myself here as I might be hitting the very same issue.

Running HiGHS 1.7.2 (git hash: 5ce7a2753): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e-05, 2e+05]
  Cost   [1e+00, 1e+00]
  Bound  [0e+00, 0e+00]
  RHS    [1e-01, 6e+03]
Presolving model
85619 rows, 142837 cols, 551793 nonzeros  0s

[...nothing happens...]

Switching presolve off solves the issue (although for this model size the algorithms get annoyingly slow so I didn't get an applicable result yet).

Also I unfortunately cannot share the model. I'd try to produce one untainted with sensitive data in case it would help reproducing the issue here, but it's gonna need some nontrivial time investment -- please let me know in case that would be needed.

[jajhall]

Hello, just +1ing myself here as I might be hitting the very same issue.

Thanks. I'll see what I get from @odow's example, and there's another user who may have the same issue

[jajhall]

I've reproduced the behaviour in release, and it triggers an assert in debug so there's a start...

[jajhall]

Presolve is trying to fix a variable to -inf. Presumably related to the LP being unbounded

[jajhall]

Closed by #1885

[exaexa]

@jajhall Hello, is there please any estimate on if/when this is going to get released? (I'd love to enjoy the fix in Julia via HiGHS.jl :) )

[jajhall]

Within a month, I'd expect

[exaexa]

OK perfect, thanks! ( I'll try to build this locally then, unfortunately this issue was a bit of a blocker so certainly worth trying :) )

[mingodad]

Every time or once in a while the github actions could extract and make available the resulting binaries.

[jajhall]

Every time or once in a while the github actions could extract and make available the resulting binaries.

Yes, but they wouldn't be fully tested, or correspond to an identifiable release.

Clearly anyone can build latest from source, but that's up to them!

[exaexa]

@jajhall is there please any plan re the release?

(Apologies for likely unnecessary spam here, but not having this fix released has become a source of minor annoyances (telling users to "just compile HiGHS with BinaryBuilder.jl custom script or use Gurobi" ain't very good). So just kinda wanted to ask for status. Thanks for any info! )

[jajhall]

We've got quite a lot of Python changes that we'll need to release as the ultimate test. Hopefully before 7 October

[exaexa]

ok great! thanks for the info!

[exaexa]

@jajhall Hello, just reporting here that the issue is not solved on my side. The model where I can reproduce this is unfortunately huge and slightly non-publishable, is there any good way to export a JuMP/HiGHS model so that you could have a look at it?

Running HiGHS 1.7.2 (git hash: f7c79b3b3): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [1e-05, 2e+05]
  Cost   [1e+00, 1e+00]
  Bound  [0e+00, 0e+00]
  RHS    [4e-04, 8e+03]
Presolving model
85619 rows, 142838 cols, 551809 nonzeros  0s

[...never finishes]

[exaexa]

(the reported f7c79b3 is the latest commit on latest)

[exaexa]

Backtrace from the stuck solver:

#0  0x00007f27502339cb in presolve::HPresolve::updateColImpliedBounds(int, int, double) () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#1  0x00007f2750234264 in presolve::HPresolve::recomputeColImpliedBounds(int) () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#2  0x00007f2750238f7c in presolve::HPresolve::substitute(int, int, double) () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#3  0x00007f27502c8188 in presolve::HPresolve::aggregator(presolve::HighsPostsolveStack&) () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#4  0x00007f275023e667 in presolve::HPresolve::presolve(presolve::HighsPostsolveStack&) () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#5  0x00007f27502c5855 in presolve::HPresolve::run(presolve::HighsPostsolveStack&) () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#6  0x00007f27501cfabf in PresolveComponent::run() () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#7  0x00007f27501d6a89 in Highs::runPresolve(bool, bool) () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#8  0x00007f27501de4a4 in Highs::run() () from /home/exa/.julia/dev/HiGHS_jll/override/lib/libhighs.so
No symbol table info available.
#9  0x00007f274f83c405 in Highs_run () at /home/exa/.julia/packages/HiGHS/MQAyL/src/gen/libhighs.jl:311
No locals.
#10 julia_optimize!_8615 () at /home/exa/.julia/packages/HiGHS/MQAyL/src/MOI_wrapper.jl:1915
No locals.
#11 0x00007f274f83c701 in optimize! () at /home/exa/.julia/packages/MathOptInterface/jqDoD/src/Bridges/bridge_optimizer.jl:367
No locals.
#12 optimize! () at /home/exa/.julia/packages/MathOptInterface/jqDoD/src/MathOptInterface.jl:122
No locals.
[..., continues to Julia]

I'll try to make a build where local variables will be visible.