Ignored lazy constraint leads to wrong solution
進行中
Hi,
I am working on a branch-and-cut algorithm in C++ using both lazy constraints and user cuts. For one particular model, an incumbent solution is accepted although a violated lazy constraint is added before. This leads to an optimal solution which is in fact infeasible for the problem under consideration.
In order to make this situation reproducible, I exported the initial model (MPS), the used mip start (MST), the parameters (PRM), and the lazy constraints and user cuts with the information in which callback they are added (own file format), and wrote a simple C++ program, reading all files and simulating the branch-and-cut. The files can be downloaded here: https://mario.ruthmair.at/wp-content/uploads/2021/05/lazy-cuts.zip
The log below shows what happens: In callback call 21 a lazy constraint is added to reject the incumbent with value 828.0, but the solution is still accepted and identified as an optimal solution. The total number of added lazy constraints reported by Gurobi (14) is one less than the actual number of added lazy constraints (15).
In the end, all added lazy constraints are again verified and it turns out that the last one (added in call 21) is still violated. Any idea what is going on here?
Minor side comment: Many user cuts are ignored by Gurobi. I know that Gurobi heuristically decides which user cuts to keep based on dual bound improvements, violation, numerics, etc. Still it would be nice to have a switch to get more user cuts accepted, e.g., by setting parameter Cuts to "aggressive" (or by introducing a dedicated UserCuts parameter?).
I would be thankful for any hint or suggestion!
Best regards, Mario
Read MPS format model from file model.mps
Reading time = 0.01 seconds
(null): 169 rows, 594 columns, 9082 nonzeros
Set parameter PreCrush to value 1
Set parameter Threads to value 1
Set parameter LazyConstraints to value 1
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (linux64)
Thread count: 4 physical cores, 8 logical processors, using up to 1 threads
Optimize a model with 169 rows, 594 columns and 9082 nonzeros
Model fingerprint: 0x68ba66f5
Variable types: 0 continuous, 594 integer (0 binary)
Coefficient statistics:
Matrix range [1e-01, 2e+00]
Objective range [4e+00, 4e+01]
Bounds range [1e+00, 2e+01]
RHS range [1e+00, 3e+01]
Callback 1 MIPSOL: add 0 lazy constraints
Loaded user MIP start with objective 836
Presolve removed 44 rows and 34 columns
Presolve time: 0.01s
Presolved: 125 rows, 560 columns, 4945 nonzeros
Variable types: 0 continuous, 560 integer (496 binary)
Root relaxation: objective 8.000000e+02, 90 iterations, 0.00 seconds
Callback 2 MIPSOL: add 1 lazy constraints
Callback 3 MIPSOL: add 1 lazy constraints
Callback 4 MIPSOL: add 1 lazy constraints
Callback 5 MIPSOL: add 1 lazy constraints
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 801.33333 0 41 836.00000 801.33333 4.15% - 0s
Callback 6 MIPSOL: add 1 lazy constraints
Callback 7 MIPNODE: add 66 user cuts
Callback 8 MIPSOL: add 1 lazy constraints
Callback 9 MIPSOL: add 1 lazy constraints
Callback 10 MIPSOL: add 1 lazy constraints
Callback 11 MIPSOL: add 1 lazy constraints
0 0 814.00000 0 41 836.00000 814.00000 2.63% - 0s
Callback 12 MIPSOL: add 1 lazy constraints
Callback 13 MIPNODE: add 4 user cuts
0 0 814.00000 0 24 836.00000 814.00000 2.63% - 0s
Callback 14 MIPNODE: add 8 user cuts
Callback 15 MIPSOL: add 1 lazy constraints
Callback 16 MIPSOL: add 1 lazy constraints
0 0 828.00000 0 12 836.00000 828.00000 0.96% - 0s
Callback 17 MIPNODE: add 8 user cuts
Callback 18 MIPSOL: add 1 lazy constraints
Callback 19 MIPSOL: add 1 lazy constraints
0 0 828.00000 0 40 836.00000 828.00000 0.96% - 0s
Callback 20 MIPNODE: add 34 user cuts
Callback 21 MIPSOL: add 1 lazy constraints
H 0 0 828.0000000 828.00000 0.00% - 0s
0 0 828.00000 0 40 828.00000 828.00000 0.00% - 0s
Cutting planes:
User: 18
Lazy constraints: 14
Explored 1 nodes (375 simplex iterations) in 0.06 seconds
Thread count was 1 (of 8 available processors)
Solution count 2: 828 836
Optimal solution found (tolerance 1.00e-04)
Best objective 8.280000000000e+02, best bound 8.280000000000e+02, gap 0.0000%
User-callback calls 125, time in user-callback 0.00 sec
Check if final solution violates some added lazy constraints:
Lazy constraint added in callback 21 is still violated: -3 < -5
-
Hi Mario,
Are you able to reproduce the problem when you add all lazy constraints to the LP file as described in LP format?
This would make it easier to solve the problem, write the final solution via ResultFile and then check by hand or programmatically which lazy constraint is violated. I understand that you implemented the C++ function for this, however, it is rather hard to understand what the violated lazy constraint actually looks like.
Best regards,
Jaromił1 -
Hi Jaromił,
if I add all lazy constraints a priori to the model with lazy attribute 1, then all lazy constraints are correctly satisfied and the solution is different (I added the LP file including the lazy constraints and the SOL file resulting from the problematic run to the ZIP archive linked in my initial post).
But this is not surprising to me, I call it the MIP butterfly effect ;), small changes to the solution process can have huge consequences. In fact, if I remove the MIP start or add only a subset of the user cuts, the problem does not occur.I also believe that the lazy constraint itself is not problematic, it only includes a few variables with coefficients 1 and -1, and an integer RHS. The final violation in the problematic run is significant, the left-hand side values to -3, see below the full lazy constraint.
lazy21: x(17,19) + x(17,21) + x(17,23) + x(17,27) + x(17,29) + x(17,31)
+ x(19,21) + x(19,23) + x(19,27) + x(19,29) + x(19,31) + x(21,23)
+ x(21,27) + x(21,29) + x(21,31) + x(23,27) + x(23,29) + x(23,31)
+ x(27,29) + x(27,31) + x(29,31) - z(17) - z(19) - z(21) - z(23) - z(27)
- z(29) - z(31) <= -5I know that this is a nasty situation but I would really like to see where the problem comes from. Anyway, thanks for your time!
Best regards,
Mario1 -
How did you generate the user cuts? From the GRBCallback::addCut() documentation:
Note that cutting planes [...] can cut off continuous solutions, but they may not cut off integer solutions that respect the original constraints of the model. Ignoring this restriction will lead to incorrect solutions.
It seems to me that your user cuts cut off integer-feasible solutions. For example, there exists a feasible solution to the model (including the 15 lazy constraints but without the 120 user cuts) satisfying:
$$\begin{align*} x_{17,18} &= 1 \\ z_{17} &= 1 \\ z_{18} &= 1.\end{align*}$$
You can test this by solving your model with the above constraints added. Gurobi should find a feasible solution. However, your 28th user cut (line 33 of \( \texttt{cuts.txt} \)) cuts off this integer-feasible solution:
$$\begin{align*} x_{17,18} - z_{17} - z_{18} &\leq -2.\end{align*}$$
Because the user cuts cut off integer-feasible solutions, Gurobi may return an incorrect solution.
1 -
Hi Eli,
this is indeed a very interesting point! The problem I want to solve is a capacitated routing problem. Capacity cuts (the cut you are mentioning above is one of them) are used both as lazy constraints to ensure capacity restrictions and as user cuts to improve the dual bounds. So if in a MIPNODE callback I want to add a cut violated by the current fractional solution to improve dual bounds, I should use addLazy() instead of addCut() if the type of cut can potentially also be a lazy constraint? (This would be a different behavior as for example in CPLEX.) So far, I added all cuts in a MIPSOL callback with addLazy() and all cuts in a MIPNODE callback with addCut().
In the situation above, the same cut would have been generated as a lazy constraint if Gurobi would bring up the integer solution you are mentioning but clearly in my reduced branch-and-cut simulator the separation routines are not included to identify it, so the solution is accepted. In my original code, switching from addCut() to addLazy() indeed solved this issue!
Still, it would be interesting to know how this can lead to a lazy constraint not being considered? Could you provide any additional information to get a deeper understanding of what's going on?
Thanks a lot for your effort!
Best regards,
Mario1 -
Still, it would be interesting to know how this can lead to a lazy constraint not being considered? Could you provide any additional information to get a deeper understanding of what's going on?
Your callback should be written to generate lazy constraints to cut off MIPSOL solutions that violate your capacity constraints, even if you have previously added the same lazy constraints. That is, in every MIPSOL callback, the new solution should be examined with GRBCallback::getSolution() and (if applicable) invalidated by adding a lazy constraint that cuts it off.
After looking at your code a bit closer, I suspect this is the real reason certain lazy constraints were violated by the final solution. It looks like your code predefines which lazy constraints are added in each callback. Does your original code do this too? This approach does not result in a valid algorithm - lazy constraints should be separated based on the specific solution Gurobi presents to the user in the MIPSOL callback. Additionally, it can happen that a solution found by Gurobi violates a previously added lazy constraint, in which case another lazy constraint (possibly one previously added) must be separated.
So, invalid user cuts were not causing lazy constraints to be violated. But it was still useful to discuss user cuts.
So if in a MIPNODE callback I want to add a cut violated by the current fractional solution to improve dual bounds, I should use addLazy() instead of addCut() if the type of cut can potentially also be a lazy constraint?
Yes, I would use a lazy constraint instead of a user cut in this situation. And be prepared to re-add that lazy constraint if Gurobi finds an otherwise integer-feasible solution that violates it (even though the same lazy constraint was previously added).
2 -
Hi Eli,
Your callback should be written to generate lazy constraints to cut off MIPSOL solutions that violate your capacity constraints, even if you have previously added the same lazy constraints. That is, in every MIPSOL callback, the new solution should be examined with GRBCallback::getSolution() and (if applicable) invalidated by adding a lazy constraint that cuts it off
Yes, this is exactly what I did in my original code.
Note that the code I uploaded in this thread is only kind of a "branch-and-cut simulator", my original code involves several separation methods requiring additional libraries etc. So, what I did was to remember the lazy and user cuts added in each iteration in my original code (generated by the separation methods), export them, and rebuild the same procedure (without separation) here in the simulator, just to reduce the code to a minimum. This works as long as nothing (absolutely nothing) is changed, different parameters or cut sequences invalidate the simulation immediately. I know this is not a satisfying B&C simulator, since one cannot play around with it.
In my original code, I always separate from scratch for every new callback solution (integer or fractional), without using information from past iterations, so I would generate the same cuts repeatedly if they are violated.
Yes, I would use a lazy constraint instead of a user cut in this situation. And be prepared to re-add that lazy constraint if Gurobi finds an otherwise integer-feasible solution that violates it (even though the same lazy constraint was previously added).
Yes, always using addCut() in a MIPNODE callback was basically the main misunderstanding on my side since in CPLEX this is different. But the Gurobi interpretation clearly makes sense.
Still, I am confused about the consequences of this misuse that lead to adding a lazy constraint in a MIPSOL callback that is finally violated in the accepted solution. But to clarify this issue we would need to dig much deeper into my case which is difficult here in this forum.
Currently, I am happy that I found the mistake with your help, so thanks again for your (meanwhile enormous) effort! (Don't tell Sonja ;))
All the best, Mario1 -
Hi all,
we are currently also working on some kind of capacitated routing problem like Mario and add capacity cuts for fractional and integer solutions. Like Mario, we always separate from scratch for every new solution (MIPNODE and MIPSOL). We have done some tests with multiple runs per instance with either addCut() or andLazy() and the optimal solutions were always the same. However, that could just be luck and it is not clear to us whether the use of addCut() is valid or not when the added cut can also be a lazy constraint. Eli, you state
Yes, I would use a lazy constraint instead of a user cut in this situation.
Is this a general recommendation because the algorithm would not be valid or are there other factors? If it is not valid, why? Like Mario, I'm a little confused about this.
We have observed in our tests that adding a user cut instead of lazy constraint leads to better dual bounds at the root node, since far more cuts are added than constraints. I can only assume that Gurobi can derive additional cuts from the added user cuts, but not from the lazy constraints? As we are not sure if using addCut() is valid or not, we currently add a violated capacity cut at the root node as user cut and as lazy constraints. Surprisingly, this works. Are there any drawbacks to doing this?
Best regards and thanks for the great work and support!
Felix
1 -
User cuts, like Gurobi's own internal cuts, are placed in an internal cut pool. Here, Gurobi filters the cuts based on criteria like cut violation and orthogonality to other cuts. Cuts that make it through the filtering process are added to the LP relaxation.
In contrast, lazy constraints are always added directly to the LP relaxation.
We have observed in our tests that adding a user cut instead of lazy constraint leads to better dual bounds at the root node, since far more cuts are added than constraints. I can only assume that Gurobi can derive additional cuts from the added user cuts, but not from the lazy constraints?
Once a user cut makes it to the LP relaxation, there shouldn't be a big difference in how Gurobi leverages the user cut for additional cut generation/strengthening compared to an identical lazy constraint.
Are you saying that adding a large number of user cuts improves the dual bound more than adding a much smaller number of lazy constraints? If so, this doesn't seem strange. If many of the user cuts survive the cut filtering process and make it into the LP relaxation, the dual bound can be stronger than the bound obtained by adding a much smaller number of lazy constraints directly to the LP relaxation.
As we are not sure if using addCut() is valid or not, we currently add a violated capacity cut at the root node as user cut and as lazy constraints. Surprisingly, this works. Are there any drawbacks to doing this?
Lazy constraints are added directly to the LP relaxation, but user cuts must survive Gurobi's cut filtering process to make it to the LP relaxation. Since you add the capacity cut as a lazy constraint, the identical user cut is effectively useless.
One possible drawback of adding all of your capacity cuts as lazy constraints is that you bypass Gurobi's internal cut filtering. As a result, you risk adding weak, near-parallel, and/or simply too many cuts to the LP relaxation, all of which can negatively affect performance.
Eli, you state
Yes, I would use a lazy constraint instead of a user cut in this situation.
Is this a general recommendation because the algorithm would not be valid or are there other factors? If it is not valid, why?
If you are unsure whether your capacity cut cuts off any integer-feasible solutions, it is valid to add the cut at the root node as either a lazy constraint or a user cut, assuming you:
- Set LazyConstraints=1 to disable dual presolve reductions that rely on having a complete description of the model's feasible set, and
- Still use lazy constraints in a \( \texttt{MIPSOL} \) callback to cut off any otherwise integer-feasible solutions (even if it means later separating the exact same capacity cut as a lazy constraint).
Both of these are necessary anyways for the correctness of an algorithm employing lazy constraints.
I like the idea of adding such capacity cuts as lazy constraints from the perspective that they may cut off integer-feasible solutions. However, like I mentioned, the orthogonality, strength, and quantity of the capacity cuts may impact Gurobi's performance. So, a more conservative approach would be to add such capacity cuts as user cuts to take advantage of Gurobi's internal cut filtering, then separate lazy constraints as necessary when Gurobi presents you with new incumbent solutions.
1 -
Hi Eli,
thank you very much for the quick and comprehensive answer.
If you are unsure whether your capacity cut cuts off any integer-feasible solutions, it is valid to add the cut at the root node as either a lazy constraint or a user cut, assuming you:
- Set LazyConstraints=1 to disable dual presolve reductions that rely on having a complete description of the model's feasible set, and
- Still use lazy constraints in a
callback to cut off any otherwise integer-feasible solutions (even if it means later separating the exact same capacity cut as a lazy constraint).
Both of these are necessary anyways for the correctness of an algorithm employing lazy constraints.
As I said, we check every new incumbent integer solution and add violated constraints as lazy constraints in the callback. So I guess our algorithm works correctly regardless of whether we add the capacity cuts as user cuts or lazy constraints in the callback. Still, I wonder why a lazy contraint in Mario's approach was ignored. But of course you can't answer that without knowing their algorithm.
Are you saying that adding a large number of user cuts improves the dual bound more than adding a much smaller number of lazy constraints? If so, this doesn't seem strange. If many of the user cuts survive the cut filtering process and make it into the LP relaxation, the dual bound can be stronger than the bound obtained by adding a much smaller number of lazy constraints directly to the LP relaxation.
See the two logs below. In the first one, we add violated capacity cuts as lazy constraints and in the second log, we add them as user cuts. Besides that, everything is the same. Of course, there are slight differences between runs with different seeds, but the behavior of the algorithm is pretty much the same.
RCC added with addLazy() at the root node in callback
Gurobi 9.1.0 (win64, C++) logging started Wed Jun 23 10:51:48 2021
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 32 physical cores, 32 logical processors, using up to 8 threads
Optimize a model with 864 rows, 1681 columns and 5000 nonzeros
Model fingerprint: 0x25402c11
Variable types: 0 continuous, 1681 integer (1681 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [4e+00, 7e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+01]
Warning: Completing partial solution with 1543 unfixed non-continuous variables out of 1681
User MIP start produced solution with objective 1210.97 (0.01s)
Loaded user MIP start with objective 1210.97
Presolve removed 24 rows and 84 columns
Presolve time: 0.01s
Presolved: 840 rows, 1597 columns, 4710 nonzeros
Variable types: 0 continuous, 1597 integer (1597 binary)
Root relaxation: objective 6.350581e+02, 115 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 656.63003 0 22 1210.96756 656.63003 45.8% - 0s
Warning: Completing partial solution with 1543 unfixed non-continuous variables out of 1681
0 0 690.73459 0 20 1210.96756 690.73459 43.0% - 0s
0 0 723.59620 0 59 1210.96756 723.59620 40.2% - 0s
0 0 726.44653 0 40 1210.96756 726.44653 40.0% - 0s
0 0 731.38448 0 63 1210.96756 731.38448 39.6% - 0s
H 0 0 976.3104617 731.38448 25.1% - 0s
0 0 731.38448 0 48 976.31046 731.38448 25.1% - 0s
0 2 731.38448 0 48 976.31046 731.38448 25.1% - 0s
Cutting planes:
User: 11
Lazy constraints: 76
Explored 1 nodes (745 simplex iterations) in 0.36 seconds
Thread count was 8 (of 32 available processors)RCC added with addCut() at the root node in callback
Gurobi 9.1.0 (win64, C++) logging started Wed Jun 23 10:48:08 2021
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 32 physical cores, 32 logical processors, using up to 8 threads
Optimize a model with 864 rows, 1681 columns and 5000 nonzeros
Model fingerprint: 0x25402c11
Variable types: 0 continuous, 1681 integer (1681 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [4e+00, 7e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+01]
Warning: Completing partial solution with 1543 unfixed non-continuous variables out of 1681
User MIP start produced solution with objective 1210.97 (0.01s)
Loaded user MIP start with objective 1210.97
Presolve removed 24 rows and 84 columns
Presolve time: 0.01s
Presolved: 840 rows, 1597 columns, 4710 nonzeros
Variable types: 0 continuous, 1597 integer (1597 binary)
Root relaxation: objective 6.350581e+02, 115 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 656.63003 0 22 1210.96756 656.63003 45.8% - 0s
Warning: Completing partial solution with 1543 unfixed non-continuous variables out of 1681
0 0 690.73459 0 20 1210.96756 690.73459 43.0% - 0s
0 0 714.75147 0 22 1210.96756 714.75147 41.0% - 0s
0 0 726.90391 0 56 1210.96756 726.90391 40.0% - 0s
0 0 742.25879 0 72 1210.96756 742.25879 38.7% - 0s
0 0 754.21210 0 66 1210.96756 754.21210 37.7% - 0s
0 0 757.51434 0 96 1210.96756 757.51434 37.4% - 0s
0 0 760.38108 0 96 1210.96756 760.38108 37.2% - 0s
0 0 762.77759 0 106 1210.96756 762.77759 37.0% - 0s
0 0 763.60792 0 101 1210.96756 763.60792 36.9% - 0s
0 0 766.02305 0 106 1210.96756 766.02305 36.7% - 0s
0 0 769.27280 0 101 1210.96756 769.27280 36.5% - 0s
0 0 772.19216 0 121 1210.96756 772.19216 36.2% - 0s
0 0 774.91413 0 115 1210.96756 774.91413 36.0% - 0s
0 0 776.76944 0 115 1210.96756 776.76944 35.9% - 0s
0 0 782.95271 0 112 1210.96756 782.95271 35.3% - 0s
0 0 786.48278 0 118 1210.96756 786.48278 35.1% - 0s
0 0 787.68155 0 120 1210.96756 787.68155 35.0% - 0s
0 0 788.57955 0 128 1210.96756 788.57955 34.9% - 0s
0 0 790.29200 0 129 1210.96756 790.29200 34.7% - 0s
0 0 792.46492 0 126 1210.96756 792.46492 34.6% - 0s
0 0 793.57640 0 129 1210.96756 793.57640 34.5% - 0s
0 0 795.11731 0 130 1210.96756 795.11731 34.3% - 0s
0 0 797.92585 0 125 1210.96756 797.92585 34.1% - 1s
0 0 799.52665 0 131 1210.96756 799.52665 34.0% - 1s
0 0 799.95084 0 138 1210.96756 799.95084 33.9% - 1s
0 0 800.78791 0 123 1210.96756 800.78791 33.9% - 1s
0 0 802.26672 0 139 1210.96756 802.26672 33.7% - 1s
0 0 803.00530 0 140 1210.96756 803.00530 33.7% - 1s
0 0 803.59475 0 121 1210.96756 803.59475 33.6% - 1s
0 0 804.28820 0 140 1210.96756 804.28820 33.6% - 1s
0 0 804.49263 0 141 1210.96756 804.49263 33.6% - 2s
0 0 804.83350 0 140 1210.96756 804.83350 33.5% - 2s
0 0 806.26469 0 135 1210.96756 806.26469 33.4% - 2s
0 0 806.85253 0 138 1210.96756 806.85253 33.4% - 2s
0 0 807.19502 0 142 1210.96756 807.19502 33.3% - 2s
0 0 807.48170 0 142 1210.96756 807.48170 33.3% - 2s
0 0 807.54095 0 138 1210.96756 807.54095 33.3% - 2s
0 0 808.10315 0 140 1210.96756 808.10315 33.3% - 3s
0 0 809.08659 0 141 1210.96756 809.08659 33.2% - 3s
0 0 809.32293 0 141 1210.96756 809.32293 33.2% - 3s
0 0 809.45265 0 144 1210.96756 809.45265 33.2% - 3s
0 0 809.66218 0 143 1210.96756 809.66218 33.1% - 3s
0 0 810.05278 0 135 1210.96756 810.05278 33.1% - 3s
0 0 810.27258 0 141 1210.96756 810.27258 33.1% - 4s
0 0 810.53570 0 142 1210.96756 810.53570 33.1% - 4s
0 0 810.62292 0 145 1210.96756 810.62292 33.1% - 4s
0 0 810.70679 0 148 1210.96756 810.70679 33.1% - 4s
0 0 811.22249 0 140 1210.96756 811.22249 33.0% - 4s
0 0 811.50205 0 143 1210.96756 811.50205 33.0% - 4s
0 0 811.90654 0 147 1210.96756 811.90654 33.0% - 4s
0 0 812.05994 0 148 1210.96756 812.05994 32.9% - 5s
0 0 812.06690 0 147 1210.96756 812.06690 32.9% - 5s
H 0 0 976.3104617 812.06690 16.8% - 5s
0 0 812.23518 0 145 976.31046 812.23518 16.8% - 5s
0 0 812.41923 0 140 976.31046 812.41923 16.8% - 5s
0 0 812.73465 0 135 976.31046 812.73465 16.8% - 6s
0 0 812.87351 0 133 976.31046 812.87351 16.7% - 6s
0 2 812.97538 0 130 976.31046 812.97538 16.7% - 6s
Cutting planes:
User: 92
MIR: 1
Lazy constraints: 24
Explored 1 nodes (5806 simplex iterations) in 6.89 seconds
Thread count was 8 (of 32 available processors)So yeah, we add far more cuts by using addCut() and the dual bound is better. But why? I thought because not all cuts in the cut pool are applied immediately, we get other fractional and integer solutions which in turn lead to other cuts (and lazy constraints). However, if we use addLazy() and addCut() for the identical capacity cut, we get a different result:
RCC added with addLazy() and addCut() at the root node in callback
Gurobi 9.1.0 (win64, C++) logging started Wed Jun 23 11:21:39 2021
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 32 physical cores, 32 logical processors, using up to 8 threads
Optimize a model with 864 rows, 1681 columns and 5000 nonzeros
Model fingerprint: 0x25402c11
Variable types: 0 continuous, 1681 integer (1681 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [4e+00, 7e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+01]
Warning: Completing partial solution with 1543 unfixed non-continuous variables out of 1681
User MIP start produced solution with objective 1210.97 (0.01s)
Loaded user MIP start with objective 1210.97
Presolve removed 24 rows and 84 columns
Presolve time: 0.01s
Presolved: 840 rows, 1597 columns, 4710 nonzeros
Variable types: 0 continuous, 1597 integer (1597 binary)
Root relaxation: objective 6.350581e+02, 115 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 656.63003 0 22 1210.96756 656.63003 45.8% - 0s
Warning: Completing partial solution with 1543 unfixed non-continuous variables out of 1681
0 0 690.73459 0 20 1210.96756 690.73459 43.0% - 0s
0 0 714.75147 0 26 1210.96756 714.75147 41.0% - 0s
0 0 722.86893 0 73 1210.96756 722.86893 40.3% - 0s
0 0 734.95932 0 74 1210.96756 734.95932 39.3% - 0s
0 0 746.53855 0 74 1210.96756 746.53855 38.4% - 0s
0 0 749.92056 0 80 1210.96756 749.92056 38.1% - 0s
0 0 755.88599 0 97 1210.96756 755.88599 37.6% - 0s
0 0 760.61964 0 91 1210.96756 760.61964 37.2% - 0s
0 0 762.20048 0 91 1210.96756 762.20048 37.1% - 0s
0 0 764.56252 0 93 1210.96756 764.56252 36.9% - 0s
0 0 767.24757 0 103 1210.96756 767.24757 36.6% - 0s
0 0 769.14751 0 123 1210.96756 769.14751 36.5% - 0s
0 0 770.01085 0 115 1210.96756 770.01085 36.4% - 0s
0 0 770.52077 0 117 1210.96756 770.52077 36.4% - 0s
0 0 773.09401 0 112 1210.96756 773.09401 36.2% - 0s
0 0 777.47505 0 120 1210.96756 777.47505 35.8% - 0s
0 0 778.81168 0 115 1210.96756 778.81168 35.7% - 0s
0 0 780.02747 0 121 1210.96756 780.02747 35.6% - 0s
0 0 782.40691 0 121 1210.96756 782.40691 35.4% - 0s
0 0 785.65042 0 122 1210.96756 785.65042 35.1% - 0s
0 0 787.79445 0 119 1210.96756 787.79445 34.9% - 0s
0 0 789.30579 0 131 1210.96756 789.30579 34.8% - 0s
0 0 790.91430 0 125 1210.96756 790.91430 34.7% - 0s
0 0 792.69096 0 130 1210.96756 792.69096 34.5% - 0s
0 0 794.66807 0 126 1210.96756 794.66807 34.4% - 1s
0 0 796.33139 0 128 1210.96756 796.33139 34.2% - 1s
0 0 799.42694 0 136 1210.96756 799.42694 34.0% - 1s
0 0 799.94925 0 132 1210.96756 799.94925 33.9% - 1s
0 0 800.73598 0 138 1210.96756 800.73598 33.9% - 1s
0 0 801.70511 0 140 1210.96756 801.70511 33.8% - 1s
0 0 802.04076 0 138 1210.96756 802.04076 33.8% - 1s
0 0 802.21635 0 138 1210.96756 802.21635 33.8% - 1s
0 0 802.49615 0 137 1210.96756 802.49615 33.7% - 2s
0 0 802.70435 0 137 1210.96756 802.70435 33.7% - 2s
0 0 802.99018 0 135 1210.96756 802.99018 33.7% - 2s
0 0 803.26481 0 140 1210.96756 803.26481 33.7% - 2s
0 0 803.53421 0 133 1210.96756 803.53421 33.6% - 2s
0 0 803.80758 0 140 1210.96756 803.80758 33.6% - 2s
0 0 804.86543 0 139 1210.96756 804.86543 33.5% - 2s
0 0 805.59449 0 134 1210.96756 805.59449 33.5% - 3s
0 0 806.00456 0 142 1210.96756 806.00456 33.4% - 3s
0 0 806.80355 0 132 1210.96756 806.80355 33.4% - 3s
0 0 807.31799 0 141 1210.96756 807.31799 33.3% - 3s
0 0 807.53740 0 142 1210.96756 807.53740 33.3% - 3s
0 0 807.78106 0 143 1210.96756 807.78106 33.3% - 3s
0 0 808.00916 0 133 1210.96756 808.00916 33.3% - 3s
0 0 808.19162 0 135 1210.96756 808.19162 33.3% - 4s
0 0 808.66099 0 137 1210.96756 808.66099 33.2% - 4s
0 0 808.91615 0 140 1210.96756 808.91615 33.2% - 4s
0 0 809.05086 0 136 1210.96756 809.05086 33.2% - 4s
0 0 809.48227 0 140 1210.96756 809.48227 33.2% - 4s
0 0 809.71797 0 138 1210.96756 809.71797 33.1% - 4s
0 0 809.83732 0 140 1210.96756 809.83732 33.1% - 4s
0 0 810.37903 0 133 1210.96756 810.37903 33.1% - 5s
0 0 810.51096 0 133 1210.96756 810.51096 33.1% - 5s
0 0 810.66057 0 139 1210.96756 810.66057 33.1% - 5s
0 0 810.78408 0 138 1210.96756 810.78408 33.0% - 5s
0 0 810.96621 0 142 1210.96756 810.96621 33.0% - 5s
0 0 811.13948 0 136 1210.96756 811.13948 33.0% - 5s
0 0 811.22811 0 140 1210.96756 811.22811 33.0% - 5s
0 0 811.42782 0 138 1210.96756 811.42782 33.0% - 6s
0 0 811.55217 0 139 1210.96756 811.55217 33.0% - 6s
0 0 811.58976 0 139 1210.96756 811.58976 33.0% - 6s
0 0 811.64576 0 141 1210.96756 811.64576 33.0% - 6s
0 0 811.72423 0 146 1210.96756 811.72423 33.0% - 6s
0 0 811.73942 0 147 1210.96756 811.73942 33.0% - 6s
H 0 0 976.3104617 811.73942 16.9% - 6s
0 0 811.73942 0 144 976.31046 811.73942 16.9% - 7s
0 2 811.73942 0 140 976.31046 811.73942 16.9% - 7s
Cutting planes:
User: 79
Lazy constraints: 1471This is a surprising result, at least for me, because
Lazy constraints are added directly to the LP relaxation, but user cuts must survive Gurobi's cut filtering process to make it to the LP relaxation. Since you add the capacity cut as a lazy constraint, the identical user cut is effectively useless.
If the user cut is effectively useless, why is the behavior different from the run with only addLazy()?
I like the idea of adding such capacity cuts as lazy constraints from the perspective that they may cut off integer-feasible solutions. However, like I mentioned, the orthogonality, strength, and quantity of the capacity cuts may impact Gurobi's performance. So, a more conservative approach would be to add such capacity cuts as user cuts to take advantage of Gurobi's internal cut filtering, then separate lazy constraints as necessary when Gurobi presents you with new incumbent solutions.
Thank you for your input. We also observed that the node throughput gets worse if we add all capacity cuts as lazy constraints (after the root node). That is obvious. However, if we add all CC as user cuts, the dual bound improvement is slower and it seems that not many cuts are used. A way to influence this as a user would be nice. But that's a different topic.
Thanks again for your great effort. We very much appreciate the support from Gurobi.
Felix
1 -
Still, I wonder why a lazy contraint in Mario's approach was ignored. But of course you can't answer that without knowing their algorithm.
If LazyConstraints is set to \( 1 \), adding a lazy constraint in a \( \texttt{MIPSOL} \) callback that cuts off an otherwise feasible solution should invalidate that solution. Most of the time, issues with lazy constraints not working properly are due to a subtle error in the user's code. That said, if there is a bug in Gurobi, we of course would like to fix it.
There has been at least one issue with user cuts that's been fixed since Gurobi 9.1.0 (the version you're using). I always recommend using the latest version of Gurobi (currently 9.1.2) to rule out any possibility of stumbling across bugs that have already been fixed.
So yeah, we add far more cuts by using addCut() and the dual bound is better. But why? I thought because not all cuts in the cut pool are applied immediately, we get other fractional and integer solutions which in turn lead to other cuts (and lazy constraints).
User cuts can be added to the LP relaxation multiple times at the root node. Depending on exactly what user cuts you add, it's possible a high percentage of them make it into the LP relaxation very quickly.
If the user cut is effectively useless, why is the behavior different from the run with only addLazy()?
I was suggesting that generating capacity cuts in each \( \texttt{MIPNODE} \) callback and adding them as lazy constraints would behave very similarly to generating capacity cuts in each \( \texttt{MIPNODE} \) callback and adding them as lazy constraints and user cuts. I.e., the only difference between the two algorithms is that the latter has an extra call to GRBCallback::addCut() using exactly the same arguments as the call to GRBCallback::addLazy(). Is this the comparison you're making in your tests? I am wondering because only 24 lazy constraints are added in the addLazy() test, but 1471 lazy constraints are added in the addLazy()+addCut() test.
1 -
Hi Eli,
we've been a little distracted the last few months and thought if it works, it works. However, we have encountered another strange behavior that is probably related to this. Just to answer your last question
I was suggesting that generating capacity cuts in each callback and adding them as lazy constraints would behave very similarly to generating capacity cuts in each callback and adding them as lazy constraints and user cuts. I.e., the only difference between the two algorithms is that the latter has an extra call to GRBCallback::addCut() using exactly the same arguments as the call to GRBCallback::addLazy(). Is this the comparison you're making in your tests? I am wondering because only 24 lazy constraints are added in the addLazy() test, but 1471 lazy constraints are added in the addLazy()+addCut() test.
Yes, the only difference between the variants is that we add the same cut with the exact same arguments as
- lazy constraint with addLazy()
- user cut with addCut()
- user cut and lazy constraint
The difference between 1 and 3 was somewhat surprising for us. But it has worked, and we thought that if the algorithm is correct, as long as we check every integer solution, then everything is okay.
Enter new tests:
Gurobi 9.1.2 (win64, C++) logging started Mon Sep 13 16:36:09 2021
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 32 physical cores, 32 logical processors, using up to 8 threads
Optimize a model with 137 rows, 256 columns and 720 nonzeros
Model fingerprint: 0x2c08e0ed
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 478.678 (0.00s)
Loaded user MIP start with objective 478.678
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
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 295.17078 0 24 478.67762 295.17078 38.3% - 0s
H 0 0 456.3973832 302.74724 33.7% - 0s
0 0 302.74724 0 20 456.39738 302.74724 33.7% - 0s
0 0 306.08709 0 16 456.39738 306.08709 32.9% - 0s
0 0 312.86093 0 12 456.39738 312.86093 31.4% - 0s
0 0 316.28597 0 27 456.39738 316.28597 30.7% - 0s
0 0 321.66706 0 33 456.39738 321.66706 29.5% - 0s
0 0 323.40913 0 37 456.39738 323.40913 29.1% - 0s
0 0 324.66363 0 33 456.39738 324.66363 28.9% - 0s
0 0 324.84768 0 49 456.39738 324.84768 28.8% - 0s
0 0 325.40616 0 46 456.39738 325.40616 28.7% - 0s
0 0 325.63595 0 42 456.39738 325.63595 28.7% - 0s
0 0 325.65225 0 50 456.39738 325.65225 28.6% - 0s
0 0 325.70736 0 41 456.39738 325.70736 28.6% - 0s
0 0 325.70736 0 41 456.39738 325.70736 28.6% - 0s
0 2 325.70736 0 41 456.39738 325.70736 28.6% - 0s
H 56 51 334.9638862 328.86492 1.82% 23.3 1s
H 57 51 324.4032685 324.40327 0.00% 22.9 1s
Cutting planes:
User: 107
MIR: 2
Lazy constraints: 50
Explored 63 nodes (1699 simplex iterations) in 1.97 seconds
Thread count was 8 (of 32 available processors)
Solution count 4: 324.403 334.964 456.397 478.678
Optimal solution found (tolerance 1.00e-04)
Best objective 3.244032684765e+02, best bound 3.244032684765e+02, gap 0.0000%
User-callback calls 381, time in user-callback 1.77 secThe last found solution with objective function value 324.4032685 is definitely infeasible. The route exceeds the capacity of the vehicle and we add a lazy constraint (addLazy()) to prohibit this route. But the solution is accepted nevertheless. The added lazy constraint is correct, it's a simple RCC. The true optimal value is 334.9638862. We know this because almost all other runs (i.e., with different seeds) return 334.9638862 and this solution is feasible.
Gurobi 9.1.2 (win64, C++) logging started Mon Sep 13 16:53:17 2021
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 32 physical cores, 32 logical processors, using up to 8 threads
Optimize a model with 137 rows, 256 columns and 720 nonzeros
Model fingerprint: 0x2c08e0ed
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 478.678 (0.00s)
Loaded user MIP start with objective 478.678
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
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 295.17078 0 24 478.67762 295.17078 38.3% - 0s
H 0 0 456.3973832 302.74724 33.7% - 0s
0 0 302.74724 0 20 456.39738 302.74724 33.7% - 0s
0 0 306.08709 0 10 456.39738 306.08709 32.9% - 0s
0 0 313.95663 0 21 456.39738 313.95663 31.2% - 0s
0 0 316.73448 0 33 456.39738 316.73448 30.6% - 0s
0 0 319.30077 0 20 456.39738 319.30077 30.0% - 0s
0 0 321.10733 0 43 456.39738 321.10733 29.6% - 0s
0 0 322.44012 0 38 456.39738 322.44012 29.4% - 0s
0 0 324.08663 0 8 456.39738 324.08663 29.0% - 0s
H 0 0 453.5548073 324.08663 28.5% - 0s
0 2 324.53158 0 22 453.55481 324.53158 28.4% - 0s
* 42 39 6 344.1105565 325.75453 5.33% 19.9 1s
H 75 39 341.9984295 325.75453 4.75% 15.2 1s
* 303 112 20 334.9638862 325.75453 2.75% 12.8 3s
Cutting planes:
User: 98
Lazy constraints: 128
Explored 462 nodes (5105 simplex iterations) in 4.10 seconds
Thread count was 8 (of 32 available processors)
Solution count 6: 334.964 341.998 344.111 ... 478.678
Optimal solution found (tolerance 1.00e-04)
Best objective 3.349638862376e+02, best bound 3.349638862376e+02, gap 0.0000%
User-callback calls 1209, time in user-callback 3.77 secIt is also strange that the false objective function value is lower than the lower bound in the row above. But maybe that's because of multiple threads?
Best regards
Felix
1 -
Hi again,
we add another example to provide some more detailed information.
At first some preliminary remarks:
- 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 999 out of 1000 runs. However, sometimes an infeasible solution is accepted as feasible even though we add a lazy constraint. Consider the log file below. In addition to the gurobi output, this also shows the nodes in the lazy constraints/ user cuts and the minimum number of vehicles required (minV).
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Thread count: 32 physical cores, 32 logical processors, using up to 8 threads
Optimize a model with 137 rows, 256 columns and 720 nonzeros
Model fingerprint: 0x2c08e0ed
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 478.678 (0.00s)
Loaded user MIP start with objective 478.678
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
Lazy constraint: 2 | 3 | 4 | 5 | 7 | 8 | 9 | 10 | 13 | 14 | 15 | minV: 4
Lazy constraint: 1 | 2 | 3 | 6 | 7 | 8 | 9 | 10 | 15 | minV: 3
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 295.17078 0 24 478.67762 295.17078 38.3% - 0s
Lazy constraint: 2 | 3 | 9 | 10 | 11 | 15 | minV: 2
Lazy constraint: 1 | 2 | 3 | 7 | 8 | minV: 2
Lazy constraint: 2 | 3 | 6 | minV: 2
Lazy constraint: 4 | 5 | 9 | 14 | 15 | minV: 2
User cut: 1 | 2 | 3 | 5 | 7 | 8 | 9 | 10 | 11 | 15 | minV: 3
User cut: 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 5
Solution found with heuristic with 5 vehicles and costs 456.397383
Lazy constraint: 2 | 3 | 6 | 7 | 8 | 11 | minV: 3
H 0 0 456.3973832 303.09807 33.6% - 0s
0 0 303.09807 0 30 456.39738 303.09807 33.6% - 0s
Lazy constraint: 6 | 13 | 14 | minV: 2
Lazy constraint: 5 | 9 | 10 | 11 | 12 | 15 | minV: 2
Lazy constraint: 4 | 5 | 13 | 14 | minV: 2
Lazy constraint: 9 | 10 | 11 | 12 | 15 | minV: 2
Lazy constraint: 3 | 5 | 9 | 11 | minV: 2
Lazy constraint: 1 | 2 | 4 | 7 | 8 | 13 | 14 | minV: 3
User cut: 1 | 2 | 3 | 4 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
Lazy constraint: 6 | 7 | 8 | minV: 2
Lazy constraint: 5 | 9 | 10 | 12 | 15 | minV: 2
0 0 310.50955 0 20 456.39738 310.50955 32.0% - 0s
Lazy constraint: 4 | 12 | 13 | minV: 2
Lazy constraint: 2 | 3 | 7 | 8 | minV: 2
Lazy constraint: 5 | 9 | 10 | 11 | 15 | minV: 2
Lazy constraint: 1 | 3 | 6 | 8 | minV: 2
User cut: 1 | 2 | 3 | 8 | minV: 2
User cut: 2 | 3 | 8 | minV: 2
User cut: 2 | 3 | 4 | 5 | 8 | 9 | 10 | 12 | 13 | 15 | minV: 4
User cut: 2 | 3 | 5 | 8 | 9 | 10 | 12 | 15 | minV: 3
User cut: 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 5
User cut: 2 | 3 | 7 | 8 | 9 | 10 | 15 | minV: 3
User cut: 2 | 3 | 8 | 9 | 10 | 11 | 15 | minV: 3
User cut: 2 | 3 | 4 | 8 | 12 | 13 | minV: 3
User cut: 2 | 3 | 4 | 5 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 4
User cut: 2 | 3 | 5 | 8 | 9 | 10 | 15 | minV: 3
User cut: 2 | 3 | 4 | 7 | 8 | 13 | minV: 3
User cut: 4 | 12 | 13 | minV: 2
User cut: 2 | 3 | 7 | 8 | minV: 2
User cut: 2 | 3 | 7 | 8 | 12 | minV: 3
User cut: 2 | 3 | 6 | 7 | 8 | 14 | minV: 3
User cut: 2 | 3 | 4 | 5 | 6 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 2 | 3 | 4 | 5 | 8 | 9 | 10 | 11 | 12 | 13 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 2 | 3 | 5 | 8 | 9 | 10 | 11 | 15 | minV: 3
User cut: 1 | 2 | 3 | 5 | 8 | 9 | 10 | 11 | 12 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 15 | minV: 5
User cut: 2 | 3 | 8 | 9 | 10 | 15 | minV: 2
User cut: 1 | 2 | 3 | 8 | 9 | 10 | 11 | 15 | minV: 3
User cut: 2 | 3 | 6 | 7 | 8 | 9 | 10 | 15 | minV: 3
User cut: 2 | 3 | 6 | 7 | 8 | 9 | 10 | 11 | 14 | 15 | minV: 4
User cut: 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 5
User cut: 2 | 3 | 4 | 6 | 7 | 8 | 12 | 13 | 14 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 5
Lazy constraint: 1 | 2 | 3 | 11 | minV: 2
0 0 320.44303 0 22 456.39738 320.44303 29.8% - 0s
Lazy constraint: 4 | 6 | 13 | 14 | minV: 2
User cut: 1 | 2 | 3 | 7 | 8 | 11 | minV: 3
User cut: 2 | 3 | 11 | minV: 2
User cut: 7 | 8 | 14 | minV: 2
User cut: 2 | 3 | 5 | 9 | 10 | 11 | 15 | minV: 3
User cut: 1 | 2 | 3 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 5
User cut: 1 | 2 | 3 | 7 | 8 | 14 | minV: 3
0 0 320.66256 0 12 456.39738 320.66256 29.7% - 0s
Lazy constraint: 4 | 9 | 10 | 11 | 13 | 15 | minV: 2
Lazy constraint: 4 | 12 | 13 | 14 | minV: 2
Lazy constraint: 2 | 4 | 7 | 14 | minV: 2
Lazy constraint: 4 | 12 | 14 | minV: 2
Lazy constraint: 1 | 4 | 8 | 10 | 11 | 14 | minV: 2
User cut: 4 | 9 | 10 | 11 | 13 | 15 | minV: 2
User cut: 4 | 6 | 7 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 3
User cut: 4 | 7 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 3
User cut: 4 | 6 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 3
0 0 321.66706 0 21 456.39738 321.66706 29.5% - 0s
User cut: 4 | 9 | 10 | 13 | 15 | minV: 2
Lazy constraint: 1 | 2 | 3 | 6 | minV: 2
Lazy constraint: 5 | 6 | 12 | minV: 2
Lazy constraint: 3 | 5 | 6 | 12 | minV: 2
Lazy constraint: 4 | 9 | 10 | 11 | 14 | 15 | minV: 2
Lazy constraint: 4 | 9 | 10 | 14 | 15 | minV: 2
Lazy constraint: 4 | 6 | 7 | 13 | 14 | minV: 2
Lazy constraint: 5 | 11 | 12 | minV: 2
Lazy constraint: 1 | 2 | 3 | 5 | 12 | minV: 2
Lazy constraint: 5 | 7 | 8 | 12 | minV: 2
Lazy constraint: 4 | 5 | 9 | 10 | 11 | 12 | 13 | 14 | minV: 3
Lazy constraint: 1 | 6 | 7 | 8 | minV: 2
Lazy constraint: 9 | 10 | 11 | 13 | 14 | minV: 2
Lazy constraint: 2 | 9 | 10 | 15 | minV: 2
Lazy constraint: 1 | 3 | 4 | 7 | 13 | 14 | minV: 2
Lazy constraint: 12 | 13 | 14 | minV: 2
Lazy constraint: 4 | 5 | 9 | 10 | 15 | minV: 2
Lazy constraint: 2 | 6 | 7 | minV: 2
Lazy constraint: 5 | 12 | 13 | minV: 2
Lazy constraint: 2 | 7 | 8 | 11 | minV: 2
Lazy constraint: 2 | 7 | 8 | minV: 2
Lazy constraint: 1 | 8 | 9 | 10 | 11 | 15 | minV: 2
Lazy constraint: 1 | 8 | 10 | 11 | 12 | minV: 2
Lazy constraint: 1 | 3 | 5 | 6 | 8 | 10 | 11 | minV: 2
Lazy constraint: 3 | 5 | 6 | 9 | 15 | minV: 2
Lazy constraint: 1 | 8 | 10 | 11 | 12 | 13 | minV: 2
User cut: 1 | 2 | 3 | 4 | 7 | 8 | 11 | 13 | 14 | minV: 4
User cut: 4 | 7 | 13 | 14 | minV: 2
User cut: 4 | 6 | 7 | 12 | 13 | 14 | minV: 3
User cut: 1 | 3 | 4 | 7 | 8 | 13 | 14 | minV: 3
0 2 323.05575 0 14 456.39738 323.05575 29.2% - 0s
User cut: 4 | 5 | 9 | 10 | 11 | 12 | 13 | 15 | minV: 3
User cut: 4 | 5 | 6 | 7 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 4
User cut: 4 | 5 | 7 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 4
User cut: 5 | 9 | 10 | 11 | minV: 2
User cut: 3 | 7 | 8 | minV: 2
User cut: 4 | 13 | 14 | 15 | minV: 2
User cut: 2 | 3 | 4 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 2 | 3 | 4 | 7 | 8 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 4
User cut: 2 | 4 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 3
User cut: 4 | 5 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 3
User cut: 2 | 4 | 5 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 4
User cut: 2 | 9 | 10 | 11 | minV: 2
User cut: 4 | 5 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 3
User cut: 2 | 5 | 9 | 10 | 11 | 12 | 15 | minV: 3
User cut: 2 | 3 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 15 | minV: 4
User cut: 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 2 | 3 | 6 | 7 | minV: 2
Lazy constraint: 2 | 3 | 6 | 7 | minV: 2
User cut: 2 | 3 | 9 | 10 | 15 | minV: 2
User cut: 1 | 2 | 3 | 6 | 9 | 10 | 11 | 15 | minV: 3
User cut: 1 | 2 | 3 | 7 | 8 | 9 | 10 | 15 | minV: 3
User cut: 2 | 3 | 9 | 10 | 15 | minV: 2
User cut: 1 | 2 | 3 | 6 | 9 | 10 | 11 | 15 | minV: 3
User cut: 1 | 2 | 3 | 7 | 8 | 9 | 10 | 15 | minV: 3
Lazy constraint: 2 | 3 | 9 | 10 | 15 | minV: 2
User cut: 1 | 2 | 3 | 6 | 7 | minV: 2
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
Lazy constraint: 1 | 2 | 3 | 6 | 7 | minV: 2
User cut: 1 | 2 | 3 | 9 | 10 | minV: 2
User cut: 4 | 7 | 8 | 13 | minV: 2
User cut: 1 | 2 | 3 | 9 | 10 | 11 | 12 | 15 | minV: 3
User cut: 1 | 2 | 3 | 4 | 9 | 10 | 13 | 15 | minV: 3
User cut: 1 | 2 | 3 | 4 | 7 | 8 | 9 | 10 | 13 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 1 | 2 | 3 | 5 | 9 | 10 | 12 | 15 | minV: 3
User cut: 4 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 9 | 10 | minV: 2
User cut: 4 | 7 | 8 | 13 | minV: 2
User cut: 1 | 2 | 3 | 9 | 10 | 11 | 12 | 15 | minV: 3
User cut: 1 | 2 | 3 | 4 | 9 | 10 | 13 | 15 | minV: 3
User cut: 1 | 2 | 3 | 4 | 7 | 8 | 9 | 10 | 13 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 4 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 5 | 9 | 10 | 12 | 15 | minV: 3
User cut: 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 5
Lazy constraint: 1 | 2 | 3 | 12 | minV: 2
User cut: 1 | 3 | 7 | 8 | minV: 2
User cut: 1 | 2 | 3 | 7 | 8 | 9 | 10 | minV: 3
User cut: 1 | 7 | 8 | 11 | minV: 2
User cut: 1 | 4 | 5 | 7 | 8 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 4
User cut: 1 | 5 | 7 | 8 | 9 | 10 | 11 | 15 | minV: 3
User cut: 1 | 2 | 3 | 7 | 8 | 11 | minV: 3
User cut: 1 | 2 | 3 | 5 | 7 | 8 | 9 | 10 | 12 | 15 | minV: 4
User cut: 1 | 3 | 7 | 8 | minV: 2
User cut: 1 | 2 | 3 | 7 | 8 | 9 | 10 | minV: 3
User cut: 1 | 7 | 8 | 11 | minV: 2
User cut: 1 | 4 | 5 | 7 | 8 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 4
User cut: 1 | 5 | 7 | 8 | 9 | 10 | 11 | 15 | minV: 3
User cut: 1 | 2 | 3 | 5 | 7 | 8 | 9 | 10 | 12 | 15 | minV: 4
Lazy constraint: 1 | 5 | 7 | 8 | 12 | minV: 2
User cut: 2 | 3 | 7 | minV: 2
User cut: 1 | 2 | 3 | 7 | minV: 2
User cut: 1 | 2 | 3 | 4 | 6 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 5 | 9 | 10 | 11 | 15 | minV: 3
User cut: 1 | 2 | 3 | 4 | 5 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 4
User cut: 1 | 2 | 7 | 8 | minV: 2
User cut: 1 | 2 | 7 | 8 | minV: 2
User cut: 7 | 8 | 13 | minV: 2
Lazy constraint: 7 | 8 | 13 | minV: 2
User cut: 7 | 8 | 13 | minV: 2
User cut: 1 | 2 | 3 | 4 | 6 | 7 | 8 | 11 | 13 | 14 | minV: 4
User cut: 7 | 13 | 14 | minV: 2
User cut: 1 | 2 | 3 | 6 | 7 | 8 | 11 | 13 | 14 | minV: 4
User cut: 1 | 3 | 4 | 5 | 6 | 7 | 8 | 12 | 13 | 14 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 11 | 12 | 13 | 14 | minV: 5
User cut: 1 | 3 | 6 | 7 | 8 | 13 | 14 | minV: 3
User cut: 1 | 3 | 4 | 6 | 7 | 8 | 13 | 14 | minV: 3
User cut: 2 | 3 | 4 | 5 | 6 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 4
User cut: 4 | 5 | 6 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 3
User cut: 6 | 12 | 14 | minV: 2
User cut: 4 | 5 | 6 | 10 | 11 | 12 | 14 | 15 | minV: 3
User cut: 4 | 6 | 12 | 14 | 15 | minV: 2
User cut: 4 | 6 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 3
User cut: 4 | 6 | 10 | 12 | 13 | 14 | 15 | minV: 3
User cut: 4 | 5 | 6 | 9 | 10 | 11 | 14 | 15 | minV: 3
User cut: 2 | 3 | 9 | minV: 2
User cut: 4 | 6 | 10 | 14 | 15 | minV: 2
User cut: 2 | 3 | 4 | 6 | 9 | 10 | 14 | 15 | minV: 3
User cut: 2 | 3 | 4 | 5 | 6 | 9 | 10 | 12 | 14 | 15 | minV: 4
User cut: 4 | 6 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 3
User cut: 2 | 3 | 4 | 6 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 4
User cut: 4 | 5 | 6 | 9 | 10 | 12 | 14 | 15 | minV: 3
User cut: 1 | 4 | 6 | 7 | 8 | 13 | 14 | minV: 3
User cut: 1 | 4 | 5 | 6 | 7 | 8 | 12 | 13 | 14 | minV: 4
User cut: 1 | 2 | 3 | 8 | 9 | 10 | 11 | minV: 3
User cut: 1 | 2 | 3 | 4 | 8 | 9 | 10 | 11 | 13 | 14 | 15 | minV: 4
Lazy constraint: 1 | 3 | 5 | 6 | 8 | 11 | minV: 2
Lazy constraint: 1 | 3 | 6 | 8 | 11 | minV: 2
Lazy constraint: 1 | 2 | 7 | 8 | minV: 2
Lazy constraint: 7 | 9 | 14 | 15 | minV: 2
Lazy constraint: 1 | 2 | 8 | 10 | 11 | minV: 2
User cut: 4 | 8 | 13 | 14 | minV: 2
User cut: 1 | 2 | 3 | 4 | 5 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
Lazy constraint: 4 | 8 | 13 | 14 | minV: 2
User cut: 5 | 9 | 10 | 13 | 15 | minV: 2
User cut: 4 | 5 | 6 | 9 | 10 | 13 | 14 | 15 | minV: 3
User cut: 4 | 6 | 11 | 12 | 13 | 14 | minV: 3
Lazy constraint: 2 | 4 | 9 | 14 | 15 | minV: 2
Lazy constraint: 1 | 3 | 5 | 8 | 10 | 11 | minV: 2
User cut: 5 | 9 | 10 | 13 | 15 | minV: 2
User cut: 4 | 5 | 6 | 9 | 10 | 13 | 14 | 15 | minV: 3
User cut: 4 | 6 | 11 | 12 | 13 | 14 | minV: 3
Lazy constraint: 1 | 2 | 7 | 10 | 11 | 13 | minV: 2
User cut: 5 | 9 | 10 | 11 | 12 | 13 | 15 | minV: 3
User cut: 4 | 12 | 13 | 15 | minV: 2
User cut: 1 | 2 | 3 | 4 | 6 | 7 | 8 | 11 | 12 | 13 | 14 | 15 | minV: 5
Lazy constraint: 4 | 12 | 13 | 15 | minV: 2
Solution found with heuristic with 5 vehicles and costs 351.158566
H 44 45 351.1585659 330.90865 5.77% 13.1 0s
User cut: 3 | 4 | 6 | 7 | 8 | 13 | 14 | minV: 3
User cut: 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 2 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | minV: 5
User cut: 7 | 8 | 11 | minV: 2
User cut: 2 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 15 | minV: 4
User cut: 2 | 4 | 5 | 6 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 5
User cut: 2 | 4 | 5 | 6 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 9 | 10 | 12 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 5 | 9 | 10 | 11 | 12 | 13 | 15 | minV: 4
User cut: 7 | 8 | 11 | minV: 2
User cut: 1 | 2 | 3 | 4 | 6 | 9 | 10 | 12 | 13 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 5 | 9 | 10 | 11 | 12 | 13 | 15 | minV: 4
User cut: 2 | 4 | 5 | 6 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 14 | 15 | minV: 5
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 9 | 10 | 12 | 14 | 15 | minV: 4
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 9 | 10 | 13 | 14 | 15 | minV: 4
User cut: 5 | 9 | 10 | 12 | minV: 2
User cut: 5 | 9 | 10 | 12 | minV: 2
User cut: 2 | 3 | 4 | 6 | 13 | 14 | minV: 3
User cut: 1 | 3 | 6 | 7 | minV: 2
User cut: 1 | 3 | 6 | 7 | minV: 2
User cut: 1 | 2 | 3 | 4 | 6 | 13 | 14 | minV: 3
User cut: 1 | 2 | 3 | 4 | 5 | 6 | 12 | 13 | 14 | minV: 4
* 79 54 12 334.9638862 331.12633 1.15% 9.8 0s
Lazy constraint: 2 | 3 | 5 | 11 | minV: 2
H 82 54 321.4782436 321.47824 0.00% 9.6 0s
Cutting planes:
User: 120
MIR: 1
Lazy constraints: 72
Explored 92 nodes (1114 simplex iterations) in 0.96 seconds
Thread count was 8 (of 32 available processors)
Solution count 5: 321.478 334.964 351.159 ... 478.678
Optimal solution found (tolerance 1.00e-04)
Best objective 3.214782435696e+02, best bound 3.214782435696e+02, gap 0.0000%
User-callback calls 473, time in user-callback 0.76 secThe most important lines are at the end right above the added cuts:
* 79 54 12 334.9638862 331.12633 1.15% 9.8 0s
Lazy constraint: 2 | 3 | 5 | 11 | minV: 2
H 82 54 321.4782436 321.47824 0.00% 9.6 0sSome, at least for us, strange things happen there. The infeasible solution with value 321.478 contains a route 11 - 2 - 3 - 5. However, we have added a lazy constraint with exactly these nodes to eliminate this route in the MIPSOL callback. Note that this lazy constraint has not been added as user cut before. What is equally confusing for us, is that the objective function value is below the known lower bound (see image below). Why is the solution checked at all if its value is less than the lower bound?
If you are interested, we can also discuss this via screensharing or similar.
Best regards
Felix
1 -
Thanks for the nice explanation. Are you able to set up a GitHub repository with code that reproduces the issue? Gurobi should discard that infeasible solution if you add a lazy constraint in the corresponding \( \texttt{MIPSOL} \) callback that cuts it off.
1 -
We have a private GitHub repository. The project is quite large and requires Google or-tools to solve a subproblem. We can invite you to the repo. If you do not share your e-mail address here, you can write me an e-mail at felix.tamke[at]tu-dresden.de.
1 -
Hi,
since I have a very similar problem (build 10.0.0rc2, linux64), I'd like to ask if the issue is fixed in this version.
I found
"
- Fixed numerical issue that lead to not cutting off a solution even though a lazy constraint was added in the callback
"
in the release notes of 10.0.0; though, some lazy constraints seem to be ignored, as described in Felix Tamke's post. It also does not seem to be a numerical issue, since the violation is considerable, and the cut coefficients are of reasonabe scale.
Changing Parameters like "Seed" or "Threads" influencing the course of B&B sometimes prevent this to happen (i.e., the code runs well then).
I also was able to reproduce this (with another instance, though) in single-thread mode.
Best Regards from Erlangen,
Florian Rösel
Here some detailed information:
...
Gurobi Optimizer version 10.0.0 build v10.0.0rc2 (linux64)
...
... somewhere in the output:
[ 2. 2. 5. 3. 2. 7. 4. 6. 2. 3. 6. 6. 7. 3. -0. 4. 2. 3.
12. 6. 4. 6. 2. 7. 2. 10. 1. 5. 1. 1. 1. 3.]
2023-03-16 10:46:12,557, MSGE: CUT 0.0 >= 687.2088853971509
2023-03-16 10:46:12,557, MSGE: Ins. MD-Feas-Cut. Incumbent: 1007.0. Depth: 687.2. Alpha: 0.0000000
* 181 101 19 640.0000000 635.00000 0.78% 2.2 6sThe third line prints out LHS and RHS (for the current solution candidate, to be cut off) of the Lazy Cut added in the code line before (I doublechecked felt 15 times that this is correct..).
Furthermore, I stored all evaluated Lazy Cuts in a list and evaluated them with the solution spit out by the optimizer in the end; this is the result:
CUT 0.0 >= 687.2088853971491
129882.4793400438
- 2748.835541588227 y_1_1_6 (2)
- 2748.835541588227 y_1_2_3 (5)
- 2748.835541588227 y_1_2_7 (3)
- 2748.835541588227 y_1_3_8 (2)
- 2748.835541588227 y_1_5_10 (6)
- 2748.835541588227 y_1_6_11 (2)
- 2748.835541588227 y_1_7_8 (3)
- 2748.835541588227 y_1_9_14 (7)
- 2748.835541588227 y_1_11_12 (0)
- 2748.835541588227 y_1_12_17 (4)
- 2748.8355415882274 y_1_12_13 (2)
+ 5.052748343182935e-13 y_1_13_18 (3)
- 2748.835541588227 y_1_18_19 (10)
- 2748.835541588227 y_1_23_24 (1)The sol file says
y_1_1_2 1.9999999999999973e+00
y_1_1_6 2
y_1_2_3 5
y_1_2_7 3
y_1_3_8 2
y_1_3_4 7
y_1_4_5 4
y_1_5_10 6.0000000000000009e+00
y_1_6_11 2
y_1_7_8 3
y_1_7_12 6
y_1_9_10 6
y_1_9_14 7
y_1_11_16 3
y_1_11_12 0
y_1_12_17 4
y_1_12_13 2
y_1_13_18 3
y_1_14_19 12
y_1_14_15 6
y_1_15_20 4
y_1_16_17 6.0000000000000027e+00
y_1_16_21 2
y_1_17_18 7
y_1_17_22 1.9999999999999991e+00
y_1_18_19 10
y_1_18_23 1.0000000000000009e+00
y_1_19_24 4.9999999999999982e+00
y_1_21_22 1
y_1_22_23 1
y_1_23_24 1
y_1_24_25 31 -
Hi Florian,
Just to be sure, are you also adding the same type of cuts as user-cuts in a MIPNODE callback (to strengthen the bounds)?
If yes, can you also reproduce the issue when adding all cuts of this type as lazy cuts even in a MIPNODE callback, i.e., replacing all appearances of addCut() by addLazy()?Best regards,
Mario0 -
Hi,
I use only cbLazy(), with where == MIPSOL. Python Interface.
if where == grb.GRB.Callback.MIPSOL:
...
model.cbLazy(CUT)
.
0 -
Hi Florian,
Ok, this is interesting and might be different to the previous cases.
Could you create a minimal reproducible example that we could run on our side?0 -
Sure. I will send it directly to you, as soon as possible (currently busy with other things, but I should be able to create a minimal example within a couple of days).
Thanks for your fast response! :)
0
サインインしてコメントを残してください。
コメント
19件のコメント