Does the barrier method for LP automatically start from the dual problem?

Answered

Bo Yang

April 30, 2021 06:17

• 
• 
• 

Dear Sir/Madam,

I have a question on how Gurobi solve the LP with barrier method. My LP has much more constraints than the variables. That is, the m by n coefficient matrix A has m>>n. So in the barrier method, it seems much cheaper to solve the dual instead of the primal because A^TA in the dual is smaller than AA^T in the primal.  Does Gurobi automatically detect the dimension of A and start from the dual LP? Thanks for your help in advance.

Best,

Bo

0

• Official comment

  

  Yuriy Zinchenko

  • Gurobi Staff

  May 03, 2021 15:12

  Hello Bo:

   

  we do apply dual transformation automatically (in some cases), specifically, indeed, when A is "long and narrow" we would look into that with the code. In other words, the matrix "aspect ratio" (m/n) is one of the main problem statistics we look at when deciding if it is worth solving the dual instead of the primal.  

  Regarding the full rank, we do not require this, but generally speaking non-full rank in A may lead to some numerical issues (very rare).  If you can make sure the matrix is full rank, this would not hurt.

   

  Hope this helps,
• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 02:55 Edited

  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 why not try our AI Gurobot?.
• 

  Bo Yang

  May 01, 2021 20:21

  • 
  • 
  • 

  I also want to ask if the matrix A is full column rank (given m>>n), would Gurobi benefit from this condition? Thank you for your answer.

  0

Post is closed for comments.