Can we add cuts to all nodes of the B&B tree based on an incumbent solution?

回答済み

Ramin Fakhimi

2022年08月24日 17:31 編集済み

• 
• 
• 

As I realized Gurobi cbCut function adds cuts to the current relaxed node. I want to add some cuts to every relaxed node in the B&B tree based on an incumbent solution. I wonder if this is possible and how.

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2025年11月16日 23:30

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Jaromił Najman

  • Gurobi Staff

  2022年08月25日 14:17

  It sounds like you are looking for user cuts and lazy constraints. Those special cuts can be added during the optimization process. You should refer to Gurobi's callback documenation. Moreover, the callback.py and tsp.py should be helpful. The webinar on implementing custom heuristics might also be helpful to get started with callbacks.

  Moreover, you should refer to the Knowledge Base articles

  • What is the difference between user cuts and lazy constraints?
  • How do I implement lazy constraints in Gurobi?

  Best regards, 
  Jaromił

   

  0
• 

  Ramin Fakhimi

  2022年08月25日 20:34 編集済み

  • 
  • 
  • 

  Thanks, Jaromił. Based on what I learned, Gurobi adds cuts only for children nodes of the current node in a B&B tree. However, what I am looking for is to add cuts for all nodes. I wonder whether this is possible or not. To be more specific. Let us assume I have a Big M constraint as $y \le M x$. I have a rough estimate for the value of M. Whenever I find a better incumbent in the B&B tree; I can reduce the value of M and improve that constraint. We can consider it as a new cut to the model.

  0
• 

  Jaromił Najman

  • Gurobi Staff

  2022年08月26日 07:00 編集済み

  Gurobi adds cuts only for children nodes of the current node in a B&B tree. 

  This is not correct. Gurobi puts the cuts into a so called cut pool and uses them just as normal cuts. If you take lazy constraints for the TSP model as an example. You could theoretically explicitly add all subtour constraints to your model before solving it (thus, they have to hold for all nodes of the B&B tree). However, there are exponentially many of them so your model size would explode. Through lazy constraints, one can control to only add the significant constraints to the model.

  Let us assume I have a Big M constraint as $y \le M x$. I have a rough estimate for the value of M. Whenever I find a better incumbent in the B&B tree; I can reduce the value of M and improve that constraint. We can consider it as a new cut to the model.

  Here, you have to check whether tightening of your constraint cuts off any feasible solutions. If yes, then you should add this constraint as a lazy constraint and not as a user cut, cf. What is the difference between user cuts and lazy constraints?

  0

投稿コメントは受け付けていません。