Solution foun by heuristic GLPK

Specific Domains Optimization (Mathematical)
1

Hi guys!
I am using GLPK solver for a MIP. The output terminal shows me the next information:

GLPK Simplex Optimizer, v4.64
16 rows, 120 columns, 800 non-zeros
1: obj = 4.548322148e+003 inf = 0.000e+000 (0)

  • 9: obj =  3.270600000e+003 inf =  0.000e+000 (0)

OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.64
16 rows, 120 columns, 800 non-zeros
120 integer variables, all of which are binary
Integer optimization begins…

  • 9: mip =     not found yet >=              -inf        (1; 0)

Solution found by heuristic: 3351

  • 14: >>>>> 3.330000000e+003 >= 3.330000000e+003 0.0% (1; 3)
  • 14: mip = 3.330000000e+003 >= tree is empty 0.0% (0; 7)
    INTEGER OPTIMAL SOLUTION FOUND

I don’t want him to use heuristics to find a solution and, I don’t know which parameter i should disable for this.

Do you have any idea how to disable the option: provide solution found by heuristic in GLPK.

Thanks for your help!

2

May I ask why you don’t want heuristics?

1 Like
3

I’m not sure if GLPK has an option to turn all heuristics off.

I’ve moved your question to the Optimization (Mathematical) category.

4

anyway, you can always look at the manual: ftp://ftp.gnu.org/gnu/glpk/ …
it seems that the only heuristic ON by default is: simple rounding (sr_heur)

1 Like
5

Hi joaquimg,

sorry for replying to a post dating back 4 months, but I think there is at least one good reason for disabling the simple rounding heuristic in GLPK.
Namely, there is a known bug with that heuristic and the lazy constraint callback in GLPK: if am not wrong, when a solution is found by the simple rounding heuristic, it is not checked for feasibility by invoking the lazy constraint callback.
The bug is reported at least until GLPK 4.60, but I experienced a similar issue with a more recent version of GLPK in Julia 1.5.0. This implies that if the solution found by simple rounding heuristic satisfies the constraints in the model, it is considered (incorrectly) feasible also if some lazy constraints are in fact violated (just because…they are not checked).
In a branch-and-bound this may prune the search-tree nodes containing the correct optimal solution, thus reporting incorrect solutions.
The suggested workaround is to turn off the simple rounding heuristic, via flag sr_heur (which I did not find how to do in JuMP).
Thanks for your attention!
Michele

1 Like
6

There is a sketch on how to set parameters in: https://github.com/jump-dev/GLPK.jl#glpkoptimizer
Thus you can do:

using JuMP, GLPK
model = Model(GLPK.Optimizer)
set_optimizer_attribute(model, "sr_heur", GLPK.GLP_OFF)
7

Hi joaquimg,
thanks for your reply.
Unfortunately I was already aware of the sketch you sent me, on how to set GLPK parameters in JuMP.
It seems that the flag sr_heur is not supported by JuMP, or that the one you were referring to is not the correct way to do.
More precisely, trying

set_optimizer_attribute(model, "sr_heur", GLPK.GLP_OFF)

returns me the error:

UndefVarError: GLP_OFF not defined
Stacktrace:
[1] getproperty at .\Base.jl:26 [inlined]

Also trying with:

set_optimizer_attribute(model, "sr_heur", 0)

gives the error:

MathOptInterface.UnsupportedAttribute{MathOptInterface.RawParameter}: Attribute MathOptInterface.RawParameter(“sr_heur”) is not supported by the model.
Stacktrace:
[1] set(::GLPK.Optimizer, ::MathOptInterface.RawParameter, ::Int64) at .julia\packages\GLPK\oTTtu\src\MOI_wrapper.jl:315

explicitly saying that sr_heur is not supported.
I did this tests on a machine running Windows 8.1, Julia 1.5.0 and GLPK v4.64.
Best regards,
Michele

9

Please run:
] st
And paste results here.
It must be a version problem.

1 Like
10

I am on the latest versions:
JuMP 0.21.5
MathOptInterface 0.9.17
GLPK 0.14.2 (GLPK.jl the julia wrapper not GLPK itself)

1 Like
11

Hello joaquimg,

thanks again for your support. This is the output you asked in a previous message (I keep only the relevant stuff):

(@v1.5) pkg> st
Status .julia\environments\v1.5\Project.toml
[a076750e] CPLEX v0.6.6
[60bf3e95] GLPK v0.13.0
[4076af6c] JuMP v0.21.3

You were 100% right: updating the JuMP and GLPK packages to the latest versions, the simple rounding heuristic was successfully disabled as you suggested, using:

set_optimizer_attribute(model, "sr_heur", GLPK.GLP_OFF)

Best regards,
Michele