MIP faster than its relaxation
AnsweredHello,
I have a MIP model and its relaxed counterpart, and when running (1 thread each) them the MIP is always faster, is there any explanation for this behavior?
I keep both models and over a number of iterations I change the RHS of the same constraints for both models and reoptimize them, and on average the MIP takes 24.9s to solve while the relaxation takes 393.56s.
The model has integer flow constraints and knapsack constraints related to the established flow.
Could it be for the presolve on the MIP?
Here are snippets of the log for the first iteration of the MIP:

Yes, the difference is probably due to presolve. LP presolve isn't exactly the same as MIP presolve. On the LP:
Presolve removed 199711 rows and 197457 columns
Presolve time: 1.49s
Presolved: 62222 rows, 61266 columns, 252112 nonzerosOn the MIP, Gurobi reduces the model even further:
Presolve removed 223213 rows and 221193 columns
Presolve time: 7.64s
Presolved: 38720 rows, 37530 columns, 173928 nonzerosThe presolved LP model is ~50% larger than the presolved MIP model and takes awhile to solve. Meanwhile, Gurobi solves the root relaxation of the presolved MIP model fairly quickly, then finds a nearoptimal heuristic solution at the root node almost instantly. I agree this behavior is strange, but it makes sense when considering the size differences of the presolved models.1 
Thanks for the answer Eli!
0
Please sign in to leave a comment.
Comments
2 comments