I was wondering how the run time of an LP and an MILP model compare to each other. I found out that MIPs are NP-hard, where as LPs aren't, but it don't really understand what it means.
Does that mean that LPs can be solved faster than MIPs? And how does the runtime of MIPs increase with size? Exponentially?
At the risk of offending someone by oversimplifying, NP-hard basically means that the amount of time to solve a model instance can grow faster than any polynomial function of the model size (number of variables, number of constraints, magnitude of coefficients etc.). In and of itself, it's not particularly germane to your question.
The simple answer is that an LP is usually going to be faster than the same model with some or all variables restricted to integers because the solver will typically first solve the LP relaxation (the model without integrality, i.e., the LP to which we are comparing it) and then do a bunch of additional work. In some cases you get lucky and the LP solution satisfies the integrality conditions, in which case they take the same amount of time. The MIP version is very unlikely to be faster to solve than the LP, the rare exception being when the integrality conditions let the presolver solve the model before any pivoting takes place.
Note that I'm comparing the same model with and without integrality. You can certain find a trivial MIP that solves faster than a ginormous LP.
