Bugs: Optimizer stucks in an infinite loop when solving a small size problem

[Rose-max111]

When i was using HiGHS.Optimizer to solve some LP problems, i encountered a small-size instance that cause the optimizer stuck in an infinite loop. However, this instance could be successfully solved by other optimizers, such as COPT.Optimizer.

One could use the following code to reproduce the issue i encountered.

using JuMP
using HiGHS

weights_list = [[0, 2, 0, -2, 0, 2, 0, -2, 0, 2, 0, -2, -2, 0, 2, 0, 0, -2, 0, 2, 0],
[2, 0, 2, -2, 0, 2, 0, 0, -2, 2, -2, 0, 0, -2, 2, 0, -2, 0, -2, 2, 0],
[2, 2, 2, -2, 0, 0, 0, 0, -2, 0, 0, -2, 0, -2, 2, 0, -2, -2, -2, 2, 0],
[2, 2, 2, 0, 0, 0, 0, -2, -2, 0, -2, -2, -2, -2, 0, -2, 0, 0, 0, 2, 2],
[2, 0, 2, 0, 0, 2, 0, -2, -2, 2, 0, 0, -2, -2, 0, -2, 0, -2, 0, 2, 2],
[0, 2, 2, 0, 0, 2, 2, 0, 0, 0, -2, -2, -2, -2, 0, -2, -2, 0, 0, 2, 2],
[0, 0, 2, 0, 0, 0, 2, 0, 0, 2, 0, 0, -2, -2, 0, -2, -2, -2, 0, 2, 2],
[0, 0, 0, -2, -2, 0, 0, -2, -2, 0, -2, -2, -2, -2, 0, 0, 0, 0, 0, 2, 2],
[2, 0, 0, -2, -2, 2, 2, 0, 0, 0, -2, -2, -2, -2, 0, 0, -2, 0, 0, 2, 2],
[0, 2, 0, -2, -2, 2, 0, -2, -2, 2, 0, 0, -2, -2, 0, 0, 0, -2, 0, 2, 2],
[2, 2, 0, -2, -2, 0, 2, 0, 0, 2, 0, 0, -2, -2, 0, 0, -2, -2, 0, 2, 2],
[0, 0, 2, -2, -2, 0, 2, -2, -2, 2, -2, -2, 0, 0, 0, 0, 0, 0, -2, 2, 2],
[2, 2, 0, 0, 0, 0, 2, -2, -2, 2, -2, -2, 0, 0, 0, -2, 0, 0, -2, 2, 2],
[2, 0, 2, -2, -2, 2, 0, 0, 0, 2, -2, -2, 0, 0, 0, 0, -2, 0, -2, 2, 2],
[0, 2, 0, 0, 0, 2, 0, 0, 0, 2, -2, -2, 0, 0, 0, -2, -2, 0, -2, 2, 2],
[0, 2, 2, -2, -2, 2, 2, -2, -2, 0, 0, 0, 0, 0, 0, 0, 0, -2, -2, 2, 2],
[2, 0, 0, 0, 0, 2, 2, -2, -2, 0, 0, 0, 0, 0, 0, -2, 0, -2, -2, 2, 2],
[2, 2, 2, -2, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, -2, -2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, -2, -2, -2, 2, 2],
[0, 0, 0, 0, -2, 0, 0, 0, -2, 0, 0, -2, 0, -2, 2, 0, 0, 0, 0, 0, 2],
[2, 2, 2, -2, 0, 0, 0, 0, -2, 0, 0, -2, 0, -2, 2, -2, 0, 0, 0, 0, 2],
[2, 0, 0, 0, -2, 2, 2, -2, 0, 0, 0, -2, 0, -2, 2, 0, -2, 0, 0, 0, 2],
[0, 2, 2, -2, 0, 2, 2, -2, 0, 0, 0, -2, 0, -2, 2, -2, -2, 0, 0, 0, 2],
[0, 2, 0, 0, -2, 2, 0, 0, -2, 2, -2, 0, 0, -2, 2, 0, 0, -2, 0, 0, 2],
[2, 0, 2, -2, 0, 2, 0, 0, -2, 2, -2, 0, 0, -2, 2, -2, 0, -2, 0, 0, 2],
[2, 2, 0, 0, -2, 0, 2, -2, 0, 2, -2, 0, 0, -2, 2, 0, -2, -2, 0, 0, 2],
[0, 0, 2, -2, 0, 0, 2, -2, 0, 2, -2, 0, 0, -2, 2, -2, -2, -2, 0, 0, 2],
[0, 0, 2, 0, -2, 0, 2, 0, -2, 2, 0, -2, -2, 0, 2, 0, 0, 0, -2, 0, 2],
[2, 2, 0, -2, 0, 0, 2, 0, -2, 2, 0, -2, -2, 0, 2, -2, 0, 0, -2, 0, 2],
[2, 0, 2, 0, -2, 2, 0, -2, 0, 2, 0, -2, -2, 0, 2, 0, -2, 0, -2, 0, 2],
[0, 2, 0, -2, 0, 2, 0, -2, 0, 2, 0, -2, -2, 0, 2, -2, -2, 0, -2, 0, 2],
[0, 2, 2, 0, -2, 2, 2, 0, -2, 0, -2, 0, -2, 0, 2, 0, 0, -2, -2, 0, 2],
[2, 0, 0, -2, 0, 2, 2, 0, -2, 0, -2, 0, -2, 0, 2, -2, 0, -2, -2, 0, 2],
[2, 2, 2, 0, -2, 0, 0, -2, 0, 0, -2, 0, -2, 0, 2, 0, -2, -2, -2, 0, 2],
[0, 0, 0, -2, 0, 0, 0, -2, 0, 0, -2, 0, -2, 0, 2, -2, -2, -2, -2, 0, 2],
[0, 0, 0, -2, 0, 0, 0, -2, 0, 0, -2, 0, -2, 0, 2, 0, 0, 0, 0, 2, 0],
[2, 2, 2, 0, -2, 0, 0, -2, 0, 0, -2, 0, -2, 0, 2, -2, 0, 0, 0, 2, 0],
[2, 0, 0, -2, 0, 2, 2, 0, -2, 0, -2, 0, -2, 0, 2, 0, -2, 0, 0, 2, 0],
[0, 2, 2, 0, -2, 2, 2, 0, -2, 0, -2, 0, -2, 0, 2, -2, -2, 0, 0, 2, 0],
[2, 0, 2, 0, -2, 2, 0, -2, 0, 2, 0, -2, -2, 0, 2, -2, 0, -2, 0, 2, 0],
[2, 2, 0, -2, 0, 0, 2, 0, -2, 2, 0, -2, -2, 0, 2, 0, -2, -2, 0, 2, 0],
[0, 0, 2, 0, -2, 0, 2, 0, -2, 2, 0, -2, -2, 0, 2, -2, -2, -2, 0, 2, 0],
[0, 0, 2, -2, 0, 0, 2, -2, 0, 2, -2, 0, 0, -2, 2, 0, 0, 0, -2, 2, 0],
[2, 2, 0, 0, -2, 0, 2, -2, 0, 2, -2, 0, 0, -2, 2, -2, 0, 0, -2, 2, 0],
[0, 2, 0, 0, -2, 2, 0, 0, -2, 2, -2, 0, 0, -2, 2, -2, -2, 0, -2, 2, 0],
[0, 2, 2, -2, 0, 2, 2, -2, 0, 0, 0, -2, 0, -2, 2, 0, 0, -2, -2, 2, 0],
[2, 0, 0, 0, -2, 2, 2, -2, 0, 0, 0, -2, 0, -2, 2, -2, 0, -2, -2, 2, 0],
[0, 0, 0, 0, -2, 0, 0, 0, -2, 0, 0, -2, 0, -2, 2, -2, -2, -2, -2, 2, 0],
[2, 2, 2, -2, -2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0, 0],
[2, 0, 0, 0, 0, 2, 2, -2, -2, 0, 0, 0, 0, 0, 0, 0, -2, 0, 0, 0, 0],
[0, 2, 2, -2, -2, 2, 2, -2, -2, 0, 0, 0, 0, 0, 0, -2, -2, 0, 0, 0, 0],
[0, 2, 0, 0, 0, 2, 0, 0, 0, 2, -2, -2, 0, 0, 0, 0, 0, -2, 0, 0, 0],
[2, 0, 2, -2, -2, 2, 0, 0, 0, 2, -2, -2, 0, 0, 0, -2, 0, -2, 0, 0, 0],
[2, 2, 0, 0, 0, 0, 2, -2, -2, 2, -2, -2, 0, 0, 0, 0, -2, -2, 0, 0, 0],
[0, 0, 2, -2, -2, 0, 2, -2, -2, 2, -2, -2, 0, 0, 0, -2, -2, -2, 0, 0, 0],
[0, 0, 2, 0, 0, 0, 2, 0, 0, 2, 0, 0, -2, -2, 0, 0, 0, 0, -2, 0, 0],
[2, 2, 0, -2, -2, 0, 2, 0, 0, 2, 0, 0, -2, -2, 0, -2, 0, 0, -2, 0, 0],
[2, 0, 2, 0, 0, 2, 0, -2, -2, 2, 0, 0, -2, -2, 0, 0, -2, 0, -2, 0, 0],
[0, 2, 0, -2, -2, 2, 0, -2, -2, 2, 0, 0, -2, -2, 0, -2, -2, 0, -2, 0, 0],
[0, 2, 2, 0, 0, 2, 2, 0, 0, 0, -2, -2, -2, -2, 0, 0, 0, -2, -2, 0, 0],
[2, 0, 0, -2, -2, 2, 2, 0, 0, 0, -2, -2, -2, -2, 0, -2, 0, -2, -2, 0, 0],
[2, 2, 2, 0, 0, 0, 0, -2, -2, 0, -2, -2, -2, -2, 0, 0, -2, -2, -2, 0, 0],
[0, 0, 0, -2, -2, 0, 0, -2, -2, 0, -2, -2, -2, -2, 0, -2, -2, -2, -2, 0, 0]
]

