Retrieve UserCuts' slack for sensitivity analysis

Specific Domains Optimization (Mathematical)
,
1

Settings: Julia 1.8, JuMP 1.13.0, Gurobi.jl 1.0.2

I have been trying to check which type of cuts that I included through callbacks are still active.

  • As shown in Gurobi’s log, the initial formulation has 9010 constraints.
  • During the branch-and-bound, I separate 2 types of constraints on fractional solutions and, when a violation is found, I keep track of how many cuts I applied for each one.
  • For this instance, 1 cut of type “A” and 6 of type “B” were added but only one is binding in the optimal solution as per Gurobi’s log.
Optimize a model with 9010 rows, 1118 columns and 33885 nonzeros
Model fingerprint: 0x0d75667f
Variable types: 94 continuous, 1024 integer (1024 binary)
Coefficient statistics:
  Matrix range     [2e-02, 1e+03]
  Objective range  [1e+00, 1e+04]
  Bounds range     [0e+00, 0e+00]
  RHS range        [5e-14, 1e+03]
Presolve removed 8335 rows and 872 columns
Presolve time: 0.02s
Presolved: 675 rows, 246 columns, 3559 nonzeros
Variable types: 77 continuous, 169 integer (169 binary)
Found heuristic solution: objective 50789.110000

Root relaxation: objective 2.054028e+04, 137 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 20540.2850    0   16 50789.1100 20540.2850  59.6%     -    0s
     0     0 20542.8500    0    - 50789.1100 20542.8500  59.6%     -    1s
     0     0 20543.7700    0   14 50789.1100 20543.7700  59.6%     -    1s
H    0     0                    40702.450000 20543.7700  49.5%     -    2s
H    0     0                    30587.930000 20543.7700  32.8%     -    2s
     0     2 20545.5950    0    6 30587.9300 20545.5950  32.8%     -    2s
*   19     9               4    20577.570000 20549.0600  0.14%  16.6    2s
*   23     0               5    20575.760000 20549.7150  0.13%  16.2    2s

Cutting planes:
  User: 1
  Lazy constraints: 26

Explored 28 nodes (614 simplex iterations) in 2.61 seconds (0.05 work units)
Thread count was 8 (of 8 available processors)

Solution count 5: 20575.8 20577.6 30587.9 ... 50789.1

Optimal solution found (tolerance 1.00e-07)
Best objective 2.057576000000e+04, best bound 2.057576000000e+04, gap 0.0000%

To check the constraints slack, I do as suggested in this doc.

function constraint_report(c::ConstraintRef)
    return (
        value = value(c),
        rhs = normalized_rhs(c),
        slack = normalized_rhs(c) - value(c),
    )
end

constraint_df = DataFrames.DataFrame(
    constraint_report(ci) for (F, S) in list_of_constraint_types(model) for
    ci in all_constraints(model, F, S) if F == AffExpr
)
display(constraint_df)

However, it shows just the 9010 initial constraints, i.e., it doesn’t included the added cut.

9010×3 DataFrame
Row│ value    rhs      slack        
       │ Float64  Float64  Float64
──────────────────────────────────────
    1 │     1.0      1.0   0.0
    2 │     1.0      1.0   0.0
    3 │     1.0      1.0   0.0
    4 │     1.0      1.0   0.0
    5 │     1.0      1.0   0.0
    6 │     1.0      1.0   0.0
    7 │     1.0      1.0   0.0
    8 │     1.0      1.0   0.0
    9 │     1.0      1.0   0.0
   10 │     1.0      1.0   0.0
   11 │     1.0      1.0   0.0
   12 │     1.0      1.0   0.0
   13 │     1.0      1.0   0.0
   14 │     1.0      1.0   0.0
   15 │     1.0      1.0   0.0
   16 │     1.0      1.0   0.0
   17 │     1.0      1.0   1.11022e-16
   18 │     1.0      1.0   0.0
  ⋮   │    ⋮        ⋮          ⋮
 8993 │     0.0      1.0   1.0
 8994 │     0.0      1.0   1.0
 8995 │     0.0      1.0   1.0
 8996 │     0.0      1.0   1.0
 8997 │     0.0      1.0   1.0
 8998 │     0.0      1.0   1.0
 8999 │     0.0      1.0   1.0
 9000 │     0.0      1.0   1.0
 9001 │     0.0      1.0   1.0
 9002 │     0.0      1.0   1.0
 9003 │     0.0      1.0   1.0
 9004 │     0.0      1.0   1.0
 9005 │     0.0      1.0   1.0
 9006 │     0.0      1.0   1.0
 9007 │     0.0      1.0   1.0
 9008 │     0.0      1.0   1.0
 9009 │     1.0      1.0   0.0
 9010 │     0.0      1.0   1.0
                      8974 rows omitted

