CPLEX Performance Tuning for Linear Programs

Answer

CPLEX has internal logic that enables it to examine a linear program (LP) and typically make good decisions regarding the best way to solve it.  As a result, CPLEX's default settings typically perform very well.  However, if you do need to improve CPLEX's performance on a linear program, here are some suggestions.   Refer to the CPLEX User Manual if you need additional information on any of the concepts mentioned, and refer to the CPLEX Parameters Reference Manual for more information on any of the individual parameters and their associated settings discussed below.

1.  Try each linear programming algorithm.
2.  Solving the dual problem may be faster.
3.  Check if degeneracy hampers performance.
4.  Check for numerical difficulties.
 

1.  Try each linear programming algorithm.
     While changing individual parameters rarely has a major impact on LP performance, CPLEX's algorithms can behave quite differently on  a problem. CPLEX can solve a linear program using the primal simplex method, the dual simplex method, the barrier method, and, in some cases, the network simplex method.  CPLEX also supports variants of these algorithms including sifting and concurrentopt. Sifting is a simple form of column generation well suited for models where the number of variables dramatically exceeds the number of constraints. Concurrentopt works with multiple processors, running a different algorithm on each processor and stopping as soon as one of them finds an optimal solution. Find out which algorithm works best on your particular problem if you need to improve performance.  The barrier method tends to work well on problems where the product of the constraint matrix multiplied by its transpose is sparse.

2.  Solving the dual problem may be faster.
    You can obtain the solution to a linear program either by solving the primal linear program itself, or solving the dual of the linear program and using the dual's dual variables to obtain the solution to the linear program.  If you set the presolve dual indicator on, CPLEX will do this for you by taking the dual problem, solving it, and returning solution values in the context of the primal problem.  Since the computation time for the simplex method depends more on the number of constraints than the number of variables, this approach is most likely to help on problems where the primal has more constraints than variables.  The dual will therefore have fewer constraints.  CPLEX will probably solve it faster than the primal., especially if you try each linear programming algorithm as mentioned above.

3.  Check if degeneracy hampers performance.
     Degeneracy can dramatically slow down the simplex method.  If a customer reports slow performance on a linear program, degeneracy is a likely cause. To verify this, check the CPLEX iteration log and look for long sequences of iterations where the objective value remains unchanged.   Also, look for messages that indicate CPLEX has to perturb the problem.  While perturbations help speed up performance on degenerate problems, using a different algorithm works better.  If the problem is primal degenerate, the dual simplex method may still work well.  If the problem is dual degenerate, the primal simplex may still work well.  If the problem is both primal and dual degenerate, the barrier method may work well.
 

4.  Check for numerical difficulties.
     A computer is a finite precision machine.  CPLEX's algorithms perform millions of floating point computations, and round off error can gradually accumulate.  CPLEX uses numerically stable methods to perform its linear algebra, so round off error usually does not cause problems.  However, if a problem is fundamentally ill conditioned, even the most stable methods may have trouble, either in terms of the accuracy of the final solution or simply the amount of time required to solve the problem.  Make good use of CPLEX's solution quality routines to determine if this is a problem.  From the Interactive CPLEX Optimizer, use the 'display solution quality' command.  Also, 'display solution kappa' will give the condition number of the current basis.  Condition numbers larger than 1e+10 suggest that the problem may be numerically unstable, and the potential for numerical difficulties increases as the condition number increases above this threshold.    From the CPLEX Callable Library, use the CPXgetdblquality and CPXgetkappa routines to obtain the corresponding information.  From Concert, use IloCplex::getQuality for solution quality.  Concert doesn't currently support a function to obtain the basis condition number.

    If you do find that numerical instability hampers performance, setting the Markowitz tolerance to a value of .9 (or in extreme cases to its maximum of .9999) may help.  Also, try setting CPLEX's scaling parameter to 1.  Users of CPLEX 10.0 and later can simply turn CPLEX's numerical caution emphasis parameter on to set these (and other) parameters all at once. Also, consider the feasibility and optimality tolerances.  The default values are 1e-6.  If your problem data is only accurate to a larger value (e.g. 1e-4), consider increasing the feasibility and optimality tolerance to the same level of accuracy as your data.