Redundant Cuts using Lazy
Answered
Hello,
I'm working on a branch-and-cut algorithm. Through my analysis of the algorithm's efficiency, I noticed that many of the lazy constraints are redundant. Specifically, even after cutting a solution, I often detect the same solution again. To address this, I store the added cuts added, and whenever I compute a new cut, I check if it already exists among the stored ones. Aren't lazy cuts supposed to be added directly to the model? What could explain this behavior? I believe this might be a crucial factor affecting the algorithm's efficiency, as adding the same cut multiple times slows down the computations.
Thank you,
PS1: My cuts are feasibility cuts, so adding them to the model using lazy constraints is mandatory.
PS2: I asked a colleague who is also working on a branch-and-cut algorithm for a different problem to check if he has the same issue, and he confirmed that he does.
-
Hi Eliass,
Aren't lazy cuts supposed to be added directly to the model? What could explain this behavior?
Yes, the lazy cuts are added directly to the LP relaxation. However, the behaviour you observed is expected.
Due to multi-threading and the time it takes for newly added lazy constraints to sync among all threads, you might encounter solutions that violate previously added lazy constraints. The important point is that in every MIPSOL callback, every new solution should be examined, and a lazy constraint should be added if the new solution is invalid, regardless of whether the same lazy constraint was added previously.
Best regards,
Maliheh
0 -
Thank you Maliheh for your quick answer. I understand your point.
Due to multi-threading and the time it takes for newly added lazy constraints to sync among all threads, you might encounter solutions that violate previously added lazy constraints.
However, in my code, I disabled multi-threading in Gurobi. I'm coding in C++, so I set
GRB_IntParam_Threadsto 1. Shouldn't this deactivate multi-threading, making the sync among nodes faster ?0 -
This is a bit strange, given that you have set the Threads parameter to 1. I have consulted our development team about this issue. A likely explanation could be that multiple heuristics applied to the same LP relaxation solution found solutions that violate the same lazy constraint. The second heuristic might not have been aware of the lazy constraint generated for the first heuristic solution, which is why you had to add the same lazy constraint again.
Best regards,
Maliheh
0 -
A likely explanation could be that multiple heuristics applied to the same LP relaxation solution found solutions that violate the same lazy constraint.
Does this mean that disabling the Gurobi heuristic should prevent this behavior? My colleague and I, working on different problems, set the Heuristic parameter to 0.0 to disable the heuristic. However, we still observe the same behavior. Furthermore, we notice that redundant cuts only appear twice most of the time with lazy cuts, whereas they appear much more frequently with user cuts, which is expected in the latter case.
0 -
Does this mean that disabling the Gurobi heuristic should prevent this behavior?
Setting the Heuristics parameter to 0 only means that Gurobi does not devote meaningful work to finding feasible solutions. It still may occur that feasible solutions are encountered as part of the solving process.
I believe this might be a crucial factor affecting the algorithm's efficiency, as adding the same cut multiple times slows down the computations.
Adding the same lazy cuts multiple times should not be a performance bottleneck.
Maliheh
0 -
I would like to ask a similar issue about redundant cuts generated from the callback. In my case, the cuts are added under two scenarios, i.e., (1) when the solution is integral , i.e., if (where == GRB_CB_MIPSOL), and (2) when the solution is fractional, i.e., if (where == GRB_CB_MIPNODE && getIntInfo(GRB_CB_MIPNODE_STATUS)== GRB_OPTIMAL).
When I separate the cut in scenario (2) and add the cut using "addLazy", duplicated cuts are generated. I have tested the case where the cut is only added in scenario (1). There are no duplicated cuts in this case. It seems like the cuts are not directly added to the model just in scenario (2). I am aware of multi-threading, thus I have already set the thread into 1 by model.set(GRB_IntParam_Threads, 1). In addition, we initially used "addCut" in scenario (2). However, there are a larger number of duplicated cuts generated compared to the case when we use "addLazy", increasing the overall computational time because the separation routine is continuously being called due to the violations producing the same cuts. Therefore, addLazy is used instead of addCut in this case.
is this also a common behavior from Gurobi?
0
Please sign in to leave a comment.
Comments
7 comments