ILOG CPLEX finds the primal solutions, conventionally denoted (x, s), from the primal formulation:

with these bounds x + s = u and x l

Its performance is most dependent on these characteristics:

- the number of floating-point operations required to compute the Cholesky factor;
- the presence of dense columns, that is, columns with a relatively high number of nonzero entries.

To decide whether to use the barrier optimizer on a given problem, you should look at both these characteristics. (We explain how to check those characteristics later in this chapter in *"Cholesky Factor in the Log File"* , and *"Nonzeros in Lower Triangle of AAT in the Log File"* ).

Since many users prefer basic solutions because they can be used to restart simplex optimization, the ILOG CPLEX Barrier Optimizer includes basis crossover algorithms. By default, the barrier optimizer automatically invokes a primal crossover when the barrier algorithm terminates (unless termination occurs abnormally because of insufficient memory or numerical difficulties). Optionally, you can also execute barrier optimization with a dual crossover or with no crossover at all. The section *"Controlling Crossover"* explains how to control crossover in the Interactive Optimizer.

- The fact that barrier without crossover does not produce a basic solution has other consequences. Without a basis, you will not be able to optimize the same or similar problems repeatedly using advanced start information. You will also not be able to obtain range information for performing sensitivity analysis.

- Simplex and barrier optimizers have different numerical properties, sensitivity, and behavior. For example, the barrier optimizer is sensitive to the presence of unbounded optimal faces, whereas the simplex optimizers are not. As a result, problems that are numerically difficult for one method may be easier to solve by the other.
- Simplex and barrier optimizers have different memory requirements. Depending on the size of the Cholesky factor, the barrier optimizer can require significantly more memory than the simplex optimizers.
- Simplex and barrier optimizers work well on different types of problems. The barrier optimizer works well on problems where the AAT remains sparse. Also, highly degenerate problems that pose difficulties for the primal or dual simplex optimizers may be solved quickly by the barrier optimizer. In contrast, the simplex optimizers will probably perform better on problems where the AAT and the resulting Cholesky factor are relatively dense, though it is sometimes difficult to predict from the dimensions of the model when this will be the case.