How to add lazy constraint using callback?
Answered
Hi all,
I have wrote the original model before, now I want to define so constraints as lazy constraints by using callback.
The original nonlinear constraint :
c[i][j][k] * v[j][k] = c[j][h][k]is written:
for (int j = 1; j < instance.nodesNum - 1; j++) {
for (int k = 0; k < instance.vehiclesNum; k++) {
GRBQuadExpr expr = new GRBQuadExpr();
for (int i = 0; i < instance.nodesNum; i++) {
if (i != j) {
expr.addTerm(1, c[i][j][k], v[j][k]);
}
}
for (int h = 0; h < instance.nodesNum; h++) {
if (j != h) {
expr.addTerm(-1, c[j][h][k]);
}
}
model.addQConstr(expr, GRB.EQUAL, 0, "cos_18");
}
}
In addLazy() function, only linear constraint can be used, so I linearize the above constraint. After doing that, the model with added lazy constraint was rerun, but there was no feasible solution after a long computation.
What are the reasons for this situation?
-
Set parameter Threads to value 12
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 11+.0 (22631.2))
CPU model: 12th Gen Intel(R) Core(TM) i5-12400, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Set parameter Method to value 1
Set parameter MIPFocus to value 1
Set parameter TimeLimit to value 3600
Set parameter LazyConstraints to value 1
Warning: linear constraint 0 and linear constraint 60 have the same name "internalVar_sumZ_0_0"
Warning: quadratic constraint 4020 and quadratic constraint 4021 have the same name "cos_14"
Warning: general constraint 0 and general constraint 1 have the same name "constr_aVars[i][k][0]"
Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 11+.0 (22631.2))
CPU model: 12th Gen Intel(R) Core(TM) i5-12400, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 2413 rows, 7676 columns and 22245 nonzeros
Model fingerprint: 0xd2211c9e
Model has 4135 quadratic constraints
Model has 600 general constraints
Variable types: 2388 continuous, 5288 integer (1195 binary)
Coefficient statistics:
Matrix range [5e-01, 3e+04]
QMatrix range [1e-01, 1e+00]
QLMatrix range [1e-01, 1e+03]
Objective range [1e+00, 9e+00]
Bounds range [1e+00, 3e+04]
RHS range [5e-01, 1e+03]
QRHS range [1e-04, 3e+04]
Presolve added 35 rows and 0 columns
Presolve removed 0 rows and 1306 columns
Presolve time: 0.09s
Presolved: 21743 rows, 16045 columns, 76535 nonzeros
Presolved model has 4430 SOS constraint(s)
Presolved model has 1980 bilinear constraint(s)
Solving non-convex MIQCP
Variable types: 6463 continuous, 9582 integer (3765 binary)
Root relaxation: objective 3.685120e+01, 16506 iterations, 0.83 seconds (1.06 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 36.85120 0 4925 - 36.85120 - - 1s
0 0 36.85120 0 4988 - 36.85120 - - 2s
0 0 36.85120 0 5186 - 36.85120 - - 2s
0 0 36.85120 0 5451 - 36.85120 - - 3s
0 0 36.85120 0 5249 - 36.85120 - - 3s
0 0 36.85120 0 5327 - 36.85120 - - 3s
0 0 36.85120 0 5340 - 36.85120 - - 4s
0 0 36.85120 0 5310 - 36.85120 - - 4s
0 0 36.85120 0 5301 - 36.85120 - - 4s
0 0 36.85120 0 5350 - 36.85120 - - 5s
0 0 36.85120 0 5308 - 36.85120 - - 5s
0 0 36.85120 0 4887 - 36.85120 - - 6s
0 0 36.85120 0 5007 - 36.85120 - - 7s
0 0 36.85120 0 4935 - 36.85120 - - 8s
0 0 36.85120 0 4893 - 36.85120 - - 8s
......
37580 14925 44.02673 28 1782 45.20000 40.84175 9.64% 2094 3165s
38819 15305 44.53873 28 1064 45.20000 40.88571 9.54% 2088 3248s
40139 15738 41.14821 25 1402 45.20000 40.91276 9.49% 2078 3331s
41568 16266 infeasible 30 45.20000 40.93994 9.42% 2069 3413s
43067 16738 43.11354 28 848 45.20000 40.96087 9.38% 2057 3507s
44419 17215 43.61052 29 875 45.20000 40.98026 9.34% 2046 3590s
45836 17294 43.48187 25 1316 45.20000 40.99963 9.29% 2037 3600s
Cutting planes:
Gomory: 1
Cover: 30
Implied bound: 1086
Clique: 26
MIR: 204
StrongCG: 9
Flow cover: 495
Flow path: 66
Inf proof: 12
Zero half: 8
Network: 12
RLT: 1873
Relax-and-lift: 143
BQP: 121
PSD: 1
Explored 46027 nodes (93786381 simplex iterations) in 3600.29 seconds (3180.89 work units)
Thread count was 12 (of 12 available processors)
Solution count 10: 45.2 45.924 45.984 ... 54.237
Time limit reached
Best objective 4.520000000000e+01, best bound 4.099963149378e+01, gap 9.2929%
User-callback calls 229311, time in user-callback 1.43 secThis is my log, does this means that the callback has been successfully used?
0 -
Hi Haoxing,
This line:
User-callback calls 229311, time in user-callback 1.43 sec
tells you that the callback method is being called, however if lazy constraints were added then we should see a "Lazy constraints" entry under "Cutting planes".
Can you post your callback method?
- Riley
0 -
Hi Riley,
So glad to get your answered. Here's my callback method, I will use one of the lazy constraints as an example:
package Model.Main;
import Model.Instance;
import com.gurobi.gurobi.*;
public class LazyCallback extends GRBCallback {
private GRBVar[][][] c;
private GRBVar[][][] X;
private Instance instance;
public LazyCallback(GRBVar[][][] c, GRBVar[][][] X, Instance instance) {
this.c = c;
this.X = X;
this.instance = instance;
}
@Override
protected void callback() {
try {
if (where == GRB.CB_MIPNODE) {
int nodeStatus = this.getIntInfo(GRB.CB_MIPNODE_STATUS);
if (nodeStatus == GRB.OPTIMAL) {
/**
* Constraint：c[i][j][k] <= X[i][j][k]
*/
for (int k = 0; k < instance.vehiclesNum; k++) {
for (int i = 0; i < instance.nodesNum; i++) {
for (int j = 0; j < instance.nodesNum; j++) {
double cVal = getSolution(c[i][j][k]);
double xVal = getSolution(X[i][j][k]);
if (cVal > xVal) {
GRBLinExpr lhs = new GRBLinExpr();
lhs.addTerm(1.0, c[i][j][k]);
lhs.addTerm(-1.0, X[i][j][k]);
addLazy(lhs, GRB.LESS_EQUAL, 0);
}
}
}
}
}
}
} catch (GRBException e) {
System.out.println("Error code: " + e.getErrorCode() + ". " + e.getMessage());
}
}
}After I build the callback method, I call it in the main model:
LazyCallback callback = new LazyCallback(c, X, instance);
model.setCallback(callback);
model.optimize();May | ask if this operation correctly uses the callback method?
Why does my solving speed not change after running the model within callback, sometimes even longer?
0 -
Hi Haoxing,
Are you adding lazy constraints, or cutting planes? I.e. are these necessary for validity of the solution, or just to hopefully improve performance of the solver?
Note that in the docs for addLazy it says:
You would typically add a lazy constraint by first querying the current node solution (by calling getSolution from a
GRB.CB_MIPSOLcallback, or getNodeRel from aGRB.CB_MIPNODEcallback), and then callingaddLazy()to add a constraint that cuts off the solutionCan you try replacing getSolution with getNodeRel in your callback code?
Do you have
model.set(GRB.IntParam.LazyConstraints, 1);
somewhere in your code?
Can you try adding a public int to your callback class, and increase its value in the line after
addLazy(lhs, GRB.LESS_EQUAL, 0);then query its value after the model has solved, to see if this code is reached?
- Riley
0 -
Hi Riley,
Thank you for your reminder. It's true that the "where"setting in my callback class is incorrect. Since I am adding a lazy constraint, it should be set to where==GRB CB-MIPSOL.
I ran the model again and displayed “Lazy Constraint” in “Cutting Planes”：
Cutting planes:
Gomory: 2
Implied bound: 377
MIR: 136
StrongCG: 4
Flow cover: 61
Zero half: 15
Network: 16
RLT: 474
Relax-and-lift: 20
BQP: 79
Lazy constraints: 2Now I am facing with a new problem is: solving the model directly is faster than using Lazy constraints.
May I ask what the reason is?
0 -
Hi Haoxing,
When you say solving the model directly is faster, do you mean adding all
c[i][j][k] <= X[i][j][k]
constraints into the model at the beginning, instead of using a callback?
- Riley
0 -
Hi Riley,
Yes, I mean solving the original model is faster than using callback method.0 -
Hi Haoxing,
Did you test this across many values of Seed, or just 1 run of each?
- Riley
0 -
Hi Riley,
After listening to your advice, I set:
model.set(GRB.IntParam.Seed, 2000000000);
I tested it with different examples, and in some cases, the solution speed using the callback method is indeed faster than sovling the original model!! But in some cases the speed of solving the original model is still faster.
So I think:
(1)The effectiveness of using the callback method still depends on the characteristics of the example, right?
(2)Does Gurobi have an official document stating that using callback will accelerate the solving speed and convergence?
0 -
Hi Haoxing,
in some cases, the solution speed using the callback method is indeed faster than sovling the original model!! But in some cases the speed of solving the original model is still faster.
This is indeed the reason why it is important to compare a distribution of run times against another. Our python package gurobi-logtools makes this easy to visualize with boxplots.
The effectiveness of using the callback method still depends on the characteristics of the example, right?
The effectiveness will depend on how expensive it is to calculate the lazy constraints, how often the callback is called, and how many lazy constraints result. All of these can depend on the instance data.
Does Gurobi have an official document stating that using callback will accelerate the solving speed and convergence?
No, because it not necessarily true. Consider a trivial example where every constraint in your model is added as a lazy constraint. This is a terrible idea... Maybe lazy constraints are a better approach, maybe they're not - you have to test. Experimentation is crucial to model building.
- Riley
0 -
Hi Riley,
Thank you very much for your reply!
Best,
Haoxing
0 -
Hi Haoxing,
Another thing I forgot to mention... This:
model.set(GRB.IntParam.LazyConstraints, 1);
does not come for free. To be able to add lazy constraints we need to turn off some presolve reductions, which in general will lead to a weaker presolve result, so there is an initial cost to pay even if you then don't add any lazy constraints during the optimization.
- Riley
0 -
Hi Riley,
Thank you for your reminder! But I'm facing another problem now. Could you please help me take a look?
What I want to solve is a Vehicle Routing Problem, using three-index variables X[i][j][k] to represent vehicle k travels from node i to j. As the model has three-index variables representing homogeneous routes of vehicles, so I want to reduce the solution symmetry with constraints(34)-(35) using "User Cut" by callback method, the deatils is in the picture:
But after adding "User Cut", the model has no solution, and I don't know if the code in the "User Cut" class is incorrect:
public class UserCut extends GRBCallback {
private GRBVar[][][] X;
private Vehicle vehicle;
private Instance instance;
public UserCut(GRBVar[][][] X, Vehicle vehicle, Instance instance) {
this.X = X;
this.vehicle = vehicle;
this.instance = instance;
}
@Override
protected void callback() {
try {
if (where == GRB.CB_MIPNODE) {
int nodeStatus = this.getIntInfo(GRB.CB_MIPNODE_STATUS);
if (nodeStatus == GRB.OPTIMAL) {
//Constraint(34)
for (int k = 1; k < instance.vehiclesNum; k++) {
for (int i = 1; i < instance.nodesNum - 1; i++) {
for (int j = 0; j < instance.nodesNum; j++) {
if (j != i) {
double lhs = getNodeRel(X[j][i][k]);
for (int h = 1; h < instance.nodesNum - 1; h++) {
double rhs = 0;
if (h != j && h <= i) {
rhs = getNodeRel(X[j][h][k - 1]);
}
if (rhs < lhs) {
GRBLinExpr expr = new GRBLinExpr();
expr.addTerm(1, X[j][i][k]);
expr.addTerm(-1, X[j][h][k - 1]);
addCut(expr, GRB.LESS_EQUAL, 0);
}
}
}
}
}
}
}
//Constraint(35)
for (int j = 0; j < instance.nodesNum; j++) {
if (j != 1) {
double var = getNodeRel(X[j][1][0]);
if (var != 1) {
GRBLinExpr expr = new GRBLinExpr();
expr.addTerm(1, X[j][1][0]);
addCut(expr, GRB.EQUAL, 1);
}
}
}
}
} catch (GRBException e) {
System.out.println("Error code: " + e.getErrorCode() + ". " + e.getMessage());
}
}
}I have already set:
model.set(GRB.IntParam.PreCrush, 1);
I really need your help.
0 -
I forgot to mention that in my code, "instance. nodesNum" includes node 0 and node n+1 (both of which are the same depot). This is a bit different from the constraints(34)-(35) in the picture.
0 -
Hi Haoxing,
I think there's some typos, but I'd guess the main issue seems to be that the translation of math into code is way off.
It should be something like this:
for (int k = 1; k < instance.vehiclesNum; k++) {
for (int i = 1; i < instance.nodesNum-1; i++) {
double lhs = 0;
for (int j = 0; j < instance.nodesNum-1; j++) {
if (j != i) {
lhs += getNodeRel(X[j][i][k]);
}
}
double rhs = 0;
for (int j = 0; j < instance.nodesNum; j++) {
if (j != i) {
for (int h = 1; h < instance.nodesNum-1; h++) {
if (h != j && h <= i) {
rhs += getNodeRel(X[j][h][k-1]);
}
}
}
}
if (rhs < lhs) {
// construct constraint
}
}
}Note that this code is not tested, any maybe there are some tweaks to be made based off your different indices. I've left the constraint construction as an exercise, but it needs to closely mirror the calculation of lhs and rhs. There is probably an elegant way to combine them both.
Also note that there is no guarantee that Gurobi will use a user-cut. This is the difference between lazy constraints and user cuts. Lazy constraints will always be used by Gurobi since they are needed for validity. User cuts are not needed for validity and Gurobi does not have to add them if it thinks it is a bad idea.
- Riley
0 -
Hi Riley,
Thanks for your reply! I made modifications based on your code. After testing, the code for User Cut is feasible.
Now what makes me confused is:
When I use User Cut or Lazy Constraints alone, runing the model can obtain feasible solutions. But when I use User Cut and Lazy Constraints at the same time, model usually have no solution(in many cases). An example log information for a infeasible model using both User Cut and Lazy Constraints is as follows:
Cutting planes:
User: 1296
Learned: 16
Gomory: 6
Cover: 6
Implied bound: 697
Clique: 46
MIR: 196
StrongCG: 2
Flow cover: 5
GUB cover: 1
Inf proof: 6
Zero half: 113
Network: 1
RLT: 1070
Relax-and-lift: 82
BQP: 1
PSD: 1
Lazy constraints: 24May I ask why this is happening?
0 -
Hi Haoxing,
Let me see if I understand correctly.
You have some constraints which can be used to break symmetry and are not necessary for a correct solution.
When you add all of these as normal constraints you get a feasible solution.
When you set LazyConstraints=1 and add these constraints with cbLazy in a MIPSOL callback you get a feasible solution.
When you set PreCrush=1 and add these constraints with cbCut in a MIPNODE callback you get a feasible solution.
When you set LazyConstraints=1, PreCrush=1 and add the constraints (potentially twice) using both cbLazy and cbCut (??) you get an infeasible model?
Is this correct?
- Riley
0 -
Hi Riley,
There seems to be a slight deviation:
(1)
You have some constraints which can be used to break symmetry and are not necessary for a correct solution.
When you add all of these as normal constraints you get a feasible solution.
I used the "break symmetry" constraints as the User Cut, they are not included in my MIP model.
And when I set PreCrush=1 and add these constraints with cbCut in a MIPNODE callback I can get a feasible solution.
(2)
When you c add these constraints with cbLazy in a MIPSOL callback you get a feasible solution.
I set certain inequalities (except for the "break symmetry" constraints) as Lazy Constraints, such as:
c[i][j][k] <= X[i][j][k]
And when I set LazyConstraints=1 and add these constraints with cbLazy in a MIPSOL callback I can get a feasible solution.
(3)
When I set LazyConstraints=1, PreCrush=1 and add the constraints using both cbLazy and cbCut I get an infeasible model.
This is what I want to express.
Thanks.
0 -
Ok, so it's not that you're adding all constraints as both lazy constraints and cuts, you split your symmetry breaking constraints into two groups, with one group added as lazy constraints, and one group added as cuts?
What happens if you just add them all to your model as normal constraints? Is it infeasible?
0 -
Hi Riley,
I am not split the symmetry breaking constraints into lazy constraints and user cut. Certainly, I just add the constraint (34) as user cut. And it is infeasibe when I just add it to my model as normal constraints.
Secondly, the constraints which added to lazy constraints is hard constraints in my original model, and they are solvable when added as normal constraints.
Thansk.
0 -
Ok I think I understand. Your symmetry breaking constraints are user cuts, and there are some other type of constraints (not the symmetry breaking ones) that you are adding as lazy constraints?
My advice is to add everything as normal constraints, so that you get an infeasible model, then follow our guide How do I determine why my model is infeasible?
- Riley
0 -
Hi Riley,
Yes sir, your understanding is correct.
My advice is to add everything as normal constraints, so that you get an infeasible model, then follow our guide How do I determine why my model is infeasible?
So do you mean that If I add the symmetry breaking constraint in the original model, the model is feasible, then adding it as a user cut the model can also be solved?
0 -
No I think there is a misunderstanding.
You need to obtain an infeasible model so that you can diagnose infeasibility.
And it is infeasibe when I just add it to my model as normal constraints.
You say it is infeasible when you add them as normal constraints, so do this. Then diagnose infeasibility.
- Riley
0 -
But the symmetry breaking constraint is not a necessary constraint in my model, the purpose of adding it is to accelerate the speed of model solving. Do I still need to verify the infeasibility of adding this constraint as normal constraints?
-Haoxing
0
Please sign in to leave a comment.
Comments
24 comments