Overcoming Numerical Difficulties

INDEX PREVIOUS NEXT

As 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, it is a good idea to 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 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.

The ILOG CPLEX Barrier Optimizer implements the algorithms listed in Table 9.9. The selection of barrier algorithm is controlled by the BarAlg parameter. The default option invokes option 3 for LPs and QPs, option 1 for QCPs, 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 LP or QP 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 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 9.8.