Tuning Barrier Optimizer Performance

Naturally, the default parameter settings for the ILOG CPLEX Barrier Optimizer work best on most problems. However, you can tune several algorithmic parameters to improve performance or to overcome numerical difficulties. These parameters are described in the sections:

In addition, several parameters set termination criteria. With them, you control when ILOG CPLEX stops optimization.

You can also control convergence tolerance-another factor that influences performance. Convergence tolerance determines how nearly optimal a solution ILOG CPLEX must find: tight convergence tolerance means ILOG CPLEX must keep working until it finds a solution very close to the optimal one; loose tolerance means ILOG CPLEX can return a solution within a greater range of the optimal one and thus stop calculating sooner.

Performance of the ILOG CPLEX Barrier Optimizer is most highly dependent on the number of floating-point operations required to compute the Cholesky factor at each iteration. When you adjust barrier parameters, always check their impact on this number. At default output settings, this number is reported at the beginning of each barrier optimization in the log file, as we explain in Cholesky Factor in the Log File.

Another important performance issue is the presence of dense columns. By a dense column, we mean that a given variable appears in a relatively large number of rows. You can check column density as we suggest in Nonzeros in Lower Triangle of AAT in the Log File. We also say more about column density in Detecting and Eliminating Dense Columns.

In adjusting parameters, you may need to experiment to find beneficial settings because the precise effect of parametric changes will depend on the nature of your LP problem as well as your platform (hardware, operating system, compiler, etc.). Once you have found satisfactory parametric settings, keep them in a parameter specification file for re-use, as explained in Saving a Parameter Specification File.

Out-of-Core Barrier: Letting the Optimizer Use Disk for Storage

Under default settings, the ILOG CPLEX Barrier Optimizer will do all of its work using central memory (variously referred to also as RAM, core, or physical memory). For models too large to solve in the central memory on your computer, or in cases where it is simply not desired to use this much memory, it is possible to instruct the barrier optimizer to use disk for part of the working storage it needs, specifically the Cholesky factorization. Since disk is slower than central memory, there may be some lost performance by making this choice on models that could be solved entirely in central memory, but the out-of-core feature in the ILOG CPLEX Barrier Optimizer is designed to make this as efficient as possible. It generally will be far more effective than relying on the operating system's virtual memory (swap space). To activate out-of-core Barrier, set the parameter BarOOC to 1 instead of its default value of 0.

Note that out-of-core barrier uses some working memory to store the portion of the factor on which it is currently performing computation. You can improve performance by allocating more working memory, using the WorkMem parameter. More working memory allows the algorithm to transfer less factor data to and from disk. In fact, the factor matrix will not be written to disk at all if its size does not exceed the value of WorkMem. The default for this parameter is 128, meaning 128 megabytes.

When Barrier is being run out-of-core, the location of disk storage is controlled by the Working Directory parameter, WorkDir. For example, to use the directory /tmp/mywork, set WorkDir to the string '/tmp/mywork'. WorkDir should be specified as the name of a directory that already exists, and ILOG CPLEX will create its working directory under that.

Preprocessing: the Presolver and Aggregator

For best performance of the ILOG CPLEX Barrier Optimizer, preprocessing should almost always be on. That is, we recommend that you use the default setting where the presolver and aggregator are active. While they may use more memory, they also reduce the problem, and problem reduction is crucial to barrier optimizer performance. In fact, reduction is so important that even when you turn off preprocessing, ILOG CPLEX still applies minimal presolving before barrier optimization.

For problems that contain linearly dependent rows, it is a good idea to turn on the preprocessing dependency parameter. (By default, it is off.) This dependency checker may add some preprocessing time, but it can detect and remove linearly dependent rows to improve overall performance.

To turn on dependency checking, set parameter DepInd to 1.

Detecting and Eliminating Dense Columns

Dense columns can significantly degrade barrier optimizer performance. A dense column is one in which a given variable appears in many rows. The interactive optimizer contains a display feature that shows a histogram of the number of nonzeros in the columns of your model, display problem histogram c.

In fact, when a few dense columns are present in a problem, it is often effective to reformulate the problem to remove those dense columns from the model.

Otherwise, you can control whether ILOG CPLEX perceives columns as dense by setting the column nonzeros parameter. At its default setting, ILOG CPLEX calculates an appropriate value for this parameter automatically. However, if your problem contains one (or a few) dense columns that remain undetected at the default setting, you can adjust this parameter yourself to help ILOG CPLEX detect it (or them). For example, in a large problem in which one column contains forty entries while the other columns contain less than five entries, you may benefit by setting the column nonzeros parameter to 30. This setting allows ILOG CPLEX to recognize that column as dense and thus invoke techniques to handle it.

To set the dense column threshold, set the parameter BarColNz to a positive integer. The default value of 0 means that ILOG CPLEX will determine the threshold.

Choosing an Ordering Algorithm

ILOG CPLEX offers several different algorithms in the ILOG CPLEX Barrier Optimizer for ordering the rows of a matrix:

The log file, as we explain in Ordering-Algorithm Time in the Log File, records the time spent by the ordering algorithm in a barrier optimization, so you can experiment with different ordering algorithms and compare their performance on your problem.

Automatic ordering, the default option, will usually be the best choice. This option attempts to choose the most effective of the available ordering methods, and it usually results in the best order. It may require more time than the other settings. The ordering time is usually small relative to the total solution time, and a better order can lead to a smaller total solution time. In other words, a change in this parameter is unlikely to improve performance very much.

The AMD algorithm provides good quality order within moderate ordering time. AMF usually provides better order than AMD (usually 5-10% smaller factors) but it requires somewhat more time (10-20% more). ND often produces significantly better order than AMD or AMF. Ten-fold reductions in runtimes of the ILOG CPLEX Barrier Optimizer have been observed with it on some problems. However, ND sometimes produces worse order, and it requires much more time.

To select an ordering algorithm, set the parameter BarOrder to a value 0, 1, 2, or 3.

Using a Starting-Point Heuristic

ILOG CPLEX supports several different heuristics to compute the starting point for the ILOG CPLEX Barrier Optimizer. The starting-point heuristic is determined by the BarStartAlg parameter, and Table 5.12 summarizes the possible values and their meanings.

Table 5.12 BarStartAlg Parameter Values for Starting-Point Heuristics

dual is 0 (default) 
estimate dual 
average primal estimate, dual 0 
average primal estimate, estimate dual 

For most problems the default works well. However, if you are using the dual preprocessing option (setting the parameter PreDual to 1) then one of the other heuristics for computing a starting point may perform better than the default.

Previous Page: Understanding Solution Quality from the Barrier LP Optimizer  Return to Top Next Page: Overcoming Numerical Difficulties