Does the barrier method for LP automatically start from the dual problem?
AnsweredDear 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

Official comment
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 nonfull 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,

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.
Comments
2 comments