HiGHS
HiGHS copied to clipboard
ERGO-Code
Presolve leads to multiple 'WARNING: Untransformed solution with objective[...] is violated by 0.42 for the original model'
For the attached MIP model HiGHS with default options struggles to find a feasible solution. Instead
WARNING: Untransformed solution with objective 1.50762e+08 is violated by 0.42 for the original model
is written to stdout / logfile multiple times. With presolve=off a feasible solution is found quickly (same with SCIP/Soplex and CBC) I have a set of related models that show the same behaviour.
I seem to be having a similar issue, with presolving leading this message and then HiGHS complaining about an infeasible problem. Unlike issue #771, I don't think has anything to do with large constants -- all my variables are binary, and only occur in constraints with coefficients of 0 and 1, so it should be numerically fairly well conditioned With presolving turned off, it solves it fine.
Sure, here: bad_highs_model.txt That's the .lp format, but GitHub insisted I give it a known file extension (.txt).
For reference, I'm getting this error on HiGHS v1.5.1, githash 93f1876e4, which is the one currently in the Julia repos (HiGHS.jl).
Strange, I get the following with githash https://github.com/ERGO-Code/HiGHS/commit/93f1876e453eeec2d16e2a0c95874d0ef12c5b23 built on Linux. Are you running on Windows?
Running HiGHS 1.5.1 [date: 2023-04-18, git hash: 93f1876e4] Copyright (c) 2023 HiGHS under MIT licence terms MIP issue-942 has 1879 rows; 619 cols; 4441 nonzeros; 619 integer variables Presolving model 1729 rows, 572 cols, 3849 nonzeros 1358 rows, 495 cols, 3129 nonzeros 996 rows, 342 cols, 2347 nonzeros 634 rows, 0 cols, 0 nonzeros 0 rows, 0 cols, 0 nonzeros Presolve: Optimal
Solving report Status Optimal Primal bound 0 Dual bound 0 Gap 0% (tolerance: 0.01%) Solution status feasible 0 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.09 (total) 0.09 (presolve) 0.00 (postsolve) Nodes 0 LP iterations 0 (total) 0 (strong br.) 0 (separation) 0 (heuristics)
Yes, on Windows. I could try it without the Julia wrapper, later, to see if that's relevant. (I would be suspicious of double values changing slightly or something, but given that it's all integers, it shouldn't have any rounding...)
I'll also check that loading the .lp back in makes it fail. The bug might depend on e.g. the specific order that variables are added.
I could try it without the Julia wrapper, later, to see if that's relevant
Yip. Solving a model with HiGHS.jl will not produce the same model as writing it to a file and then calling the HiGHS binary.
EDIT: I think this is an easier way to replicate the issue locally. Download highs_file.txt, then run this Julia code:
using JuMP
import HiGHS
new_model = read_from_file("highs_file.txt"; format = MOI.FileFormats.FORMAT_LP)
set_optimizer(new_model, HiGHS.Optimizer)
optimize!(new_model)
It produces the following output:
Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
735 rows, 277 cols, 1611 nonzeros
543 rows, 243 cols, 1237 nonzeros
397 rows, 139 cols, 917 nonzeros
221 rows, 6 cols, 257 nonzeros
11 rows, 5 cols, 25 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal
WARNING: Untransformed solution with objective 0 is violated by 1 for the original model
Solving report
Status Optimal
Primal bound 0
Dual bound 0
Gap 0% (tolerance: 0.01%)
Solution status infeasible
0 (objective)
0 (bound viol.)
0 (int. viol.)
1 (row viol.)
Timing 0.01 (total)
0.01 (presolve)
0.00 (postsolve)
Nodes 0
LP iterations 0 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
ERROR: MIP solver claims optimality, but with num/sum/max primal(2/2/1) infeasibilities
If I run it without presolving, as in
using JuMP
import HiGHS
new_model = read_from_file("highs_file.txt"; format = MOI.FileFormats.FORMAT_LP)
set_optimizer(new_model, optimizer_with_attributes(HiGHS.Optimizer, "presolve" => "off"))
optimize!(new_model)
Then it works fine:
Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolve is switched off
Objective function is integral with scale 1
Solving MIP model with:
1052 rows
356 cols (356 binary, 0 integer, 0 implied int., 0 continuous)
2288 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
0 0 0 0.00% 0 inf inf 0 0 2 122 0.0s
Solving report
Status Optimal
Primal bound 0
Dual bound 0
Gap 0% (tolerance: 0.01%)
Solution status feasible
0 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.02 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 229 (total)
0 (strong br.)
107 (separation)
0 (heuristics)
I had an earlier version of this comment which had a much longer and hard-to-interpret MWE, but I've hidden in it this block if you're curious.
Previous MWE
Alright, I tried making a minimal working example with the Julia. (This is actually slightly different than the LP I gave earlier, I changed it a bit to make it smaller while still giving the same issue.) I'm sure there's some way to get the actual model 'out' of the HiGHS object, but I don't know how, so the best I could do was to give a minimized version of the Julia code to generate the model. I added a "print_only" option so you can dump out the LP in the order that Julia makes the variables and constraints. Hopefully that would be enough to (mostly?) reconstruct the problem in vanilla HiGHS. I've attached that output in a text file to this comment: [highs_bug.txt](https://github.com/ERGO-Code/HiGHS/files/11267583/highs_bug.txt)
Julia code:
using JuMP
import HiGHS
function make_and(var_1, var_2)
var_res = @variable(model, binary=true)
@constraint(model, var_res <= var_1)
@constraint(model, var_res <= var_2)
@constraint(model, var_res >= var_1 + var_2 - 1.0)
if print_only
println("Binary ",var_res,"")
println(var_1-var_res," >= 0")
println(var_2-var_res," >= 0")
println(var_res-var_1-var_2+1," >= 0")
end
return var_res
end
make_nor(var_1, var_2) = make_and(1 - var_1, 1 - var_2)
make_xor(var_1, var_2) = make_and(1 - make_and(var_1, var_2), 1 - make_and(1 - var_1, 1 - var_2))
function make_sum(word_1, word_2)
b1, b2, b3, b4 = word_1[2], word_2[2], word_1[1], word_2[1]
v0 = make_and(b3, b4)
v1 = make_nor(b1, b2)
v2 = make_nor(b1, v1)
v3 = make_nor(v1, b2)
v4 = make_nor(v2, v3)
v5 = make_nor(v4, v0)
v6 = make_nor(v4, v5)
v7 = make_nor(v5, v0)
v8 = make_nor(b3, b4)
v9 = make_nor(v6, v7)
v10 = make_nor(v0, v8)
return [v10, v9]
end
function do_circuit()
global model
optimizer = optimizer_with_attributes(HiGHS.Optimizer,
"presolve" => (if use_presolve "choose" else "off" end));
model = Model(optimizer);
@variable(model, iv[i=1:4, b=1:2], binary=true)
if print_only
for x=1:4, y=1:2
println("Binary ",iv[x,y])
end
end
Avar, Bvar, Cvar, Dvar = [1,0], [1,1], [0,0], [0,0]
for round = 1:6
bm = [[1,1],[1,1],[0,0],[1,1],[1,1],[1,0]][round]
F1 = make_xor.(Dvar, make_and.(Bvar, make_xor.(Cvar, Dvar)))
F2 = make_sum(F1, make_sum(Avar, make_sum(bm, iv[1+(round-1)%4, :])))
F3 = make_sum(Bvar, if [1,0,0,0,1,1][round]==1 reverse(F2) else F2 end)
Avar, Dvar, Cvar, Bvar = Dvar, Cvar, Bvar, F3
end
@constraint(model, vcat(Avar,Bvar,Cvar,Dvar) .== [0,1,1,0,1,0,0,0])
if print_only
for i=1:8
println(vcat(Avar,Bvar,Cvar,Dvar)[i]," == ",[0,1,1,0,1,0,0,0][i])
end
return
end
optimize!(model)
@assert primal_status(model) == FEASIBLE_POINT
end
use_presolve = false
#Uncomment this part to print out the LP in a plain-text form
# print_only = true
# do_circuit()
print_only = false
#Try solving without presolving: finds a solution
do_circuit()
#Try solving with presolving: crashes
use_presolve = true
do_circuit()
Output:
Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolve is switched off
Objective function is integral with scale 1
Solving MIP model with:
1052 rows
356 cols (356 binary, 0 integer, 0 implied int., 0 continuous)
2288 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
0 0 0 0.00% 0 inf inf 0 0 2 122 0.0s
Solving report
Status Optimal
Primal bound 0
Dual bound 0
Gap 0% (tolerance: 0.01%)
Solution status feasible
0 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.03 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 230 (total)
0 (strong br.)
108 (separation)
0 (heuristics)
Running HiGHS 1.5.1 [date: 1970-01-01, git hash: 93f1876e4]
Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
735 rows, 277 cols, 1611 nonzeros
543 rows, 243 cols, 1237 nonzeros
397 rows, 139 cols, 917 nonzeros
235 rows, 23 cols, 337 nonzeros
105 rows, 17 cols, 238 nonzeros
43 rows, 17 cols, 107 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal
WARNING: Untransformed solution with objective 0 is violated by 1 for the original model
Solving report
Status Optimal
Primal bound 0
Dual bound 0
Gap 0% (tolerance: 0.01%)
Solution status infeasible
0 (objective)
0 (bound viol.)
0 (int. viol.)
1 (row viol.)
Timing 0.01 (total)
0.01 (presolve)
0.00 (postsolve)
Nodes 0
LP iterations 0 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
ERROR: MIP solver claims optimality, but with num/sum/max primal(2/2/1) infeasibilities
AssertionError: primal_status(model) == FEASIBLE_POINT