I wonder if there is a way of retrieving which added UserCut is binding in the optimal solution.

Let me know if more details are needed. Thanks in advance.

1 Like
2

Hi @abreualexp, welcome to the forum!

There is no support for this because user-cuts are not added as constraints to the JuMP model; they are a solution hint to the solver.

In your callback, you should store the cuts you are adding in an appropriate data structure. So something like this:

julia> using JuMP, GLPK

julia> begin
           N = 30
           item_weights, item_values = rand(N), rand(N)
           model = Model(GLPK.Optimizer)
           @variable(model, x[1:N], Bin)
           @constraint(model, item_weights' * x <= 10)
           @objective(model, Max, item_values' * x)
           list_of_cuts = Any[]
           function my_callback_function(cb_data)
               x_vals = callback_value.(Ref(cb_data), x)
               selected = x_vals .> 1e-4
               if sum(item_weights[selected]) > 10
                   con = @build_constraint(sum(x[selected]) <= sum(selected) - 1)
                   push!(list_of_cuts, con)
                   MOI.submit(model, MOI.UserCut(cb_data), con)
               end
               return
           end
           set_attribute(model, MOI.UserCutCallback(), my_callback_function)
           optimize!(model)
       end

julia> slack(con) = MOI.constant(con.set) - value(con.func)
slack (generic function with 1 method)

julia> slack.(list_of_cuts)
8-element Vector{Float64}:
 0.0
 0.0
 1.0
 0.0
 1.0
 0.0
 1.0
 0.0
1 Like
3

Hello @odow . Thank you for your fast reply.

It worked just fine.

For a correlated topic:
If I find a lot of cuts I might want to delete some that are not binding.
Is there a way to call slack() within the callback? I’ve tried and got the following:

┌ Warning: The model has been modified since the last call to `optimize!` (or `optimize!` has not been called yet). If you are iteratively querying solution information and modifying a model, query all the results first, then modify the model.
└ @ JuMP ..\JuMP\jZvaU\src\optimizer_interface.jl:670     
ERROR: OptimizeNotCalled()
4

You cannot delete user cuts. Note that they are a solution hint to the solver. They cannot change the feasible area, and the solver is free to ignore them.

You cannot use value in a callback. You need to use callback_value instead. So something like this:

julia> using JuMP, GLPK

julia> begin
           slack(f, con) = MOI.constant(con.set) - f(con.func)
           slack(con) = slack(value, con)
           callback_slack(cb_data, con) = slack(y -> callback_value(cb_data, y), con)
           N = 30
           item_weights, item_values = rand(N), rand(N)
           model = Model(GLPK.Optimizer)
           @variable(model, x[1:N], Bin)
           @constraint(model, item_weights' * x <= 10)
           @objective(model, Max, item_values' * x)
           list_of_cuts = Any[]
           function my_callback_function(cb_data)
               x_vals = callback_value.(Ref(cb_data), x)
               selected = x_vals .> 1e-4
               @show callback_slack.(Ref(cb_data), list_of_cuts)
               if sum(item_weights[selected]) > 10
                   con = @build_constraint(sum(x[selected]) <= sum(selected) - 1)
                   push!(list_of_cuts, con)
                   MOI.submit(model, MOI.UserCut(cb_data), con)
               end
               return
           end
           set_attribute(model, MOI.UserCutCallback(), my_callback_function)
           optimize!(model)
       end
callback_slack.(Ref(cb_data), list_of_cuts) = Any[]
callback_slack.(Ref(cb_data), list_of_cuts) = [0.0]
callback_slack.(Ref(cb_data), list_of_cuts) = [0.0, 0.0]
callback_slack.(Ref(cb_data), list_of_cuts) = [0.6104967861582864, 0.6104967861582864, 0.0]
callback_slack.(Ref(cb_data), list_of_cuts) = [0.0, 0.0, 1.0, 1.0]
callback_slack.(Ref(cb_data), list_of_cuts) = [0.09290023379396573, 0.09290023379396573, 1.0929002337939657, 1.0929002337939657, 0.09290023379396573]
1 Like
5

Great.

Thank you once again.

Kind regards,
Alex

1 Like