model = Model(HiGHS.Optimizer)
@variable(model, x[1:21])

for i in 1:7
    @constraint(model, sum(weights_list[i][j] * x[j] for j in 1:21) == 0)
end
for i in 8:length(weights_list)
    @constraint(model, sum(weights_list[i][j] * x[j] for j in 1:21) <= -1)
end

@objective(model, Min, x[1])

optimize!(model)
is_solved_and_feasible(model)

I tried to seek the solution to the problem, and the point may be the optimized target:

@objective(model, Min, x[1])

If i remove this line of code or change it to

@objective(model, Max, x[1])

Then the optimizer could give the proper solution.

[odow]

This is an upstream bug in HiGHS. I have opened an issue: ERGO-Code/HiGHS#1883

To work around the problem, disable presolve with set_attribute(model, "presolve", "off").

[exaexa]

@Rose-max111 just curious, how did you generate this problem instance? (I'm kindof trying to understand what exactly killed the presolver here, i.e. how is it special). I hit the same problem on some 500k-var problems but I don't see myself getting much useful information out of the debug info there... 😅

[Rose-max111]

I was using Linear Programming to determine if there exists a Heisenberg model with exactly five ground states. And it came that this algorithm ran into an infinite loop when some specific configurations were chosen to be ground state.

@Rose-max111 just curious, how did you generate this problem instance? (I'm kindof trying to understand what exactly killed the presolver here, i.e. how is it special). I hit the same problem on some 500k-var problems but I don't see myself getting much useful information out of the debug info there... 😅

[exaexa]

I was using Linear Programming to determine if there exists a Heisenberg model with exactly five ground states. And it came that this algorithm ran into an infinite loop when some specific configurations were chosen to be ground state.

ah wow, super interesting. thanks a lot!