Duplicated cuts are generated during the callback
Answered
Hello,
As the title suggest, I face an issue in cut generation via callback in Gurobi. I and my supervisors are developing a branch-and-cut algorithm using Gurobi in c++ language to solve instances of Capacitated Vehicle Routing Problem. We perform a separation routine to obtain capacity cut(s) and those cuts are added via callback under two scenarios: (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 a common behavior or is there any possibility that there are bugs in our implementation?
-
Hi Panca,
It seems like the cuts are not directly added to the model just in scenario (2).
Despite lazy cuts, user cuts are not necessarily added to the LP relaxation immediately. They must first survive an internal Gurobi filtering process based on criteria such as orthogonality to other cuts, strength, and quantity. Therefore, it is not surprising that the same user cut is generated multiple times, as it may reside in Gurobi's internal cut pool without being incorporated into the LP relaxation
Is there any duplicate cut in scenario 2) if the cuts are added as lazy cuts and the Threads parameter is set to 1?
You might find the post "Ignored lazy constraint leads to wrong solution" relevant to your problem.
Best regards,
Maliheh
0 -
Hello Mrs. Maliheh,
I understand your explanation about the user cuts. Thank you.
To answer your question, yes. Duplicated cuts are still identified when I added them as lazy cuts in scenario (2) under the condition in which Thread parameter is set to 1. Note that I also set parameter GRB_IntParam_LazyConstraints to 1.
Based on the title of the post you suggested to me, I think I got a different case. In my case, the cuts are still eventually added to the model. The final solution that I obtain is correct (and surely feasible). The issue here is the cuts are not immediately added to the model when we called "addLazy" in scenario (2). Only in scenario (2) because we have performed the test on "addLazy" in scenario (1) and no duplicated cuts are found (which means the cuts are immediately added to the model).
So, do you have any idea why does this happen?
I could post my sourcecode and its associated results if further explanations are necessary.Best regards,
Panca
0 -
As explained in a similar post, duplicate lazy cuts in MIPSOL callbacks with Threads=1 can be explained. However, I do not expect to see duplicated lazy cuts in MIPNODE with Threads=1.
Please post a minimal reproducible example, and we would be happy to investigate this behaviour. Make sure the example is as concise as possible; reviewing your entire source code should be our last resort.
0 -
Hello Mrs. Maliheh,
Hereby I attached the sourcecode. there are three folders: code, instance, and summary. I have simplified the code yet there are a lot of classes that need to be included. These classes are part of a separation routine to generate the cuts. I will highlight only several classes to narrow down the scope.
There are only three classes are linked to Gurobi: ExactSvrp, ExactSvrpCallBacksGurobi, and ExactSvrpSepGurobi.
First of all, a generated cut is related to a subset of customers. The separation strategies are all coded in ExactSvrpSepGurobi class. In function "void SeperateCap(.)", we call function "CAPSEP_SeparateCapCuts(.)" to detect whether there is violation from at least a subset of customers. If such subset(s) of customers exist, then the associated cut(s) are generated. For debugging purpose, I created a vector of boolean values called "capCutNodesList" to store the subsets of customers associated to the generated cuts (line 167). All these cuts are then stored in a vector called "constraints" (line 169).
Then, we move to ExactSvrpCallBacksGurobi.cpp, all the constraints generated from functions in ExactSvrpSepGurobi are added using callback in this class inside function "void callback()". There are two main conditions as I explained in my previous code, i.e., (1) if (where == GRB_CB_MIPSOL) and (2) else if (where == GRB_CB_MIPNODE && getIntInfo(GRB_CB_MIPNODE_STATUS) == GRB_OPTIMAL). I use addLazy in both cases. I also recall that the problem happens in scenario (2). So, If we remove the whole code in scenario (2), no duplicated cuts are generated.
In ExactSvrp class, the model is created and Gurobi function "model.optimize()" is called. In order to show the duplicated cuts, I created function "void printDuplicatedSets(.)" in this class so that a txt file is generated to show how many cuts are generated and pairs of duplicated cuts found. The generated txt file will be stored in folder summary.
I solved one instance and the following picture is an example of the txt file. In this picture, there are 686 generated cuts and the list of pairs of cuts from the same set of customers.
I put two instances in folder instances so that you may also generated such txt files. The above picture is obtained from solving instance A-n32-k5.vrp. To run this code, I have provided the necessary files (CMakeLists.txt and FindGUROBI.cmake) which the original files are provided in Gurobi website. To run the program, I have provided all the commands in "myscript.sh". In this file, you may change the destination of txt file generated.
The folders and files are all stored in the following link:
https://drive.google.com/file/d/199rTj7-_L8B1VvaaXT2J5Ago2OkjxLOI/view?usp=sharing
If there are further questions, I will provide my response as soon as possible.
Thank you very much, Mrs. Maliheh.
Best regards,
Panca0 -
Hello Mrs. Maliheh,
Is there any update on the issue that I posted a few weeks ago? Are you able to reproduce the result? Do you need some help for the implementation? Please kindly let me know so that I could also help to show the redundant cut issue from the sourcecode I have already provided.
Best regards,
Panca
0 -
Hi Panca,
Please look for my response to the ticket created in our Help Center for this issue.
Best regards,
Maliheh
0 -
Hello Mrs. Maliheh,
I am sorry but I do not know which response do you refer to. Would you mind providing me the link to your response regarding this issue? I posted my issue in detail with the associated source code in response to your last reply. Then, I have not received any feedback from you related to the source code that I provided.
Thank you.Best regards,
Panca
0 -
I have sent a response to the email address associated with your Gurobi account. Could you please check your inbox and spam folder for an email from Gurobi Experts?
Maliheh
0 -
Hello Mrs. Maliheh,
I have not received any email yet. Would you mind sending it again to my another email: pancajodiawan@gmail.com . I am sorry for the inconvenience caused.
Best regards,
Panca
0 -
Hello Mrs. Maliheh,
I confirmed that I received the email from Gurobi Experts. Thank you.
Best regards,
Panca0 -
Yes, I saw it. We will be in touch through the ticket.
Best regards,
Maliheh
0 -
Hi Panca,
Our development team reviewed your case, and I’m writing to update you with their feedback:
The capacity inequalities added via callbacks in your application are indeed lazy constraints because the model without them would be incorrect.- Adding lazy constraints via MIPSOL callbacks to cut off integral solutions should suffice to obtain a correct optimal solution.
- Adding the constraints proactively via MIPNODE callbacks also makes sense. However, when these constraints are added via MIPNODE callbacks, they won't cut off the current fractional solution. Instead, they will cut the fractional solution once a violated integral solution is encountered. As a result, you may observe the same fractional solution again, requiring you to regenerate the same set of lazy constraints.
- Suppose all lazy constraints are added upfront by setting the Lazy attribute. In that case, you can control the level of aggressiveness these constraints are pulled into the model by setting the attribute to an integer value between 0 and 3. This feature is not available when lazy constraints are added via callbacks. Please take a look at the documentation of the Lazy attribute for more details.
- The Gurobi callback documentation notes: "Your callback should be prepared to cut off solutions that violate any of your lazy constraints, including those that have already been added. Node solutions will usually respect previously added lazy constraints, but not always." Parallelism is one reason for this behaviour, but other subtleties might necessitate adding the same lazy constraints multiple times, even if Threads=1 and Heuristics=0.
- With Threads=1, if a lazy constraint is added via MIPNODE, we believe you should not see the regeneration of this constraint in a later MIPSOL callback, but you might need to regenerate it in a later MIPNODE callback.
- With Threads=1, if a lazy constraint is added via a MIPSOL callback, you might need to regenerate it in a later MIPSOL callback even if Heuristics=0 because a few heuristics still run on the original model, where lazy constraints are not used.
In summary, regenerating the same lazy constraints multiple times is not a bug with Threads=1 and Heuristics=0.
Thanks for your patience and for sharing your code with us.
Best regards,
Maliheh0
Please sign in to leave a comment.
Comments
12 comments