Do lazy constraints always cut integer solutions?
AnsweredDear all,
I'm currently trying to test some optimality cuts via callbacks as lazy using python. The issue I'm encountering is that the incumbent doesn't update even if the current solution doesn't violate the optimality cut. More in detail, the cut that I'm currently trying to introduce has the structure \(RHS \geq LHS\). While debugging, when I check the first optimality cut added, I get that the current \(RHS\) value is \(190196353.41657972\) and the \(LHS\) is also \(190196353.41657972\), the tolerances, which are set to \(1e-4\). I expect the current incumbent to update, since its value is GRB.INFINITY at this point, but that doesn't happen.
I thought that maybe there were numerical approximation issues so I tried with a useless/trivial lazy constraint \(RHS \geq 0\). Because of the nature of the problem I'm solving this will always be true, this condition does not interfere with the solution space whatsoever, so I expected the incumbent to update, but again, same issue as before.
The base case, without optimality cuts, works fine, it doesn't cut any of the feasible solutions found and correctly updates the incumbent.
I know this could be perceived as counter-intuitive since I'm introducing lazy constraints that don't cut an integer solution at the current node but I'm trying to quantify the effect of adding them in the B&B tree since the info. considered could be (or not) useful for the other nodes while branching.
The following logs are for each one of the cases.
With Optimality cut
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: AMD Ryzen 7 5700G with Radeon Graphics, instruction set [SSE2|AVX|AVX2]
Thread count: 8 physical cores, 16 logical processors, using up to 1 threads
Optimize a model with 35721 rows, 2230 columns and 376344 nonzeros
Model fingerprint: 0xc7e01e64
Variable types: 1200 continuous, 1030 integer (1030 binary)
Coefficient statistics:
Matrix range [1e+00, 6e+04]
Objective range [4e+01, 4e+07]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 7e+04]
Variable types: 1200 continuous, 1030 integer (1030 binary)
Root relaxation: objective 1.777070e+08, 1885 iterations, 0.27 seconds (1.11 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1.7771e+08 0 - - 1.7771e+08 - - 1s
0 0 1.8719e+08 0 161 - 1.8719e+08 - - 1s
[DEMAND] Sufficient fract. Demand cut added on node 0.0
[BENDERS] B.O. cut added at node 0.0
LHS: 190196353.41657972
RHS: 190196353.41657972
0 0 1.8808e+08 0 113 - 1.8808e+08 - - 2s
[BENDERS] B.O. cut added at node 0.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 0.0
LHS: 190196353.41657972
RHS: 190196353.41657972
0 2 1.8809e+08 0 113 - 1.8809e+08 - - 3s
[BENDERS] B.O. cut added at node 1.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 2.0
LHS: 190196353.41657972
RHS: 190196353.41657972
2 4 1.8997e+08 1 31 - 1.8873e+08 - 276 5s
[BENDERS] B.O. cut added at node 3.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 4.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 5.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 6.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 7.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 8.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 9.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 10.0
LHS: 190196353.41657972
RHS: 190196353.41657972
10 12 1.8976e+08 8 23 - 1.8940e+08 - 197 10s
[BENDERS] B.O. cut added at node 11.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 12.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 13.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 14.0
LHS: 190196353.41657972
RHS: 190196353.41657972
14 16 2.0001e+08 4 56 - 1.8961e+08 - 180 16s
[BENDERS] B.O. cut added at node 15.0
LHS: 190196353.41657972
RHS: 190196353.41657972
15 17 1.9090e+08 2 81 - 1.8998e+08 - 183 21s
[BENDERS] B.O. cut added at node 16.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 17.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 18.0
LHS: 190196353.41657972
RHS: 190196353.41657972
18 20 1.9137e+08 5 25 - 1.8998e+08 - 160 25s
[BENDERS] B.O. cut added at node 19.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 20.0
LHS: 190196353.41657972
RHS: 190196353.41657972
20 22 2.1929e+08 2 35 - 1.9020e+08 - 168 30s
[BENDERS] B.O. cut added at node 21.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 22.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 23.0
LHS: 190196353.41657972
RHS: 190196353.41657972
[BENDERS] B.O. cut added at node 24.0
LHS: 190196353.4164797
RHS: 190196353.45987976
* 24 0 12 1.901964e+08 1.9020e+08 0.00% 155 38s
Cutting planes:
User: 2
Lazy constraints: 54
Explored 25 nodes (6543 simplex iterations) in 38.42 seconds (17.34 work units)
Thread count was 1 (of 16 available processors)
Solution count 1: 1.90196e+08
Optimal solution found (tolerance 1.00e-04)
Best objective 1.901963534165e+08, best bound 1.901963534165e+08, gap 0.0000%
User-callback calls 557, time in user-callback 33.65 sec
With trivial cut
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: AMD Ryzen 7 5700G with Radeon Graphics, instruction set [SSE2|AVX|AVX2]
Thread count: 8 physical cores, 16 logical processors, using up to 1 threads
Optimize a model with 35721 rows, 2230 columns and 376344 nonzeros
Model fingerprint: 0xc7e01e64
Variable types: 1200 continuous, 1030 integer (1030 binary)
Coefficient statistics:
Matrix range [1e+00, 6e+04]
Objective range [4e+01, 4e+07]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 7e+04]
Variable types: 1200 continuous, 1030 integer (1030 binary)
Root relaxation: objective 1.777070e+08, 1885 iterations, 0.27 seconds (1.11 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1.7771e+08 0 - - 1.7771e+08 - - 1s
0 0 1.8719e+08 0 161 - 1.8719e+08 - - 1s
[DEMAND] Sufficient fract. Demand cut added on node 0.0
[BENDERS] Trivial cut added at node 0.0
0 0 1.8808e+08 0 113 - 1.8808e+08 - - 2s
[BENDERS] Trivial cut added at node 0.0
[BENDERS] Trivial cut added at node 0.0
0 2 1.8809e+08 0 113 - 1.8809e+08 - - 3s
[BENDERS] Trivial cut added at node 1.0
[BENDERS] Trivial cut added at node 2.0
[BENDERS] Trivial cut added at node 3.0
3 5 1.9077e+08 2 115 - 1.8911e+08 - 264 6s
[BENDERS] Trivial cut added at node 4.0
[BENDERS] Trivial cut added at node 5.0
5 7 1.9110e+08 2 115 - 1.8998e+08 - 290 11s
[BENDERS] Trivial cut added at node 6.0
[BENDERS] Trivial cut added at node 7.0
[BENDERS] Trivial cut added at node 8.0
[BENDERS] Trivial cut added at node 9.0
[BENDERS] Trivial cut added at node 10.0
10 12 2.1916e+08 2 29 - 1.9019e+08 - 294 17s
[BENDERS] Trivial cut added at node 11.0
[BENDERS] Trivial cut added at node 12.0
[BENDERS] Trivial cut added at node 13.0
13 15 2.2786e+08 5 27 - 1.9019e+08 - 261 22s
[BENDERS] Trivial cut added at node 14.0
14 16 1.9020e+08 2 68 - 1.9020e+08 - 255 30s
[BENDERS] Trivial cut added at node 15.0
* 15 1 3 1.901964e+08 1.9020e+08 0.00% 240 31s
Cutting planes:
User: 2
Lazy constraints: 47
Explored 16 nodes (6420 simplex iterations) in 31.25 seconds (15.63 work units)
Thread count was 1 (of 16 available processors)
Solution count 1: 1.90196e+08
Optimal solution found (tolerance 1.00e-04)
Best objective 1.901963533732e+08, best bound 1.901963533732e+08, gap 0.0000%
User-callback calls 481, time in user-callback 26.97 sec
Without optimality cut
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: AMD Ryzen 7 5700G with Radeon Graphics, instruction set [SSE2|AVX|AVX2]
Thread count: 8 physical cores, 16 logical processors, using up to 1 threads
Optimize a model with 35721 rows, 2230 columns and 376344 nonzeros
Model fingerprint: 0xc7e01e64
Variable types: 1200 continuous, 1030 integer (1030 binary)
Coefficient statistics:
Matrix range [1e+00, 6e+04]
Objective range [4e+01, 4e+07]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 7e+04]
Variable types: 1200 continuous, 1030 integer (1030 binary)
Root relaxation: objective 1.777070e+08, 1885 iterations, 0.27 seconds (1.11 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 1.7771e+08 0 - - 1.7771e+08 - - 1s
0 0 1.8719e+08 0 161 - 1.8719e+08 - - 1s
[DEMAND] Sufficient fract. Demand cut added on node 0.0
H 0 0 1.901964e+08 1.8808e+08 1.11% - 2s
0 0 1.8808e+08 0 113 1.9020e+08 1.8808e+08 1.11% - 2s
0 2 1.8809e+08 0 113 1.9020e+08 1.8809e+08 1.11% - 3s
* 4 0 2 1.901964e+08 1.9020e+08 0.00% 33.8 9s
Cutting planes:
User: 2
Lazy constraints: 11
Explored 5 nodes (2950 simplex iterations) in 9.21 seconds (4.60 work units)
Thread count was 1 (of 16 available processors)
Solution count 1: 1.90196e+08
Optimal solution found (tolerance 1.00e-04)
Best objective 1.901963533732e+08, best bound 1.901963533732e+08, gap 0.0000%
User-callback calls 243, time in user-callback 7.36 sec
I also tried to reduce the magnitude of the coefficients, but I get the same result. I'm not using a classical benders decomposition either so it is not possible to apply the classic algorithm of having the MP and solving the SPs while iteratively adding the optimality/feasibility cuts and re-optimizing until convergence.
Is this an expected behavior of adding lazy constraints? Since in the manual it states that
You would typically add a lazy constraint by first querying the current node solution (...) to add a constraint that cuts off the solution.
Appreciate any insights, suggestions or comments.
Best regards,
Nicolas Zerega
-
I'm still wondering about this. As of now I've been able to keep the updated incumbent outside gurobi and then do the analysis with it. But would like to check why it is being cut and not accepted inside the solver and, also, why is it cut when adding the trivial lazy constraint.
I will check with other cut types and see if it does the sameBest regards,
Nicolas Zerega
0 -
-
-
Gurobi Staff
Hi Nicolas,
I am still trying to understand your case. If the incumbent does not violate the added lazy constraint, the solution should be accepted, and the incumbent value should update.
What I am wondering is that the numbers of added user cuts and lazy constraints shown by the solver at the end do not correspond to your output lines. Are you probably adding other cuts that cut off the incumbent?Best regards,
Mario0 -
-
Dear Mario,
I have a very similar problem with the lazy constraints, if I understand the previous question correctly.
I can give you a very simple example.
I have the problem
min x + y + z
and add then the constraints x >= 1, y>=1, z=>1 lazily, where x,y,z binary.
So, my callback is active for "where == GRB.Callback.MIPSOL" (C#.NET API). The problem that i experience is that gurobi is invoking my callback multiple times for the solution (0,0,0) and therefore i have to add the lazy constraint x >= 1 multiple times (like 5 times). I would have expected that i have to add that constraint only once and then (0,0,0) is cutoff and i get a new feasible solution (1,0,0) from Gurobi. Consequently, the incumbent does not change as the Nicolas above describes. Is there something buggy or is that just a wrong assumption from my side that the constraints - once added - are valid for the rest of the solving process?
Reproducible under C#.net API with a Gurobi 11.0.0 ComputeServer.
0 -
-
Update: Playing a bit around with this it seems that the added constraints from the first four callback calls are just ignored (for whatever reason). So as a workaround I can add 0 = 1 four times and then it works as expected.
0 -
-
-
Hi Matthias,
The behavior you experience is probably due to parallel solves, which Tobias describes in more detail in this comment.
Best regards,
Marika0 -
-
-
Hi Matthias,
Since the solver is using multiple threads by default, it can happen that different heuristics or other components (in different threads) find the same solution. In this case, it is not surprising since the solution (0,0,0) is trivial. If you add lazy cuts, those cuts must be evaluated and propagated to the other threads. This happens only at specific synchronization points. Duplicate cuts will be discarded, then.
So, in practice, you may see the same solution in the MIPSOL callback more than once. You should consider those callbacks independently, i.e., add cuts to cut off an infeasible solution independently of what you already did in previous callbacks. Adding infeasible cuts like 0=1 can lead to problems, maybe not in this toy example, but in more complex ones.
0 -
-
Thanks. Marika Karbstein & Mario Ruthmair.
0 -
Please sign in to leave a comment.
Comments
7 comments