Iteratively apply user cuts before leaving root node

回答済み

Lorenzo Moreschini

2025年05月02日 11:35

• 
• 
• 

I need to solve a MILP model that is essentially a Travelling Salesman Problem with additional constraints.
As the core model is a TSP, most of the complexity is related to tightening the initial relaxation via subtour elimination constraints. To this aim, I would like to achieve the following:

1) Solve the root node.
2) In a callback, solve a maximum flow problem using the relaxed values in the optimal solution of the root node to identify violated connectivity constraints.
3) If at least one violated constraint is found, apply the violated constraints (using addLazy() provided by the Java API) and go to 1, otherwise start exploring the B&B tree.

In my experiments, it seems that Gurobi only allow me to solve the max flow problem once or twice before moving to open new nodes in the B&B tree, even when in the last iteration I did found violated constraints and loaded them.

Is there a way to control when Gurobi is allowed to leave the root node?

I have seen that similar questions have already been issued here https://support.gurobi.com/hc/en-us/community/posts/360077922231-same-LP-solution-multiple-times-in-root-node-user-cuts-ignored (unanswered) and here https://support.gurobi.com/hc/en-us/community/posts/21803422023953-Cuts-Parameter-and-B-B-Root-Node-User-Cuts (where they suggest as a workaround to set NodeLimit=1 to stay in the root node), yet both questions are quite old.

Is there a recommended way to achieve what I need?

関連

• Lazy Constraints
• MIP
• Callbacks
• Root Node

0

• 

  Riley Clement

  • Gurobi Staff

  2025年05月05日 01:37

  Hi Lorenzo,

  Unfortunately I don't think the NodeLimit=1 approach will work (and I suggested it).  I think we will just see termination of the solve where we would have otherwise seen branching.

  At the root node we run heuristics, add cuts, and can branch.  If you increase the effort of heuristics and cuts then you may be able to delay the branching, but ultimately there is not the level of control you are after.

  I would try experimenting with these parameters Heuristics, Cuts, CutPasses, perhaps first trying with Heuristics=0.5, CutPasses=2000000000 to see what difference it makes.  Note that this does not mean that Gurobi will do 2 billion cut passes but at least removes this an obstacle.

  - Riley

  0
• 

  Lorenzo Moreschini

  2025年05月06日 08:45 編集済み

  • 
  • 
  • 

  Thank you, I will try to experiment with those parameters.

  0

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