Branching solution accepted although it violates presently added lazy constraints

I can not produce a MWE because the code is too big so I am going to describe.

I have a JuMP model and Gurobi optimizer. I launch a callback where cb_where is MIP_SOL and all my variables are integer. On this callback, right after the entry of it, I have a solution x_cb of objective value let’s say x_cb_obj::Float64 to simplify. Later on the callback, I add a lazy constraint and I know x_cb violates this lazy constraint. My concern is that after the exit of my callback, Gurobi outputs a new incumbent of value x_cb_obj. How is that possible given that x_cb violates my lazy constraint?

Here are outputs and codes (not MWE unfortunately):

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

We enter the callback 387555.5 # CODE 1
We have added a lazy constraint. Solution of value 387555.5 violates this lazy constraint # CODE 2
* 4414  3156             246    387555.50000 144201.567  62.8%   7.2    9s # How is this new incumbent possible?
[...]

Here, 387555.50000 is x_cb_obj

# CODE 1:
            resultP = Ref{Cdouble}()
            GRBcbget(cb_data, cb_where, GRB_CB_MIPSOL_OBJBST,resultP)
            println("We enter the callback $(resultP[])")
# CODE 2:
            con = @build_constraint(λ ≥ sum([2(1-y[i])α[i] for i in V]) +
                    sum([(x[mima(β[j][1],j)] + x[mima(β[j][2],j)] - 1)rp[mima(β[j][1],β[j][2])] for j in tildeV if length(β[j]) > 0]) - sum([y[j]γ[i,j] for i in V, j in V if i != j]))
            MOI.submit(m, MOI.LazyConstraint(cb_data), con)
println("We added a lazy constraint. Solution of value $(resultP[]) violates this lazy constraint")

Improving my post thanks to @miles.lubin: for the example given above, the violation of the lazy constraint is by 191 537, so I believe it is not Float64 tolerance related :slight_smile:

1 Like

By how much does the solution violate the constraint that you added? Gurobi could ignore the lazy constraint if it’s satisfied within Gurobi’s tolerances.

They are violated by a lot. Typically for 387555.5, the lazy constraint is violated by 191537
This is not a float tolerances issue :slight_smile: I am improving my post thanks to your comment.

1 Like

I don’t think there are any guarantees on when Gurobi will accept your lazy constraint. The only guarantee is that the final optimal solution will satisfy all lazy constraints that have been added.

Does the final solution violate any of the lazy constraints?

The only guarantee that Gurobi gives with respect to lazy constraints is the following: before accepting an integer point as incumbent (the solution with current best objective value), Gurobi will always give you the opportunity to reject it.

In order to reject an incumbent, you must provide a constraint that cuts off the current solution (subject to numerical tolerances). In other words, you must provide one or more constraint(s) of the form a^{T}x \geq b with a^{T} \bar{x} < b (inequality), or a^{T}x = b with a^{T} \bar{x} \neq b (equality). Once you have rejected a solution \bar{x}, Gurobi guarantees that you will never encounter \bar{x} again.

What Gurobi does not guarantee:

  • That future integer solutions will satisfy the constraint(s) you have just submitted
  • That such constraints will be included in the LP relaxation, thus…
  • … that fractional solutions will satisfy the submitted constraints

Things that can typically happen:

  • You have a bug in your code
  • The constraint you are submitting is not actually violated, causing Gurobi to accept the solution
  • There are multiple solutions with same objective value and you did not cutoff all of them. This includes the case where Gurobi rejected the previous candidate solution but chose not to include the constraint in the formulation.

For debugging, you can keep track of all the solutions you encountered within the callback. If you see the same solution twice, then congratulations, you may have found a bug in Gurobi! If you never encounter the same solution twice, then consider some of the points above (especially the third one).

5 Likes

We discuss this briefly in the documentation: Solver-independent Callbacks · JuMP

Suggestions for improvements are welcome.

1 Like