When you have a weak LP relaxation, or a hard LP problem that needs to be solved for your MIP problem, solving the problem can take a long time.
There are several reasons why the MIP algorithm can take a long time. Some of them are:
- The MIP solver cannot handle this math program very well.
- The LP relaxation is very weak and therefore there are only a few cuts in the branch-and-bound tree.
- Solving the LP problems is relatively hard.
- If the branch-and-bound tree becomes very large, the solver needs to swap memory, which decreases the performance drastically.