I'm building a mixed-integer programming model, and the solver is experiencing a very long run time. So I tried to solve the LP relaxation to the MIP, and I get a similarly long solve time, which surprises me. I was wondering what might make an LP take a long time to solve, without any integrality constraints.
If solving the LP relaxation is taking as much time as solving the corresponding MILP formulation to optimality, I would assume one of two things:
1) Most of the work done by the MILP solver consists of solving the LP relaxation. Solving the LP relaxation is usually a step to solve any MILP with a general-purpose solver. In other words, there is probably no branching going on and preprocessing is not taking much time. That also means that the solution of the LP relaxation satisfies the integrality of the binary variables, which is often a good thing. However, if it is taking too long, I would assume that the formulation is too large. In such case, I would wonder if it would be possible to formulate the problem in a different way, in which the LP formulation is not as strong and probably the solution does not satisfy the integrality of some variables, but that allows you to solve the problem faster either by relying on the solver or implementing your own strategies on top of it. For example, problems with a lot of symmetry might be solved faster with orbital branching than with a formulation having lots of symmetry-breaking constraints. It could also be the case that your current formulation is actually very good, but you are solving problems that are too big.
2) Another possibility is that the MILP solver is spending a lot of time in preprocessing, for example by removing redundant rows and simplifying your formulation. In that case, the fact that solving the LP and the MILP takes the same time is more of a coincidence, and you should probably be able to improve your formulation in order to avoid a lengthy preprocessing step.
You can probably check if either of these cases is happening by looking at the solver output while solving your MILP formulation. For a more specific answer, we would need to know what is the formulation that you are trying to solve, how big are the inputs, and what the solver is reporting to you during the process.
If LP takes a long time to solve, you can check a couple of things:
1) How large is the problem? Large LPs (>1 million variables/constraints on a ballpark) can take a long time.
2) How large is the range of coefficients in the objective function and constraints? Having a large range of the coefficients typically hurts computational performance.