What is root relaxation in MILP models?

回答済み

Krypt

2023年11月22日 20:13

• 
• 
• 

When I see the log of my milp model I see the following line appears:

Root relaxation: objective 2.551315e+03, 541 iterations, 0.01 seconds (0.01 work units)

What does this mean? How is it different from the LP relaxation? Or are they the same?

関連

• Branch-and-Cut

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:34

  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.
• 

  Mario Ruthmair

  • Gurobi Staff

  2023年11月23日 18:13

  Hi,

  For a MILP, the root relaxation is the LP relaxation at the root node of the branch-and-bound tree, i.e., the first LP relaxation that is solved after presolving.

  Best regards,
  Mario

  0
• 

  Tobia Marcucci

  2025年09月18日 22:11

  • 
  • 

  Hello,
  
  What about a convex MIQP? I am solving an MIQP and that line of the log says
  
  Root relaxation: objective 1.406271e-02, 2275 iterations, 0.07 seconds (0.08 work units)
  
  However, if I set all the binary variables to be continuous instead, I get a convex program whose optimal value is  29.3.

  On a similar note, the convex relaxation takes 0.23 seconds to solve, while the MIQP log after 8 seconds still says

      Nodes    |    Current Node    |     Objective Bounds      |     Work
  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
  0     0   29.13175    0  129          -   29.13175      -     -    8s
  
  So it seems that it has not started the branch and bound process yet, but is still working on solving the convex relaxation. Any suggestions to speed up the solution of this MIQP?
  
  Thank you very much,

  Tobia

  0
• 

  Mario Ruthmair

  • Gurobi Staff

  2025年09月19日 06:20

  Hi Tobia,

  In most cases, the quadratic objective terms in an MIQP are linearized to convert it to an MILP. This can weaken the bound obtained from the continuous relaxation. This is probably what you observe in your run.

  You can control what is done with the quadratic terms with the parameters PreQLinearize and PreMIQCPForm (if Q-constraints are present).

  Mario

  1
• 

  Tobia Marcucci

  2025年09月19日 16:37

  • 
  • 

  Hi Mario,

  Thank you for the quick response. Setting PreMIQCPForm to 1 or 2 solves the issue.

  Tobia

  0

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