Usercut callback via python : repeated cut

回答済み

Yilu LONG

• 2025年01月22日 15:01

Hello everyone,

I am currently solving a MIP problem using Gurobi, and in my MIPNODE callback, I generate and add cuts at the root node whenever I detect that the current relaxed solution violates certain constraints. According to my log files, after adding a cut that is violated by the current relaxed solution, Gurobi proceeds to find a new relaxed solution—yet I often identify the same cut as still being violated by that new solution.

I find this behavior puzzling, because I assumed that once a cut was added, any solution violating that cut would be excluded from the feasible region. However, the log suggests that subsequent relaxed solutions can still violate the same cut.

My question is: Is this behavior expected in Gurobi’s branch-and-cut procedure—i.e., does Gurobi sometimes revisit solutions that technically violate previously added cuts—or is there a particular detail in how I am adding cuts in the callback that might explain why these solutions reappear? I have included portions of my callback code and relevant log outputs below for reference.

Thank you very much for any insights or suggestions!

関連

• Cuts

0

• 

  Riley Clement

  Gurobi Staff

  • 2025年01月24日 04:31

  Hi Yilu,

  I think a similar question was asked here last year.  Please take a look at the following post:

  https://support.gurobi.com/hc/en-us/community/posts/27095292925969/comments/27140622551825

  - Riley

  0
• 

  Yilu LONG

  • 2025年02月11日 14:32

  

  

  Hi Mr. Riley,

  Thank you for suggesting the post to me. However, I think my case is different from the one in the post you referenced.

  In my situation, the cuts are user cuts, which I add within the callback using model.cbcut() under the MIPNODE, rather than using addLazyConstraints() in the MIPNODE.

  Additionally, as Mrs. Maliheh mentioned, "The capacity inequalities added via callbacks in your application are indeed lazy constraints because the model without them would be incorrect." However, in my case, the model remains correct even without adding these cuts. The cuts are simply introduced to speed up the optimization process, and they are only added when the current solution violates the cut.

  I hope this clarification helps. Thank you again for your support!

  Best regards,

  Yilu

  0
• 

  Riley Clement

  Gurobi Staff

  • 2025年02月12日 06:33

  Hi Yilu,

  The mechanisms behind cuts and lazy constraints are almost identical so the explanations in that post and others linked from it generalize to user 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

   

  multiple heuristics applied to the same LP relaxation solution found solutions that violate the same [user cut]. The second heuristic might not have been aware of the [user cut] generated for the first heuristic solution, which is why you had to add the same [user cut] again.

   

  Due to multi-threading and the time it takes for newly added [user cuts] to sync among all threads, you might encounter solutions that violate previously added [user cuts].

  If there's anything you still think is missing then let me know.

  Kind Regards,
  Riley

  0

サインインしてコメントを残してください。