Interpreting the Barrier Log File

Like the ILOG CPLEX simplex optimizers, the barrier optimizer records information about its progress in a log file as it works. Some users find it helpful to keep a new log file for each session. By default, ILOG CPLEX records information in a file named cplex.log. In the:

You can control the level of information that ILOG CPLEX records about barrier optimization by setting the BarDisplay parameter. Its allowed values and their meanings are as follows:

Table 5.9 BarDisplay Parameter Values
BarDisplay Values 
Meaning 
0 
no display 
1 
display normal information (default) 
2 
display detailed (diagnostic) output 

Here is an example of a log file for a barrier optimization (without crossover):

Tried aggregator 1 time.

LP Presolve eliminated 9 rows and 11 columns.

Aggregator did 6 substitutions.

Reduced LP has 12 rows, 15 columns, and 38 nonzeros.

Presolve time =    0.00 sec.

Number of nonzeros in lower triangle of A*A' = 26

Using Approximate Minimum Degree ordering

Total time for automatic ordering = 0.00 sec.

Summary statistics for Cholesky factor:

  Rows in Factor            = 12

  Integer space required    = 12

  Total non-zeros in factor = 78

  Total FP ops to factor    = 650

 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf          

   0  -1.3177911e+01  -1.2600000e+03  6.55e+02  0.00e+00  3.92e+01

   1  -4.8683118e+01  -5.4058675e+02  3.91e+01  0.00e+00  1.18e+01

   2  -1.6008142e+02  -3.5969226e+02  1.35e-13  7.11e-15  5.81e+00

   3  -3.5186681e+02  -6.1738305e+02  1.59e-10  1.78e-15  5.16e-01

   4  -4.5808732e+02  -4.7450513e+02  5.08e-12  1.95e-14  4.62e-02

   5  -4.6435693e+02  -4.6531819e+02  1.66e-12  1.27e-14  1.59e-03

   6  -4.6473085e+02  -4.6476678e+02  5.53e-11  2.17e-14  2.43e-15

   7  -4.6475237e+02  -4.6475361e+02  5.59e-13  2.99e-14  2.19e-15

   8  -4.6475312e+02  -4.6475316e+02  1.73e-13  1.55e-14  1.17e-15

   9  -4.6475314e+02  -4.6475314e+02  1.45e-13  2.81e-14  2.17e-15



Barrier - Optimal:  Objective =   -4.6475314194e+02

Solution time =    0.01 sec.  Iterations = 9

Preprocessing in the Log File

The opening lines of that log file record information about preprocessing by the ILOG CPLEX presolver and aggregator. After those preprocessing statistics, the next line records the number of nonzeros in the lower triangle of a particular matrix, AAT, denoted A*A' in the log file.

Nonzeros in Lower Triangle of AAT in the Log File

The number of nonzeros in the lower triangle of AAT gives an early indication of how long each barrier iteration will take. The larger this number, the more time each barrier iteration requires. If this number is close to 50% of the square of the number of rows, then the problem may contain dense columns that are not being detected. In that case, examine the histogram of column counts; then consider setting the barrier column-nonzeros parameter to a value that enables ILOG CPLEX to treat more columns as being dense.

Ordering-Algorithm Time in the Log File

After the number of nonzeros in the lower triangle of AAT, ILOG CPLEX records the time required by the ordering algorithm. (The ILOG CPLEX Barrier Optimizer offers you a choice of four ordering algorithms, explained in Choosing an Ordering Algorithm.) This section in the log file indicates which ordering algorithm the default Automatic setting chose.

Cholesky Factor in the Log File

After the time required by the ordering algorithm, ILOG CPLEX records information about the Cholesky factor. ILOG CPLEX computes this matrix on each iteration. The number of rows in the Cholesky factor represents the number after preprocessing. The next line of information about the Cholesky factor-integer space required-indicates the amount of memory needed to store the sparsity pattern of the factored matrix. If this number is low, then the factor can be computed more quickly than when the number is high.

Information about the Cholesky factor continues with the number of nonzeros in the factored matrix. The difference between this number and the number of nonzeros in AAT indicates the fill-level of the Cholesky factor. If the fill-level is large, consider an alternate ordering algorithm.

The final line of information indicates how many floating-point operations are required to compute the Cholesky factor. This number is the best predictor of the time that will be required to perform each iteration of the barrier method.

Iteration Progress in the Log File

After the information about the Cholesky factor, the log file records progress at each iteration. It records both primal and dual objectives (as Primal Obj and Dual Obj) per iteration.

It also records absolute infeasibilities per iteration. Internally, the ILOG CPLEX Barrier Optimizer treats inequality constraints as equality constraints with added slack and surplus variables. Consequently, primal constraints in a problem are written as Ax = b and x + s = u, and the dual constraints are written as ATy + z - w = c. As a result, in the log file, the infeasibilities represent norms, as summarized in Table 5.10.

Table 5.10 Infeasibilities and Norms in the Log File of a Barrier Optimization
Infeasibility 
In log file 
Norm 
primal  
Prim Inf 
|b - Ax| 
upper 
Upper Inf 
|u - (x + s)| 
dual 
Dual Inf 
|c - yA - z + w| 

If solution values are large in absolute value, then the infeasibilities may appear inordinately large because they are recorded in the log file in absolute terms. The optimizer uses relative infeasibilities as termination criteria.

Infeasibility Ratio in the Log File

If you are using one of the barrier infeasibility algorithms available in the ILOG CPLEX Barrier Optimizer (that is, if you have set BarAlg to either 1 or 2, as discussed later in this chapter), then ILOG CPLEX records an additional column of output titled Inf Ratio, the infeasibility ratio. This ratio, always positive, is a measure of progress for that particular algorithm. In a problem with an optimal solution, you will see this ratio increase to a large number. In contrast, in a problem that is infeasible or unbounded, this ratio will decrease to a very small number.

Copyright © 2002 ILOG
http://www.ilog.com
 
 
 
 
Previous Page: Controlling Crossover Return to Top Next Page: Understanding Solution Quality from the Barrier LP Optimizer