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
Please sign in to leave a comment.