2
$\begingroup$

I'm solving a MILP model whose native lower bound (via linear relaxation) is very poor. We could provide a lower bound by providing a given value (derived based on the problem itself). I know that directly adding a numerical lower bound on the objective may do no good (sometimes it leads to a worse case by misleading the search procedure). I tried both cases: with and without the numeric lower bound. However, in neither case, CPLEX finds the optimal solution in more than ten hours with out of memory.

My problem is what makes my specific model so hard to solve?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ Without any information on your model, the only answer is : "because probably, $P\neq NP$. If you write down the model, it would help. $\endgroup$ – Kuifje Sep 25 '20 at 9:24
  • 1
    $\begingroup$ For a MIP, out of memory exceptions typically happen when the tree size becomes very large. If your LP relaxation is weak, then intuitively your model may become easier if you can figure out how to strengthen that. Beyond that I agree with @Kuifje: without the specifics it's impossible to say. $\endgroup$ – Richard Sep 25 '20 at 9:44
  • $\begingroup$ @Kuifje Thanks for you reply! I planned to upload the mps file of my problem, but cannot figure out how to upload it... $\endgroup$ – John Von Sep 25 '20 at 15:15
  • $\begingroup$ @Richard Yes, the LP relaxation is very poor, maybe I need try to strengthen it as you suggests. Thanks for your reply. $\endgroup$ – John Von Sep 25 '20 at 15:16
10
$\begingroup$

MILPs are NP-hard. People make a big deal about NP-hardness for a reason - in the worst case they are very, very hard to solve.

There is a short, easy to understand exposition of this by @Johan Löfberg : Why is my MILP not finishing

Johan provides an example: For a MILP with 72 binary variables, in the worst case, a MILP solver will have to solve $2^{72}$ continuous LPs (MILP relaxations). That is $4.2 *10^{21}$ LPs to solve in the worst case. If 10,000 LPs are solved per second, that would require the age of the universe (since the big bang).

So consider yourself fortunate when a MILP solver does better than this worst case, which is not that infrequently, otherwise MILP solver vendors wouldn't get many paying customers.

Put another way. MILPs are hard to solve in general. Some MILPs wind up not being so hard to solve, but it is often not easy to predict which will be which.

Improve this answer
$\endgroup$
5
$\begingroup$

Solver-related comments below are specific to CPLEX but may apply to some other solvers.

First comment: Out of memory errors can be postponed (by tweaking the parameter settings for swapping stuff out to disk) or possibly eliminated (by switching to depth-first search). Neither guarantees the optimum will be found within your lifetime.

Second comment: If you have not already done so, you might try switching the MIP emphasis from its default setting to the setting that stressed tightening the best bound. In addition, there are a variety of settings that can be tweaked to increase the use of various cuts (which may or may not help), or to use strong branching (which may or may not help). Switching emphasis changes some of those for you (I think), but I couldn't say which ones.

Third comment: You might want to look at an excellent paper by Klotz and Newman titled "Practical Guidelines for Solving Difficult Mixed Integer Linear Programs" (Surveys in Operations Research and Management Science, 2013, 18, 18-32). There's a proof (PDF) on Alexandra Newman's web site.

Fourth comment: Some formulations are known to be weak. A classic example is a "big M" model with a, well, big "M". If you can tighten your formulation, that should be your first choice. Unfortunately, tighter formulations are not always easy to find.

Improve this answer
$\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.