Solving MIP problem takes a long time

AIMMS Knowledge Base Article - KB00007

Solving MIP problem takes a long time

Summary

When you have a weak LP relaxation, or a hard LP problem that needs to be solved for your MIP problem, solving the problem can take a long time.

Symptoms

The MIP algorithm takes a long time when it solves your math program.

Cause

There are several causes why the MIP algorithm can take a long time. Some of them are:

  • The MIP solver cannot handle this math program very well,

  • The LP relaxation is very weak and therefore there are only a few cuts in the branch-and-bound tree,

  • Solving the LP problems is relatively hard,

  • If the branch-and-bound tree becomes very large, the solver needs to swap memory, which decreases the performance drastically.

Resolution

You could try to run your model with a different MIP solver. For many MIP models CPLEX and GUROBI perform better than CBC and XA. If you already use CPLEX or GUROBI to solve your model, the following hints might help you.

If you have a weak LP-relaxation, you should look again at your model formulation. Maybe you can decrease the use of ‘Big M’ coefficients in your model, or maybe you can add some cuts.

If you have a very large LP that takes a relatively long time to solve, you could try to solve the LPs on the nodes using the Barrier algorithm. To do this, you should set the following option (menu: Settings – Project Options…):

        Specific solvers – CPLEX X.X - MIP - MIP Method -> Barrier

If your model includes natural priorities (because some decisions follow from or follow up other decisions), you could decide to make use of these priorities. More information about priorities can be found in the AIMMS Language Reference, chapter Variable and Constraint Declaration, section (x.1.1) The PRIORITY, NONVAR and RELAX STATUS attributes.

When you are able to create a good starting solution (e.g. using a heuristic), you can provide the solver with this solution to improve the solution process. Note that this is only possible when you use CPLEX, GUROBI or CBC. You need to set the following option (menu: Settings – Project Options…) to use the starting solution:

        CPLEX X.X: Specific solvers – CPLEX X.X - General - Advanced start -> Use advanced basis

        GUROBI X.X: Specific solvers – GUROBI X.X - MIP - MIP Start -> Yes

        CBC X.X: Specific solvers – CBC X.X - MIP - MIP Start -> On

More information

For more information, please contact us at support@aimms.com.