The same LP-relaxation and root node relaxation

Awaiting user input

Saeedeh Ahmadi Basir

• January 22, 2024 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.

 

Related to

• Cuts
• Branch-and-Cut

0

• 

  Michel Soares

  • January 22, 2024 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

  • January 23, 2024 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

  • January 23, 2024 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

  • January 29, 2024 13:09

  

  

  

  Thank you very much. 

  0

Please sign in to leave a comment.