CPLEX is the first choice for solving large difficult models in mission-critical applications where robustness and reliability are important. Few solvers can come close to match CPLEX's speed and reliability. CPLEX is currently used to solve many of the largest problems in the world, with up to millions of variables, constraints, and non-zeros.

Algorithmic Features

CPLEX has a number of sophisticated features that drastically improve solving performance, these include: sophisticated problem preprocessing, efficient restarts form an advanced basis, sensitivity analysis, infeasibilty finder to mention a few.

Linear Programming

CPLEX has an arsenal of methodologies to solve LP problems, typically the best approach is CPLEX's dual simplex algorithm for the majority of problems. There are certain types of problems that may benefit from CPLEX's primal simplex algorithm. CPLEX also encompasses an interior point method, its Barrier algorithm which provides an alternative to the simplex method for solving linear problems, it is based on a primal-dual predictor-corrector method. The barrier algorithm is generally considered when used to solve large problems or if the problems may have numerical instability issues. There is also an efficient network simplex method that is effective in solving network models.

Quadratic Programming

CPLEX can solve models that have a quadratic objective function and linear constraints. If the objective function is positive semi-definite it can utilize any of the LP methods. To solve QPs in MPL by CPLEX one has to set in MPL the "ModelType" to Quadratic.

Mixed Integer Programming

CPLEX Mixed Integer Optimizer provides the capability to solve problems with mixed-integer variables (general or binary). It utilizes state-of-the art algorithms and techniques. CPLEX principally uses a branch and cut algorithm that essentially solves a series of relaxed LP subproblems. Addition of cuts and sophisticated branching strategies can be employed at these subproblems to try to find the optimal solution more effectively. CPLEX also have heuristics that can aid in finding initial good solutions, it also includes a sophisticated mixed integer preprocessing system. One can even solve large and difficult integer problems quickly and efficiently.

Performance Tuning

For LPs

CPLEX is tuned to solve the vast majority of LP problems using the default options. There are occasions where one may need to change the option settings, these are usually a result of bad performance or numerical instability issues. On the whole the dual simplex method is best for most LP problems, there are some instances where the primal simplex may work best. The barrier method typically should be used for very large sparse models or models that are experiencing numerical difficulties. The sifting algorithm is a simple form of column generation well suited for models where the number of variables dramatically exceeds the number of constraints. Bad performance on LPs is using a result of degeneracy, which can be identified by examining the iteration log, having long sequences of iterations where the objective value remains unchanged. Perturbations can help speed up performance on degenerate problems. Degeneracy is not an issue for the barrier method, thus highly degenerate problems one should use the barrier algorithm to solve the LP.

For MIPs

MIP problems can be extremely difficult to solve, though there are no steadfast rules on enhancing MIP performance, certain things may be advantageous in improving the performance on some models and be a hinderous on other problems. Below are some of the considerations one should look into when try to solve difficult MIP problems:

• Priority orders:Assign higher priority to the integer variables that should be decided earlier, these tend to represent decisions that are strategic or activate processes. The order, the variables are defined in MPL indicates the MIP priority, earlier the definition the higher the priority.

• Cutoffs: Setting cutoff values can greatly speedup the process, the cuttoff value (known value that is equal or worse than the true optimal value) maybe attained from some heuristic algorithms to the same problem or a previous uncompleted run of the MIP model. Use "MipUpperCutoff" to set upper cutoff value for minimization problems, and set "MipLowerCutoff" value for maximization problems.

• Probing: This looks at the logical implications of fixing binary variables, which happens after presolve but before branch and bound. CPLEX has 3 levels of probing, there is a trade off factor here that though more intensive probing can derive good results it can also take some time to complete the probing. For large difficult problems, we suggest using level 3 or 2 since time overhead of probing is more likely to be paid back over long running time of branch and bound.

• Variable Selection: Selecting which variable to branch on can have considerable benefits. In difficult models "Strong Branching" or "Pseudo reduced costs" may be helpful. Both methods especially strong branching invest considerable effort in analyzing potential branches in hope of drastically reducing the number of nodes that will be explored.

• Cuts: Adding cuts are one of the principal reasons of recent dramatic increases in MIP performance. The cuts can dramatically increase the best bound and remove otherwise sub-optimal branches in the tree. The more cuts added, the larger the inherent matrix becomes which can increase the processing time at the nodes. However usually on difficult models an aggressive cut strategy is the best mode of practice.

For more information about CPLEX, please visit IBM CPLEX Optimizer web page.