Deciding which CPLEX's numerous linear programming algorithms for fastest performance

Answer

CPLEX by default uses the dual simplex method. Experimentation on a wide variety of linear programs has shown that it provides the best overall performance. So, first try CPLEX's default choice by using the 'optimize' command, CPXoptimize function, or IloCplex::solve function with no changes to the IloCplex::RootAlg parameter. If that doesn't yield satisfactory speed, take a closer look at the particular features of the model. While experimentation is the only way to determine the fastest algorithm, checking problems for particular characteristics frequently reveals the best optimization method. Below are some examples:

• The primal simplex method may outperform the dual simplex method on problems where the number of variables is dramatically larger than the number of constraints. This can occur because the dual simplex method requires full pricing, while the primal does not. Nonetheless, recent advances in the dual simplex method allow it to perform full pricing more effectively.
• Look for degeneracy in the primal and dual problems. If it is present in only one of the two problems, invoke a method that uses the other one to solve the problem. For example, if the problem is primal degenerate, try the dual simplex method.
• Barrier method performance frequently depends upon the structure of the constraint matrix. In particular, if the product of the constraint matrix and its transpose is sparse, the barrier method will probably outperform the simplex method.
• CPLEX can formulate the dual problem for optimization using the "presolve dual" parameter. Since the linear program optimization time depends more on the number of constraints than variables, problems with many more matrix rows than columns usually benefit from this parameter setting.
• Problems with a significant amount of network structure often benefit from using CPLEX's network optimization procedure. CPLEX will then finish the problem using the simplex method. This approach usually requires at least 90 percent of the model to be a network.
• The barrier method currently makes better use of multiple threads then any of CPLEX's other linear programming algorithms. So, when moving from serial machine to a parallel machine, reconsider the barrier method even if the simplex method outperformed it on running on only one thread.

Also, if your machine has multiple cores or processors, consider using the CPLEX's concurrent optimization feature, and let CPLEX decide for you by running multiple linear programming algorithms on different threads. CPLEX will stop the optimization as soon as one of the algorithms finishes with an optimal solution. Set CPLEX's lp method parameter (CPX_PARAM_LPMETHOD or IloCplex::Rootalg) to 6 to invoke concurrent optimization.