Linear Program is slower than Integer Linear Program

Answered

Neha Makhija

December 08, 2022 20:51 Edited

• 
• 
• 

Hi,

I am measuring the solve time of a set of problems vs their LP optimizations. For some cases the relaxations are optimal, others they are not. While in general I see that the ILP is exponential in size of the problem, and the Linear Program is polynomial in the size of data: there are cases where the ILP is faster than the LP, by a factor of 2 or 3!

I run an ILP and I run the same program with the only difference that variables are now continuous instead of binary. In multiple runs, it is always true that the LP takes more time than the ILP. Example:The LP took 2.1s, and the LP only 1.5s. I measure only the time to solve the problem, not to build.

As I understand it, the ILP solver uses a Linear Programming based branch and bound method that first solves the Linear Program and then performs subsequent search. So the ILP should always take more time than an LP.

I am accessing gurobi through the pulp interface

What am I missing? Thank you

Related to

• Numerics

0

• 

  Jaromił Najman

  • Gurobi Staff

  December 09, 2022 08:48

  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

  December 09, 2022 16:47

  • 
  • 
  • 

  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

  December 12, 2022 10:39

  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.