Optimising the current model

Question

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.

Answer 1

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.

Answer 2

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!!!).