Skip to main content

Linear Program is slower than Integer Linear Program

Answered

Comments

4 comments

  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    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.
  • Jaromił Najman
    • 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
    • Gurobi-versary
    • First Comment
    • 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

    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

Post is closed for comments.