The same LP-relaxation and root node relaxation

ユーザーの入力を待っています。

Saeedeh Ahmadi Basir

2024年01月22日 08:47

• 
• 
• 

I used Gurobi to solve the periodic vehicle routing problem. In some instances, the values of the root node relaxation and LP-relaxation are the same. Does it mean that no cut is added to root node relaxation? Is there a way to count (not redundant) cuts that are added to root node relaxation? How can I prove the accuracy of these values?

To explain what I did,

First, I solved the original model.

model.optimize() ==> The root relaxation for the original model is 3.99.

Next, I solved the relaxed MILP using the model.relax() method:

model.reset()

model = model.relax()

model.optimize()   ==>  The optimal solution of the relaxed MILP is 3.99.

Then, I changed the variable types to GRB.CONTINUOUS and let Gurobi solve it. The optimal solution of the relaxed MILP is 3.99.

You can see that the root relaxation did not provide a tighter solution than the relaxed MILP.

Then, I turned off the presolve routine and solved as follows:

model.reset()

model.Params.PreSolve=0

model.optimize()

==> Solving without presolve gave me a root relaxation of 3.99. I saw that this also matches the relaxed MILP solution.

Next, I solved the relaxed presolve model:

model.reset()

presolve_model = model.presolve() 

presolve_model = presolve_model.relax()

presolve_model.optimize()

The final solve gives an optimal objective of 3.99. This also matches our root relaxation from the original model.

 

関連

• Cuts
• Branch-and-Cut

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:31

  This post is more than two 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.
• 

  Michel Soares

  2024年01月22日 17:30

  • 
  • 

  Hi Saeedeh,

  The root node of a MIP is indeed the solution of the relaxed model. Indeed, there are many cuts that can be added in the root node to speed up finding a good integer solution. If you want to increase the number of cuts, you can specify the parameter Cuts = 3 and see the impact in the report of cuts used at the end of optimization and the different in the optimization time.

  0
• 

  Saeedeh Ahmadi Basir

  2024年01月23日 09:55

  • 
  • 
  • 

  Thank you for your response. My question is how can I count the number of cuts that are added in root node relaxation? I want to know the reason for the same root node relaxation and LP-relaxation. I checked the solution of the LP-relaxation. It is not an integer solution.

  0
• 

  Michel Soares

  2024年01月23日 11:35

  • 
  • 

  You can get the number of cuts added using callbacks. You can get the number of cuts added so far (MIP_CUTCNT) in a MIP node (MIPNODE and MIPNODE_NODCNT = 0): that should give you the number of cuts added in the root node.

  0
• 

  Saeedeh Ahmadi Basir

  2024年01月29日 13:09

  • 
  • 
  • 

  Thank you very much. 

  0

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