Difficulties during optimization

Suggests strategies for overcoming difficulties during optimization with the barrier optimizer.

Numeric difficulties can degrade performance of the CPLEX barrier optimizer or even prevent convergence toward a solution. There are several possible sources of numeric difficulties:

  • elimination of too many dense columns may cause numeric instability;

  • tight convergence tolerance may aggravate small numeric inconsistencies in a problem;

  • unbounded optimal faces may remain undetected and thus prevent convergence.

The following subsections offer guidance about overcoming those difficulties.

Numeric instability due to elimination of too many dense columns

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

You can check how many dense columns CPLEX removes by looking at the preprocessing statistics at the beginning of the log file. For example, the following log file shows that CPLEX removed 2249 columns, of which nine were dense. 


Selected objective sense:  MINIMIZE
Selected objective  name:  obj
Selected RHS        name:  rhs
Selected bound      name:  bnd

Problem 'XXX.mps' read.
Read time =    0.03 sec. (0.69 ticks)
Tried aggregator 1 time.
LP Presolve eliminated 2200 rows and 2249 columns.
Aggregator did 8 substitutions.
Reduced LP has 171 rows, 182 columns, and 1077 nonzeros.
Presolve time =    0.02 sec. (0.46 ticks)

***NOTE: Found 9 dense columns.

Number of nonzeros in lower triangle of A*A' = 6071
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec. (0.23 ticks)
Summary statistics for Cholesky factor:
  Rows in Factor            = 180
  Integer space required    = 313
  Total nonzeros in factor = 7286
  Total FP ops to factor    = 416448

If you observe that the removal of too many dense columns results in numeric 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 CPLEX to calculate the parameter automatically.

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

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

Small numeric inconsistencies and tight convergence tolerance

If your problem contains small numeric inconsistencies, it may be difficult for the 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 convergence tolerance parameter (BarEpComp for LP or QP models, BarQCPEpComp for QCP models).

Unbounded variables and unbounded optimal faces

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

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

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