Ignored lazy constraint leads to wrong solution cont.
Ongoing
Hi,
I'm working in the same research group as Felix Tamke. We have described the following behavior already in the thread:
https://support.gurobi.com/hc/en-us/community/posts/360078071312
In rare cases, lazy constraints are ignored in Gurobi 9.1.2, and thus, infeasible results are incorrectly returned as feasible and optimal.
We have repeated the tests, and the same issue occurs under Gurobi 12.0.1.
First, some preliminary remarks:
We solve a CVRP problem using rounded capacity cuts (RCC). We add RCC as user cut (addCut()) in the callback if where == MIPNODE and we add RCC as lazy constraint (addLazy()) in the callback if where == MIPSOL
In most cases, the results are correct, i.e., in about 1499 out of 1500 runs. However, an infeasible solution is sometimes considered feasible even though we add a lazy constraint. Consider the log file below.
Gurobi Optimizer version 12.0.1 build v12.0.1rc0 (win64 - Windows Server 2022.0 (20348.2))
CPU model: AMD EPYC 7513 32-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 18 physical cores, 18 logical processors, using up to 4 threads
Non-default parameters:
SolutionLimit 10000
TimeLimit 28800
PreCrush 1
Seed 1179
Threads 4
LazyConstraints 1
Optimize a model with 137 rows, 256 columns and 720 nonzeros
Model fingerprint: 0xa6423194
Variable types: 0 continuous, 256 integer (256 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [8e+00, 6e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 5e+00]
User MIP start produced solution with objective 350.582 (0.01s)
Loaded user MIP start with objective 350.582
Presolve removed 2 rows and 18 columns
Presolve time: 0.00s
Presolved: 135 rows, 238 columns, 669 nonzeros
Variable types: 0 continuous, 238 integer (238 binary)
Root relaxation: objective 2.862678e+02, 57 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 286.26777 0 - 350.58163 286.26777 18.3% - 0s
0 0 294.19409 0 - 350.58163 294.19409 16.1% - 0s
0 0 295.17078 0 24 350.58163 295.17078 15.8% - 0s
0 0 303.18858 0 8 350.58163 303.18858 13.5% - 0s
0 0 310.99557 0 - 350.58163 310.99557 11.3% - 0s
0 0 311.91721 0 22 350.58163 311.91721 11.0% - 0s
0 0 314.76788 0 - 350.58163 314.76788 10.2% - 0s
0 0 314.88098 0 - 350.58163 314.88098 10.2% - 0s
0 0 317.45721 0 18 350.58163 317.45721 9.45% - 0s
0 0 318.88968 0 - 350.58163 318.88968 9.04% - 0s
0 0 320.33135 0 33 350.58163 320.33135 8.63% - 0s
0 0 321.71242 0 10 350.58163 321.71242 8.23% - 0s
H 0 0 336.5181131 321.71242 4.40% - 0s
0 0 321.71242 0 10 336.51811 321.71242 4.40% - 0s
0 0 321.71242 0 27 336.51811 321.71242 4.40% - 0s
0 0 323.63495 0 18 336.51811 323.63495 3.83% - 0s
0 0 323.67607 0 - 336.51811 323.67607 3.82% - 0s
0 0 323.81376 0 43 336.51811 323.81376 3.78% - 0s
0 0 324.40327 0 - 336.51811 324.40327 3.60% - 0s
0 0 324.70738 0 22 336.51811 324.70738 3.51% - 0s
0 0 324.89283 0 20 336.51811 324.89283 3.45% - 0s
0 0 325.33311 0 45 336.51811 325.33311 3.32% - 0s
0 0 325.35097 0 45 336.51811 325.35097 3.32% - 0s
0 0 325.52726 0 35 336.51811 325.52726 3.27% - 0s
0 0 325.88700 0 41 336.51811 325.88700 3.16% - 0s
0 0 326.36273 0 32 336.51811 326.36273 3.02% - 0s
0 0 326.36273 0 24 336.51811 326.36273 3.02% - 0s
0 2 326.38113 0 22 336.51811 326.38113 3.01% - 0s
H 36 19 334.9638862 329.73380 1.56% 12.9 0s
H 42 19 318.1590092 318.15901 0.00% 11.4 0s
Cutting planes:
User: 49
Gomory: 7
Clique: 2
Zero half: 1
Lazy constraints: 10
Explored 46 nodes (1062 simplex iterations) in 0.43 seconds (0.08 work units)
Thread count was 4 (of 18 available processors)
Solution count 4: 318.159 334.964 336.518 350.582
Optimal solution found (tolerance 1.00e-04)
Best objective 3.181590091987e+02, best bound 3.181590091987e+02, gap 0.0000%
User-callback calls 487, time in user-callback 0.24 sec
The most important lines are at the end:
H 36 19 334.9638862 329.73380 1.56% 12.9 0s
H 42 19 318.1590092 318.15901 0.00% 11.4 0s
In the vast majority of all runs, the optimal result is 334.96. We can, therefore, conclude that this is the true optimal result. The infeasible solution with an objective value of 318.159 contains a route 12 - 5 - 2 - 3 - 1. However, we have added a lazy constraint with exactly these nodes to eliminate this route in the MIPSOL callback.
We were informed then that the issue Mario Ruthmair communicated could be reproduced and forwarded to the development team. Is this issue still being worked on?
Best regards, and thanks for the great work and support!
Florian
-
Hi Florian,
Thanks for bringing it to our attention. I can confirm the issue is still open, but looks like it has gone stale. It looks like it was a hotly debated issue at the time. I have updated the dev team with this post, and I'll pass on any comments they have.
- Riley
0 -
Hi Florian,
You mentioned that you add the RCCs in the MIPNODE callback with addCut(). What happens if you add them in MIPNODE with addLazy()? Can you still reproduce the issue?
This was my workaround back then, i.e., to add all cuts with addLazy() if they potentially cut off integer solutions, regardless of whether I was in a MIPSOL or MIPNODE callback.Best regards,
Mario0 -
Hi all,
Thanks for the quick reply. I can confirm that the issue does not occur when I only add the RCCs as lazy constraints. Thanks for the workaround!
To evaluate the issue, we only have RCCs enabled. Besides RCCs, we are adding more CVRP cuts with AddCut() in our codebase. Can the problem of the ignored lazy constraint occur as soon as any cut, which could potentially also cut off an integer solution, is added with AddCut()?
Or does the issue only occur because the RCCs, in particular, were added with both AddCut() and AddLazy()?Do you have any idea what could be causing the incorrect behavior?
Best regards, and thanks for the support!
Florian0 -
Hi Florian,
Yes, since many CVRP cut families cut off integer solutions, too, I would strongly recommend adding all your cuts with addLazy(). There is no downside to this; in fact, you might even benefit from it since lazy constraints are accepted by the solver more often. Cuts added with addCut() might be ignored for several reasons (numerics, etc.).
There is an internal discussion about what is happening in these cases and whether this is expected or not (since user-cuts must not cut off integer solutions), but it is not fully clear yet.
Best,
Mario0
Please sign in to leave a comment.
Comments
4 comments