Add support for CallbackNodeStatus

[harshangrjn]

On JuMP v0.20.1: Attaching a small lazy callback implementation example below (modified based on https://github.com/JuliaOpt/JuMP.jl/blob/master/examples/callbacks.jl) and the output of CPLEX. x_val values are taking fractional values inside the lazy callback while this must be strictly integral as this callback must be invoked only at incumbents. Typically user callback has to do this.

Posting here since I am using solver independent callback. This issue appears in both CPLEX and Gurobi. Looks like a bug in JuMP but let me know if I am missing anything.

using JuMP, CPLEX, Gurobi

function example_lazy_constraint_mod()
    n=4
    A = [0.0 0.83513 0.564369 0.432627; 0.83513 0.0 1.93858 1.77313; 0.564369 1.93858 0.0 0.718298; 0.432627 1.77313 0.718298 0.0]
    
    model = direct_model(CPLEX.Optimizer())
    # model = direct_model(Gurobi.Optimizer())
    @variable(model, x[1:n, 1:n], Bin)
    @variable(model, y >= 0)
    @variable(model, W[1:n, 1:n])

    @objective(model, Max, y)

    @constraint(model, [i=1:n], x[i,i] == 0)
    @constraint(model, [i=1:(n-1), j=(i+1):n], x[i,j] == x[j,i])
    @constraint(model, sum(x) == 2*(n-1))   
    @constraint(model, [i=1:n], W[i,i] >= 0)
    @constraint(model, [i=1:(n-1), j=(i+1):n], W[i,j] == W[j,i])
    @constraint(model, [i=1:(n-1), j=(i+1):n], W[i,j] == -A[i,j]*x[i,j] + y)
    @constraint(model, [i=1:n], W[i,i] == sum(A[i,:] .* x[i,:]) - y)

    function my_callback_function(cb)     
        x_val = callback_value.(Ref(cb), x)      
        @show x_val
    end
    MOI.set(model, MOI.LazyConstraintCallback(), my_callback_function)
    optimize!(model)

end
example_lazy_constraint_mod()

CPLEX output

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                            0.8351        1.2827            53.59%
      0     0        1.2827     3        0.8351        1.2827        3   53.59%
x_val = [-0.0 0.906081 1.0 0.0; 0.906081 -0.0 0.370528 0.723391; 1.0 0.370528 -0.0 0.0; -0.0 0.723391 -0.0 -0.0]
      0     0        1.0958     5        0.8351      Cuts: 15       11   31.21%
x_val = [-0.0 0.818876 0.0 0.952067; 0.818876 -0.0 0.229057 0.0479327; -0.0 0.229057 -0.0 0.952067; 0.952067 0.0479327 0.952067 -0.0]
      0     0        0.9546     6        0.8351      Cuts: 10       13   14.30%
x_val = [-0.0 0.577504 0.809889 0.0351035; 0.577504 -0.0 0.577504 0.964896; 0.809889 0.577504 -0.0 0.0351035; 0.0351035 0.964896 0.0351035 -0.0]
      0     0        0.9257     6        0.8351       Cuts: 3       14   10.85%
x_val = [-0.0 0.440223 0.559777 0.559777; 0.440223 -0.0 0.440223 0.440223; 0.559777 0.440223 -0.0 0.559777; 0.559777 0.440223 0.559777 -0.0]
x_val = [-0.0 0.440223 0.559777 0.559777; 0.440223 -0.0 0.440223 0.440223; 0.559777 0.440223 -0.0 0.559777; 0.559777 0.440223 0.559777 -0.0]
      0     0        0.9257     6        0.8351        0.8351       14    0.00%
Elapsed time = 0.02 sec. (0.65 ticks, tree = 0.01 MB, solutions = 1)

[odow]

This is expected behavior. See the JuMP documentation:
https://www.juliaopt.org/JuMP.jl/dev/callbacks/#Lazy-constraints-1

In particular:

The lazy constraint callback may be called at fractional or integer nodes in the branch-and-bound tree. There is no guarantee that the callback is called at every feasible primal solution.

[harshangrjn]

@odow Thanks! Now it's not clear to me what is the difference between lazy and user callback functions if lazy callback is also invoked at fractional points. As in the purpose of the user callback is not clear.

[odow]

LazyConstraints can cut off integer solutions. UserCuts can only tighten the LP hull, they can't cut off integer solutions.

[harshangrjn]

Right! Now it's weird as we have to verify if the solution at the node is indeed integral before adding the cuts, as these cuts may not be valid for fractional points. This wasn't the case before.

[harshangrjn]

@odow CPLEX seems to work fine while adding the lazy cuts only on integral solutions. But the same implementation with Gurobi seems to be still having an error (posted below). I have a constraint of this type in the callback:

con = @build_constraint(sum(x[i,j] for i in [1,2,3], j in [4,5,6]) >= 1)  
MOI.submit(m, MOI.LazyConstraint(cb), con)

Root relaxation: objective 1.040710e+02, 25 iterations, 0.01 seconds

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

     0     0  104.07101    0    7          -  104.07101      -     -    0s
     0     0   71.18617    0   14          -   71.18617      -     -    2s
     0     0   67.75715    0   14          -   67.75715      -     -    2s
     0     0   67.72939    0   14          -   67.72939      -     -    2s
     0     0   67.37568    0   14          -   67.37568      -     -    2s
ERROR: LoadError: Gurobi.GurobiError(10011, "Must set LazyConstraints parameter to use lazy constraints")

Any idea on what this issue is?

[odow]

You need to set the LazyConstraints parameter:

MOI.set(model, MOI.RawParameter("LazyConstraints"), 1)

[mlubin]

LazyConstraints was set automatically under MPB, any reason not to do that again when a lazy constraint callback is present?

[odow]

MOI.CallbackNodeStatus is now in MOI. We just need something like

function callback_node_status(cb_data, model::Model)
    return MOI.get(model, MOI.CallbackNodeStatus(cb_data))::MOI.CallbackNodeStatusCode
end

with docs and tests.

Although this comment probably applies:

JuMP.jl/src/callbacks.jl

Lines 20 to 28 in f47b18c

	# TODO(odow):
	# MOI defines `is_set_by_optimize(::CallbackVariablePrimal) = true`.
	# This causes problems for JuMP because it checks the termination_status to
	# see if optimize! has been called. Solutions are:
	# 1) defining is_set_by_optimize = false
	# 2) adding a flag to JuMP to store whether it is in a callback
	# 3) adding IN_OPTIMIZE to termination_status for callbacks
	# Once this is resolved, we can replace the current function with:
	# MOI.get(owner_model(x), MOI.CallbackVariablePrimal(cb_data), x)