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

  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

Please sign in to leave a comment.