What is the correlation between problem size and solution time?

Overview

In general, there is no correlation between problem size and solution time with Gurobi. The time it takes Gurobi to find and prove an optimal solution depends on how well the algorithms are able to tackle the particular problem at hand.

It is often possible to identify such correlations for a particular model family, i.e., a set of models that originates from the same algebraic description but with different data.

An example

In the examples provided in the Gurobi distribution, there are two models of roughly similar size, glass4 and misc07. When solving these models using Gurobi 11.0 with default settings, the solve times differ by a factor of 20:

• glass4.mps with 396 rows, 322 columns, 1815 nonzeros: ~20 seconds
• misc07.mps with 212 rows, 260 columns, 8619 nonzeros: ~1 seconds

An exception: Reading a problem from file

If a problem is read in from a file (e.g., an MPS file), then this reading time will scale to a certain extent with the problem size, since all the data needs to be loaded into the Gurobi data structure in memory.

Further information

• Is there a way to predict how long it will take Gurobi to solve a MIP?
• Does using more threads make Gurobi faster?
• Are there performance differences amongst the different Gurobi APIs?
• Why does Gurobi perform differently on different machines?