11
$\begingroup$

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.

$\endgroup$
5
  • 8
    $\begingroup$ Hi Yinan, welcome to OR.SE. I'm not sure whether you want information about your particular problem/model or seek answer to the more general question "examples for helpful LP-relaxations"? If the first is true, then please give some more information on your model (maybe even the precise formulas/constraints) and how exactly you tried to solve it. If the latter is true, then you should rephrase your question. $\endgroup$ – JakobS Jun 18 '19 at 7:51
  • $\begingroup$ Yinan, I edited your question based on how I interpreted it. Please see whether it's OK, and if not, feel free to edit it back. It would also be good if you can comment on the answers that have been posted so far to indicate whether they are answering the "right" question. $\endgroup$ – LarrySnyder610 Jun 18 '19 at 20:48
  • $\begingroup$ Two other questions: (1) What solver are you using? (2) Are you sure that the running time is coming from the solver, and not from the modeling language (AMPL, PuLP, whatever) in the process of building the model? $\endgroup$ – LarrySnyder610 Jun 18 '19 at 20:49
  • $\begingroup$ @Yinan, can you provide us with more details, ideally a log file? I expect that you can see that you have (or have not) numerical trouble with your model and/or a lot of degeneracy the solver cannot cope well with (do we see a lot of stalling etc.). $\endgroup$ – Marco Lübbecke Jun 18 '19 at 22:17
  • $\begingroup$ @LarrySnyder610 Hi Larry, thank you very much for editing it, it helps clarify my question. The solver I am using is gurobi, and I implemented the model by Matlab library Yalmip. $\endgroup$ – Yinan Jun 19 '19 at 3:43
14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Hi Thiago, Thank you very much for answering my question. It is very helpful. I think the second assumption would explain my concern. I'll test on other formulations and keep you posted. $\endgroup$ – Yinan Jun 19 '19 at 3:49
  • 1
    $\begingroup$ +1 for the preprocessing suggestion. I'd disable that first, as ill-conditioned problems tend to give solvers some headaches during preprocessing. $\endgroup$ – baudolino Jun 24 '19 at 18:31
7
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ I'd add 3) how dense is the problem? Size alone is not that big of a problem, if the constraint matrix is sparse. $\endgroup$ – Michael Feldmeier Jun 18 '19 at 17:25
4
$\begingroup$

Highly degenerate LP's can be very hard to solve using the simplex method and much easier to solve using an interior point method. It's possible that your LP relaxation has this issue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.