6
$\begingroup$

After developing the MIP model I noticed that solver is taking a lot of time to reach the solution. So, how should I approach to optimize the current model?

Are there any visualization tools or any tools that are helpful in optimizing the model.

$\endgroup$
  • 2
    $\begingroup$ For starters, read "Why is my MILP not finishing" by Johan Lofberg (developer of YALMIP) yalmip.github.io/slowmilp $\endgroup$ – Mark L. Stone Jan 29 '20 at 19:51
  • $\begingroup$ Which solver are you using? $\endgroup$ – Dipayan Banerjee Jan 29 '20 at 20:13
  • $\begingroup$ python pulp solver $\endgroup$ – ooo Jan 29 '20 at 20:23
  • 2
    $\begingroup$ Are you using PULP_CBC_CMD, or some other solver, under PuLP and if so, which one? $\endgroup$ – Mark L. Stone Jan 29 '20 at 21:42
  • 2
    $\begingroup$ It seems you're solving your model using an open-source solver (cbc). If you have access to some commercial solvers such as gurobi or cplex, I'd suggest you try solving your model with them as well. This can be very common that some larger models take much longer times to be solved with open-source solvers. $\endgroup$ – EhsanK Jan 30 '20 at 6:25
5
$\begingroup$

Assuming that your problem is not taking too long simply because it's too large, the most likely reason is that your formulation is not strong enough.

Tools

The best tool is the output of the solver itself. You want to monitor the behaviour of your lower and upper bounds, the size of the branching pool, the time between iterations, whether a feasible solution has been found, and how long it takes to find the first one.

Diagnosis

If the solver can't close the gap

The greatest indicator of a weak formulation is that your solver is generating too many nodes which are not fathomed and remain in the branching pool. This typically results in the MIP gap improving very slowly.

If the gap is improving slowly, a likely reason is degeneracy in your problem (multiple/infinite global solutions). This would either manifest as your solver exploring too many nodes, or the number of nodes in your branching pool remaining roughly constant and your MIP gap not really improving much.

Another reason could be that the bounds of your continuous variables (if you have any) are too large.

If the lower bound improves quickly and then stops

This would behave identically to the previous case if your solver has found a feasible solution. If it hasn't however, it might be the case that it's taking too long either because (a) your problem is infeasible and it's trying to prove it, or (b) because it's having trouble finding an integer solution.

Another reason could be that your solver can find some primal solution fairly easily, but has trouble finding better ones, which would cause it to run forever even if the lower bound is exact.

If each iteration is taking too long

Best explanation is that your problem is too large, your computer is too slow, or you don't have enough RAM and the solver is forced to access your swap memory, which makes it much slower.

If none of the above apply, and your solver is taking much longer to iterate than you think it should, it's probably having trouble factorising the coefficient matrix.

Possible fixes

  • Identify and break symmetry in your model.
  • Make sure there are no free variables.
  • Make sure all your variables have bounds.
  • Tighten the bounds of as many continuous variables as you can.
  • Apply presolving techniques to reduce problem & domain size if you have access to a solver with a good presolver (e.g., GUROBI, CPLEX, or our own Octeract Engine). You can also code these techniques yourself if you are up for it, a good reference can be found here.
  • If the issue is primal feasibility, relax/reformulate some of your integer constraints to make it easier for the solver to find feasible points, or instruct the solver to use a different primal heuristic.
  • Although solvers (especially commercial ones) are typically smart enough to figure out branching on their own, in edge cases the default branching heuristic might not be a good fit for your problem. Try changing the variable selection strategy if your solver supports it.
  • If your solver is generating too many nodes, try increasing the number of strong branching passes and depth.
  • If iterations are slower than expected, try making your problem more sparse, switching to interior point instead of dual simplex (or vice versa), or instructing the solver to use a different factorisation algorithm/library if it supports it.
  • Try scaling your coefficients to avoid numerical issues, especially if you are not using a commercial solver.
$\endgroup$
  • $\begingroup$ Most commerical solvers can benefit form improved scaling, even if they are more robust and can better handle poor scaling than less sophisticated non-commercial solvers. There are many instances of improved scaling in the input data helping the performance and "correctness" of commercial solvers. $\endgroup$ – Mark L. Stone Jan 30 '20 at 14:24
  • 1
    $\begingroup$ Good point, I rephrased. $\endgroup$ – Nikos Kazazakis Jan 30 '20 at 14:28
2
$\begingroup$

To add @ Mark L. Stone mentioned:

I recommended you could try solving your model using a small instance. (E.g. by reducing dimensions of the model's data.). If the model is solved optimality, you could pretty sure (with the large scale data), you would solve the model in an optimal sense.

To ensure that the solution is correct, you could solve the model using other solvers like CBC or GUROBI. To debug your model (if it was infeasible) you might write your model in an LP format and check it. (AFAIK, unfortunately, PuLp can not create LP format!!!).

$\endgroup$
  • $\begingroup$ I have checked my model with a small instance it is working optimally. The only problem is that it is taking time for a small instance also it takes like 3-4 min. $\endgroup$ – ooo Jan 30 '20 at 6:13
  • $\begingroup$ Maybe, your problem has had hard constraints or has had many integer variables even for a small instance. You could try using some tricks such as warm/MIP-start, using B&B gap control, the problem reformulation, combining them and ... to reduce solving time. (I have often used them). Indeed, if you are interested in the decomposition method, you would go ahead. But it needs some professional skills. I hope it will be useful. $\endgroup$ – A.Omidi Jan 30 '20 at 6:23
  • $\begingroup$ By "pulp cannot create LP format" are you referring to generating the .lp file from the model in pulp? If so, Pulp can create it. If not, it'd help a lot to clarify it in your answer. $\endgroup$ – EhsanK Jan 30 '20 at 6:23
  • $\begingroup$ Many thanks, @EhsanK for your advice. $\endgroup$ – A.Omidi Jan 30 '20 at 6:25

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.