JuMP 0.18: how to obtain the root relaxation of a branch and cut model?

#1

Dear community,

as the title suggests, I want to obtain the root relaxation of a branch & cut algorithm. More precisely, if the relaxation is fractional I like to add violated cuts and resolve as long as no violated cuts can be found.

I tried it with an adapted version of the example provided in the JuMP documentation documentation, with both CPLEX and Gurobi (see the code example below).

According to the Gurobi documentation parameters PreCrush and CutPasses should do the trick, since user cuts are not added in the root node by default. However, in the example below the callback is not even called, if node_limit=0.

If CPLEX is used, the callback is called but it has no impact, i.e., the problem is not resolved. I pointed that in this thread of last week, and it seemed that this is an issue of the CPLEX.jl. However, as this example shows the problem could be somewhere else.

So the questions are:
Is this an issue of JuMP, or of CPLEX.jl and Gurobi.jl?
How can I overcome this issue to obtain the root relaxation ?

Thank you in advance, mike

Here is the example code:

## ROOT RELAXATION TEST
#########################
using JuMP
using Gurobi
using CPLEX


#BUILD MODEL
function build_model( solver_type::Int, node_limit::Int )
    if( solver_type == 1 ) #GUROBI
        m = Model(solver=GurobiSolver(PreCrush=1,
                                      CutPasses=1000,
                                      NodeLimit=node_limit,
                                      Cuts=0,
                                      Presolve=0,
                                      Threads=1,
                                      Heuristics=0.0))

    elseif( solver_type == 2 ) #CPLEX
        m = Model( solver=CplexSolver(CPXPARAM_MIP_Limits_Nodes = node_limit,
                                      CPXPARAM_Threads = 1,
                                      CPXPARAM_MIP_Display = 2,

                                      #deactivate general purpose cuts
                                      CPXPARAM_MIP_Limits_EachCutLimit = 0,
                                      CPXPARAM_MIP_Cuts_Gomory = -1,
                                      CPXPARAM_MIP_Cuts_LiftProj = -1,
                                      CPXPARAM_MIP_Strategy_CallbackReducedLP = 0,

                                      #deactivate preprocessing
                                      CPXPARAM_Preprocessing_Presolve = 0,
                                      CPXPARAM_Preprocessing_Relax = 0,
                                      CPXPARAM_Preprocessing_RepeatPresolve = 0,
                                      CPXPARAM_MIP_Strategy_PresolveNode = -1,
                                      CPXPARAM_MIP_Strategy_Probe = -1,

                                      #deactivate  heuristics
                                      CPXPARAM_MIP_Strategy_HeuristicFreq = -1,
                                      CPXPARAM_MIP_Strategy_RINSHeur = -1,
                                      CPXPARAM_MIP_Strategy_FPHeur = -1,
                                      CPXPARAM_MIP_Strategy_LBHeur = 0))
    end
    return m
end

#CALLBACK
function mycutgenerator(cb)
    x_val = getvalue(x)
    y_val = getvalue(y)
    println("In callback function, x=$x_val, y=$y_val")

    # Allow for some impreciseness in the solution
    TOL = 1e-6

    # Check top right
    if y_val + x_val > 3 + TOL
        # Cut off this solution
        println("Fractional solution was in top right, cut it off")
        # Use the original variables
        @usercut(cb, y + x <= 3)
    end
end  # End of callback function


#MAIN
#parameters
solver_type = 1
node_limit  = 0

#build model
m = build_model( solver_type, node_limit )
@variable(m, 0 <= x <= 2, Int)
@variable(m, 0 <= y <= 2, Int)
@objective(m, Max, x + 2y)
@constraint(m, y + x <= 3.5)
addcutcallback(m, mycutgenerator)

# solve problem
solve(m)

# print solution
println("Final solution: [ $(getvalue(x)), $(getvalue(y)) ]")
println("nBB nodes: ", getnodecount(m))
#2

One option is to just solve the LP relaxation and iteratively add the cuts.

Can you be more explicit in what you expect to see vs what you actually see? Remember that JuMP 0.18 doesn’t provide any guarantees about when (and if) your callbacks will be called.

Similar questions have been asked in this forum before. I can’t remember what the outcomes were, but it might be useful to search through some of the previous answers.

#3

I was not aware about the issue that callbacks are not called “as usual” in JuMP. Does this mean that B&C algorithms may considerably not perform as good as similar implementations in, e.g., C once the solving process is started?
I get your point that just for obtaining the relaxation I could add the cuts manually - thank you.

I expect to see something like this (but only for the root node):

Root relaxation: objective 5.500000e+00, 1 iterations, 0.00 seconds

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

     0     0    5.50000    0    1          -    5.50000      -     -    0s
In callback function, x=1.5, y=2.0
Fractional solution was in top right, cut it off
*    0     0               0       5.0000000    5.00000  0.00%     -    0s

Cutting planes:
  User: 1

Explored 1 nodes (2 simplex iterations) in 0.14 seconds

which I only obtain if node_limit=1 in case of Gurobi.

What I actually see is this:

Root relaxation: objective 5.500000e+00, 1 iterations, 0.00 seconds

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

     0     0    5.50000    0    1          -    5.50000      -     -    0s

Explored 0 nodes (1 simplex iterations) in 0.00 seconds
Thread count was 1 (of 12 available processors)

In case of CPLEX I see this

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

      0     0        5.5000     1                      5.5000        1
In callback function, x=1.5, y=2.0
Fractional solution was in top right, cut it off

User cuts applied:  1

But as I said, the cut is seemingly added but it has no impact.