Skip to main content

Linear Program is slower than Integer Linear Program

Answered

Comments

3 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Neha,

    It is correct that in general solving LPs is faster than solving ILPs. However, Gurobi comes with a huge bag of tricks for ILPs of which not all are applicable to LPs. Thus, it is possible that by exploiting some integer properties, Gurobi is able to solve an ILP faster than its continuous relaxation.

    Please note that (I)LPs that are solved so quickly (~2s in your example) are not a good measure for a statement about performance of LP vs ILP due to the possible integer exploitation. It is also possible that the continuous relaxation of the ILP is numerically troublesome while the continuous relaxation after exploiting some integer properties in presolve may be OK.

    Best regards, 
    Jaromił

    1
  • Neha Makhija
    First Comment
    Gurobi-versary
    First Question

    Hi Jaromil,

    Thanks for your very informative response. This is helpful! Some follow-up questions:
    1. Could you give some examples of tricks for ILPs of which not all are applicable to LPs?

    2. What does "numerically troublesome" mean in the context of solving an LP?

    You are right that perhaps 2s is not significant, I tried the same with larger examples and see similar instances, so am curious.

    Thanks!

    Neha

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Neha,

    Could you give some examples of tricks for ILPs of which not all are applicable to LPs?

    Most of those are well described in Presolve reductions in Mixed Integer Programming by Achterberg et al.

    What does "numerically troublesome" mean in the context of solving an LP?

    You can find a good description of what "numerically troublesome" means in our Guidelines for Numerical Issues.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.