Problem characteristics affecting CPLEX run time

• 
  
• 
  
• 
  
• 
  
• 
  
• 
  
• 
  
• 
  

Technote (FAQ)

Question

How much time will CPLEX need to solve my problem?

Answer

Several factors affect how much time a given CPLEX algorithm will take to complete:

• The size of the problem: For a given class of problems, it is generally the case that execution time increases when the number of variables and/or constraints increases. The size of the problem alone can be misleading, however: CPLEX has solved Mixed Integer Programming (MIP) problems with hundreds of thousands of variables and constraints in a matter of minutes; on the other hand, there exist small MIP problems with a few hundred variables that neither CPLEX nor any other solvers have (yet) solved. Solving Linear Programming (LP) problems is usually more predictable, with the execution time more strongly correlated with the number of constraints than with the number of variables.
• The characteristics of the model: At a basic level, a model with binary and integer variables is more difficult to solve than a model that has only continuous variables. Most problems, however, can be modeled in a number of different ways, and the choice of model greatly affects the ability to solve it. There are many useful references about this topic in the Mathematical Progamming literature. It is worth noting here that eliminating symmetry from a model makes it easier to solve. Refer to this FAQ for details about that topic.
• The numerical characteristics of the data: CPLEX can encounter numerical difficulties while solving some problems due to the nature of the problem data. One effect of these difficulties is a slowdown in the search algorithms. The User's Manual contains sections about how to deal with numerical difficulties, and this FAQ has more information about how data can make a model more difficult to solve.
• The CPLEX algorithm used: There is a choice of algorithms for solving LP problems, and the execution time will depend on the selected algorithm. Refer to this FAQ and to the User's Manual for hints about how to select a suitable algorithm. For MIP problems, similar principles apply to selecting the algorithm used to solve the LP subproblems.
• The CPLEX parameters settings: The default parameter settings work well for most problems. However, some problems benefit from parameter tuning. The CPLEX User's Manual provides a section about parameter tuning for each solving algorithm. In particular, for MIP problems, the parameters that set absolute and relative gaps should be set carefully. They define the desired level of optimality of the "solution".
• The hardware used: The most important factor in hardware is processor speed in integer and floating point computations. One way to gauge that is through the SPECMARK web site at http://www.specbench.org. Other factors also play a role in hardware, but these are more difficult to track.

Other than those general statements, it is very difficult to tell how long a given problem will take to solve before actually trying to solve it. The mathematical programming literature contains, in most cases, reports about execution times for specific algorithms used on specific problem formulations. While these can be useful as a general guideline for common problems, it is hard to draw generalizations from those numbers.

Cross Reference information

Segment	Product	Component	Platform	Version	Edition
Business Integration	IBM ILOG CPLEX Optimization Studio	General	AIX, HP-UX, Linux, Solaris, Windows, Mac OS	12.2	All Editions

Historical Number

cplex/FAQ/123