As we noted in Differences between Barrier and Simplex Optimizers, the algorithms in the barrier optimizer have very different numerical properties from those in the simplex optimizer. While the barrier optimizer is often extremely fast, particularly on very large problems, numerical difficulties occasionally arise with it in certain classes of problems. For that reason, we recommend that you run simplex optimizers in conjunction with the barrier optimizer to verify solutions. At its default settings, the ILOG CPLEX Barrier Optimizer always crosses over after a barrier solution to a simplex optimizer, so this verification occurs automatically.

Understanding Solution Quality from the Barrier LP Optimizer lists the items that ILOG CPLEX displays about the quality of a barrier solution. If the ILOG CPLEX Barrier Optimizer terminates its work with a solution that does not meet your quality requirements, you can adjust parameters that influence the quality of a solution. Those adjustments affect the choice of ordering algorithm, the choice of barrier algorithm, the limit on barrier corrections, and the choice of starting-point heuristic-topics introduced in Tuning Barrier Optimizer Performance and recapitulated here in the following subsections.

As we explain about tuning performance in Choosing an Ordering Algorithm, you can choose one of several ordering algorithms to use in the ILOG CPLEX Barrier Optimizer. To improve the quality of a solution in some problems, change the ordering algorithm.

The ILOG CPLEX Barrier Optimizer implements the algorithms listed in Table 5.13. The selection of barrier algorithm is controlled by the BarAlg parameter. The default option invokes option 3 for LPs and QPs and option 1 for MIPs where the ILOG CPLEX Barrier Optimizer is used on the subproblems. Naturally, the default is the fastest for most problems, but it may not work well on problems that are primal infeasible or dual infeasible. Options 1 and 2 in the ILOG CPLEX Barrier Optimizer implement a barrier algorithm that also detects infeasibility. (They differ from each other in how they compute a starting point.) Though they are slower than the default option, in a problem demonstrating numerical difficulties, they may eliminate the numerical difficulties and thus improve the quality of the solution.

The default barrier algorithm in the ILOG CPLEX Barrier Optimizer computes an estimate of the maximum number of centering corrections that ILOG CPLEX should make on each iteration. You can see this computed value by setting barrier display level two, as explained in Interpreting the Barrier Log File, and checking the value of the parameter to limit corrections. (Its default value is -1.) If you see that the current value is 0 (zero), then you should experiment with greater settings. Setting the parameter BarMaxCor to a value greater than 0 may improve numerical performance, but there may also be an increase in computation time.

As we explained in Using a Starting-Point Heuristic, the default starting-point heuristic works well for most problems suitable to barrier optimization. But for a model that is exhibiting numerical difficulty it is possible that setting the BarStartAlg to select a different starting point will make a difference. However, if you are preprocessing your problem as dual (for example, in the Interactive Optimizer you issued the command set preprocessing dual), then a different starting-point heuristic may perform better than the default. To change the starting-point heuristic, see Table 5.12.

Numerical difficulties can degrade performance of the ILOG CPLEX Barrier Optimizer or even prevent convergence toward a solution. There are several possible sources of numerical difficulties:

• elimination of too many dense columns may cause numerical instability;
• tight convergence tolerance may aggravate small numerical inconsistencies in a problem;
• unbounded optimal faces may remain undetected and thus prevent convergence.

The following subsections offer guidance about overcoming those difficulties.

Detecting and Eliminating Dense Columns explains how to change parameters to encourage ILOG CPLEX to detect and eliminate as many dense columns as possible. However, in some problems, if ILOG CPLEX removes too many dense columns, it may cause numerical instability.

You can check how many dense columns ILOG CPLEX removes by looking at the preprocessing statistics at the beginning of the log file, as we explained in Preprocessing in the Log File. If you observe that the removal of too many dense columns results in numerical instability in your problem, then increase the column nonzeros parameter, BarColNz.

The default value of the column nonzeros parameter is 0 (zero); that value tells ILOG CPLEX to calculate the parameter automatically.

To see the current value of the column nonzeros parameter-either one you have set or one ILOG CPLEX has automatically calculated-you need to look at the level two display, by setting the BarDisplay parameter to 2.

If you determine that the current value of the column nonzeros parameter is inappropriate for your problem and thus tells ILOG CPLEX to remove too many dense columns, then you can increase the parameter BarColNz to keep the number of dense columns removed low.

If your problem contains small numerical inconsistencies, it may be difficult for the ILOG CPLEX Barrier Optimizer to achieve a satisfactory solution at the default setting of the complementarity convergence tolerance. In such a case, you should increase the BarEpComp parameter to a value greater than its default, 1e-8.

An unbounded optimal face occurs in an LP or QP that contains a sequence of optimal solutions, all with the same value for the objective function and unbounded variable values. The ILOG CPLEX Barrier Optimizer will fail to terminate normally if an undetected unbounded optimal face exists.

Normally, the ILOG CPLEX Barrier Optimizer uses its barrier growth parameter, BarGrowth, to detect such conditions. If this parameter is increased beyond its default value, the ILOG CPLEX Barrier Optimizer will be less likely to determine that the problem has an unbounded optimal face and more likely to encounter numerical difficulties.

Consequently, you should change the barrier growth parameter only if you find that the ILOG CPLEX Barrier Optimizer is terminating its work before it finds the true optimum because it has falsely detected an unbounded face.

The parameter BarVarUp determines an upper bound for all variables in the model; the default value of 1e+20 is effectively treated as infinity.

ILOG CPLEX detects unbounded problems in either of two ways:

• either it finds a solution with small complementarity that is not feasible for either the primal or the dual formulation of the problem;
• or the iterations tend toward infinity with the objective value becoming very large in absolute value.

The ILOG CPLEX Barrier Optimizer stops when the absolute value of either the primal or dual objective exceeds the objective range parameter, BarObjRng.

If you increase the value of BarObjRng, then the ILOG CPLEX Barrier Optimizer will iterate more times before it decides that the current problem suffers from an unbounded objective value.

If you know that your problem has large objective values, consider increasing BarObjRng.

Also if you know that your problem has large objective values, consider changing the barrier algorithm by resetting the BarAlg parameter.