An empty callback function makes the solver unable to find any feasible solution
Awaiting user inputHi,
I am trying to implement the Branch and Benders Cut algorithm using callback functions. My simplified code setup has:
// master.cpp file
// Initialize the master problem class
Master::Master(){
class_sub_problem = new Sub();
model_master = new GRBModel(env);
// Enable lazy constraints
model_master->set(GRB_IntParam_LazyConstraints, 1);
// Create and set the callback
BendersCutCallback* cb = new BendersCutCallback(this, class_sub_problem);
model_master->setCallback(cb);
}
For verification, I put an empty callback function:
// master.cpp file
class BendersCutCallback : public GRBCallback {
private:
Master* master;
Sub* sub_problem;
protected:
void callback() override {
// Currently empty
}
public:
BendersCutCallback(Master* master_problem, Sub* sub_solver)
: master(master_problem), sub_problem(sub_solver){}
};
When it is non-empty, the purpose of this callback is such that every time a binary feasible solution is found by Gurobi in the branch-and-bound process of solving the master problem, it calls the sub-problem to get a cost if the subproblem is feasible or add a cut if the subproblem is infeasible. For now, I put objective=0 so the solver only tries to find a feasible solution.
When I tested it, something strange happened. If I commented out this line:
// model_master->set(GRB_IntParam_LazyConstraints, 1);
The solver finds a feasible solution within 1 sec, as I usually observe for my problem. Here is the output:
Gurobi Optimizer version 12.0.0 build v12.0.0rc1 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: 12th Gen Intel(R) Core(TM) i7-12800H, instruction set [SSE2|AVX|AVX2]
Thread count: 20 physical cores, 20 logical processors, using up to 20 threads
Non-default parameters:
MIPGap 0.1
Optimize a model with 6003 rows, 1419 columns and 14248 nonzeros
Model fingerprint: 0x59b4cc67
Model has 151 quadratic constraints
Variable types: 1109 continuous, 310 integer (310 binary)
Coefficient statistics:
Matrix range [2e-01, 1e+01]
QMatrix range [4e-02, 4e+01]
QLMatrix range [7e+00, 7e+00]
Objective range [0e+00, 0e+00]
Bounds range [5e-03, 1e+10]
RHS range [1e-01, 3e+01]
QRHS range [7e-01, 4e+01]
Warning: Model contains large bounds
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 3420 rows and 513 columns
Presolve time: 0.03s
Presolved: 2583 rows, 906 columns, 7289 nonzeros
Presolved model has 118 quadratic constraint(s)
Variable types: 676 continuous, 230 integer (230 binary)
Root relaxation: objective 0.000000e+00, 812 iterations, 0.01 seconds (0.03 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 62 - 0.00000 - - 0s
0 0 0.00000 0 68 - 0.00000 - - 0s
0 0 0.00000 0 61 - 0.00000 - - 0s
0 0 0.00000 0 11 - 0.00000 - - 0s
0 0 0.00000 0 25 - 0.00000 - - 0s
0 0 0.00000 0 13 - 0.00000 - - 0s
0 0 0.00000 0 33 - 0.00000 - - 0s
0 0 0.00000 0 12 - 0.00000 - - 0s
0 0 0.00000 0 15 - 0.00000 - - 0s
0 0 0.00000 0 16 - 0.00000 - - 0s
0 0 0.00000 0 8 - 0.00000 - - 0s
0 0 0.00000 0 8 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 11 - 0.00000 - - 0s
0 0 0.00000 0 14 - 0.00000 - - 0s
0 0 0.00000 0 52 - 0.00000 - - 0s
0 0 0.00000 0 45 - 0.00000 - - 0s
0 0 0.00000 0 45 - 0.00000 - - 0s
0 0 0.00000 0 16 - 0.00000 - - 0s
0 0 0.00000 0 15 - 0.00000 - - 0s
0 0 0.00000 0 18 - 0.00000 - - 0s
0 0 0.00000 0 14 - 0.00000 - - 0s
H 0 0 0.0000000 0.00000 0.00% - 0s
Cutting planes:
Cover: 5
Implied bound: 27
Clique: 9
MIR: 30
Flow cover: 1
GUB cover: 2
Zero half: 1
RLT: 7
Relax-and-lift: 18
Explored 1 nodes (8103 simplex iterations) in 0.58 seconds (0.69 work units)
Thread count was 20 (of 20 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-01)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
User-callback calls 954, time in user-callback 0.00 sec
However, if this line is not commented out, the solver cannot find any feasible solution despite minutes of search. Here is the output:
Gurobi Optimizer version 12.0.0 build v12.0.0rc1 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: 12th Gen Intel(R) Core(TM) i7-12800H, instruction set [SSE2|AVX|AVX2]
Thread count: 20 physical cores, 20 logical processors, using up to 20 threads
Non-default parameters:
MIPGap 0.1
LazyConstraints 1
Optimize a model with 6003 rows, 1419 columns and 14248 nonzeros
Model fingerprint: 0x59b4cc67
Model has 151 quadratic constraints
Variable types: 1109 continuous, 310 integer (310 binary)
Coefficient statistics:
Matrix range [2e-01, 1e+01]
QMatrix range [4e-02, 4e+01]
QLMatrix range [7e+00, 7e+00]
Objective range [0e+00, 0e+00]
Bounds range [5e-03, 1e+10]
RHS range [1e-01, 3e+01]
QRHS range [7e-01, 4e+01]
Warning: Model contains large bounds
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 3375 rows and 488 columns
Presolve time: 0.02s
Presolved: 2628 rows, 931 columns, 7490 nonzeros
Presolved model has 119 quadratic constraint(s)
Variable types: 717 continuous, 214 integer (214 binary)
Root relaxation: objective 0.000000e+00, 848 iterations, 0.02 seconds (0.03 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 15 - 0.00000 - - 0s
0 0 0.00000 0 19 - 0.00000 - - 0s
0 0 0.00000 0 19 - 0.00000 - - 0s
0 0 0.00000 0 20 - 0.00000 - - 0s
0 0 0.00000 0 17 - 0.00000 - - 0s
0 0 0.00000 0 11 - 0.00000 - - 0s
0 0 0.00000 0 11 - 0.00000 - - 0s
0 0 0.00000 0 14 - 0.00000 - - 0s
0 0 0.00000 0 15 - 0.00000 - - 0s
0 0 0.00000 0 13 - 0.00000 - - 0s
0 0 0.00000 0 13 - 0.00000 - - 0s
0 0 0.00000 0 10 - 0.00000 - - 0s
0 0 0.00000 0 10 - 0.00000 - - 0s
0 0 0.00000 0 3 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 9 - 0.00000 - - 0s
0 0 0.00000 0 10 - 0.00000 - - 0s
0 2 0.00000 0 10 - 0.00000 - - 0s
22626 391 0.00000 25 - - 0.00000 - 11.6 5s
40884 293 0.00000 28 1 - 0.00000 - 9.4 10s
51070 245 0.00000 34 - - 0.00000 - 9.0 15s
60623 284 0.00000 38 1 - 0.00000 - 8.7 20s
67304 239 0.00000 26 1 - 0.00000 - 8.4 25s
75564 220 0.00000 30 3 - 0.00000 - 8.3 31s
This happens despite the callback does not do anything. From my understanding, model_master->set(GRB_IntParam_LazyConstraints, 1) should be there if we want to use callback functions. Do you have any clue why this happens?
I can save my model into a file and upload it to Google Drive, so that you can run my model, if necessary.
Thank you!
Xuan Lin
-
Hi Xuan Lin,
Activating the LazyConstraints parameter disables some presolve reductions which would interfer with lazy constraints. From the docs
The parameter tells the Gurobi algorithms to avoid certain reductions and transformations that are incompatible with lazy constraints.
In particular it disables DualReductions. This can already be enough to change the solution process by a lot.
Best regards,
Jaromił0 -
Hi Jaromił,
Thank you for the explanation! I have a follow-up question regarding this issue. Are the techniques disabled by activating
LazyConstraints
inherently incompatible with lazy constraints, or is there a workaround to mitigate the slowdown?To better understand the impact of
DualReductions
, I modified my code as follows:// model_master->set(GRB_IntParam_LazyConstraints, 1);
model_master->set(GRB_IntParam_DualReductions, 0);The results showed some slowdown, but it was not as significant as the initial observations:
Gurobi Optimizer version 12.0.0 build v12.0.0rc1 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: 12th Gen Intel(R) Core(TM) i7-12800H, instruction set [SSE2|AVX|AVX2]
Thread count: 20 physical cores, 20 logical processors, using up to 20 threads
Non-default parameters:
MIPGap 0.1
DualReductions 0
Optimize a model with 6003 rows, 1419 columns and 14248 nonzeros
Model fingerprint: 0x59b4cc67
Model has 151 quadratic constraints
Variable types: 1109 continuous, 310 integer (310 binary)
Coefficient statistics:
Matrix range [2e-01, 1e+01]
QMatrix range [4e-02, 4e+01]
QLMatrix range [7e+00, 7e+00]
Objective range [0e+00, 0e+00]
Bounds range [5e-03, 1e+10]
RHS range [1e-01, 3e+01]
QRHS range [7e-01, 4e+01]
Warning: Model contains large bounds
Consider reformulating model or setting NumericFocus parameter
to avoid numerical issues.
Presolve removed 3375 rows and 488 columns
Presolve time: 0.02s
Presolved: 2628 rows, 931 columns, 7490 nonzeros
Presolved model has 119 quadratic constraint(s)
Variable types: 717 continuous, 214 integer (214 binary)
Root relaxation: objective 0.000000e+00, 848 iterations, 0.01 seconds (0.03 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.00000 0 15 - 0.00000 - - 0s
0 0 0.00000 0 19 - 0.00000 - - 0s
0 0 0.00000 0 19 - 0.00000 - - 0s
0 0 0.00000 0 20 - 0.00000 - - 0s
0 0 0.00000 0 17 - 0.00000 - - 0s
0 0 0.00000 0 12 - 0.00000 - - 0s
0 0 0.00000 0 35 - 0.00000 - - 0s
0 0 0.00000 0 32 - 0.00000 - - 0s
0 0 0.00000 0 10 - 0.00000 - - 0s
0 0 0.00000 0 10 - 0.00000 - - 0s
0 0 0.00000 0 10 - 0.00000 - - 0s
0 0 0.00000 0 17 - 0.00000 - - 0s
0 0 0.00000 0 8 - 0.00000 - - 0s
0 0 0.00000 0 13 - 0.00000 - - 0s
0 0 0.00000 0 10 - 0.00000 - - 0s
0 0 0.00000 0 16 - 0.00000 - - 0s
Get better solution 4.53605
Gap: 1e+02%
H 0 0 0.0000000 0.00000 0.00% - 1s
0 0 0.00000 0 19 0.00000 0.00000 0.00% - 1s
Cutting planes:
Cover: 3
Implied bound: 3
MIR: 35
Flow cover: 3
RLT: 8
Relax-and-lift: 5
BQP: 4
Explored 1 nodes (6229 simplex iterations) in 1.35 seconds (0.44 work units)
Thread count was 20 (of 20 available processors)
Solution count 1: 0
Optimal solution found (tolerance 1.00e-01)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
User-callback calls 579, time in user-callback 1.05 secThis leads me to believe that other parameters might also play a major role in the slowdown. Could you suggest a list of parameters that I might experiment with to identify the primary contributors?
Thank you!
Xuan Lin
0 -
Hi Xuan Lin,
Are the techniques disabled by activating
LazyConstraints
inherently incompatible with lazy constraints, or is there a workaround to mitigate the slowdown?The deactivated techniques are inherently incompatible with lazy constraints. Thus, unfortunately there is no workaround.
This leads me to believe that other parameters might also play a major role in the slowdown. Could you suggest a list of parameters that I might experiment with to identify the primary contributors?
It may be model dependent. Could you please share the model you presented such that we could take a closer look? Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments