User-provided heuristic solutions incorrectly report being rejected

[votroto]

Gurobi can accept user provided heuristic solutions during "MIP", "MIPNODE" and "MIPSOL". When in "MIPNODE", the solutions are used immediately, otherwise they are stored to be used later.

When setting solutions during "MIPSOL", Gurobi.jl incorrectly returns HEURISTIC_SOLUTION_REJECTED despite being used later. It could be less confusing to return HEURISTIC_SOLUTION_UNKNOWN instead.

Example code:

using JuMP
using Gurobi

m = direct_model(Gurobi.Optimizer())

@variable m x >= 0
@variable m xx
@variable m y >= 0
@variable m yy
@constraint m xx == x * x
@constraint m yy == y * y
@constraint m x + y >= 1

@objective m Min xx * x - x * x + 2 * x * y - y * y + yy * y

cb_calls = Cint[]
function my_callback_function(cb_data, cb_where::Cint)
        push!(cb_calls, cb_where)

        if cb_where != GRB_CB_MIPSOL
                return
        end

	vars = [x, y]
	vals = [0.997, 0.003]

        acc = MOI.submit(m, MOI.HeuristicSolution(cb_data), vars, vals)

	# Should be always accepted, but it never is unless queried at MIPNODE.
        if acc == MOI.HEURISTIC_SOLUTION_ACCEPTED
                throw("yay")
        end
end

MOI.set(m, MOI.RawOptimizerAttribute("NonConvex"), 2)
MOI.set(m, Gurobi.CallbackFunction(), my_callback_function)
optimize!(m)

Solutions are clearly being accepted, Gurobi.jl just can not make the determination yet at query time.

Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (linux64)

CPU model: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads

Optimize a model with 1 rows, 4 columns and 2 nonzeros
Model fingerprint: 0x8c47dbf8
Model has 5 quadratic objective terms
Model has 2 quadratic constraints
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  QMatrix range    [1e+00, 1e+00]
  QLMatrix range   [1e+00, 1e+00]
  Objective range  [0e+00, 0e+00]
  QObjective range [2e+00, 4e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+00, 1e+00]

Continuous model is non-convex -- solving as a MIP

Presolve time: 0.00s
Presolved: 14 rows, 9 columns, 25 nonzeros
Presolved model has 5 bilinear constraint(s)
Variable types: 9 continuous, 0 integer (0 binary)

Root relaxation: unbounded, 2 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  postponed    0               -          -      -     -    0s
     0     0  postponed    0               -          -      -     -    0s
H    0     0                       0.2500000          -      -     -    0s
H    0     2                       0.0029910          -      -     -    0s
H    0     2                       0.0029910          -      -     -    0s
     0     2  postponed    0         0.00299          -      -     -    0s
H   40     5                       0.0000000  -38.14697      -   0.8    0s
*   51     5              24      -0.0000000  -15.25879      -   1.0    0s

Explored 61 nodes (74 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 4 (of 4 available processors)

Solution count 3: -1.96408e-08 0.00299097 0.25 

Optimal solution found (tolerance 1.00e-04)
Best objective 2.337765143690e-07, best bound -1.964078566452e-08, gap -

User-callback calls 306, time in user-callback 0.03 sec

Versions:
Gurobi version 10
Gurobi.jl v0.11.4

[odow]

So the ask is to change REJECTED to UNKNOWN here if we are in a MIPSOL?

Gurobi.jl/src/MOI_wrapper/MOI_callbacks.jl

Lines 299 to 303 in 44101cc

	objP = Ref{Cdouble}()
	ret = GRBcbsolution(cb.callback_data, solution, objP)
	_check_ret(model, ret)
	return objP[] < GRB_INFINITY ? MOI.HEURISTIC_SOLUTION_ACCEPTED :
	MOI.HEURISTIC_SOLUTION_REJECTED

We can look up the status using something like:

Gurobi.jl/src/MOI_wrapper/MOI_callbacks.jl

Lines 172 to 179 in 44101cc

	function MOI.get(::Optimizer, attr::MOI.CallbackNodeStatus{CallbackData})
	if attr.callback_data.cb_where == GRB_CB_MIPSOL
	return MOI.CALLBACK_NODE_STATUS_INTEGER
	elseif attr.callback_data.cb_where == GRB_CB_MIPNODE
	return MOI.CALLBACK_NODE_STATUS_FRACTIONAL
	end
	return MOI.CALLBACK_NODE_STATUS_UNKNOWN
	end

PRs accepted 😄

[votroto]

Yes, I would appreciate if REJECTED were changed to UNKNOWN in cases where such a verdict can not yet be made (presumeably both MIP and MIPSOL), since debugging such problems is non-trivial.

What to do is version dependent, but the correct procedure and interpretation of the returned values is not well documented. I posted a question on their support forum and will report with the result.

There is no example of how to use user-heuristics (i could provide one if you are interested).