Introducing the barrier optimizer

Describes the type of problem the barrier optimizer solves and characterizes its approach.

The IBM ILOG CPLEX barrier optimizer is well suited to large, sparse problems. An alternative to the simplex optimizers, which are also suitable to problems in which the matrix representation is dense, the barrier optimizer exploits a primal-dual logarithmic barrier algorithm to generate a sequence of strictly positive primal and dual solutions to a problem. As with the simplex optimizers, it is not really necessary to understand the internal workings of barrier in order to obtain its performance benefits. However, for the interested reader, here is an outline of how it works.

CPLEX finds the primal solutions, conventionally denoted (x, s), from the primal formulation:

Minimize c^Tx

subject to Ax = b

with these bounds x + s = u and x ≥ l

where A is the constraint matrix, including slack and surplus variables; u is the upper and l the lower bounds on the variables.

Simultaneously, CPLEX automatically finds the dual solutions, conventionally denoted (y, z, w) from the corresponding dual formulation:

Maximize b^Ty - u^Tw + l^Tz

subject to A^Ty - w + z = c

with these bounds w ≥ 0 and z ≥ 0

All possible solutions maintain strictly positive primal solutions (x - l, s) and strictly positive reduced costs (z, w) so that the value 0 (zero) forms a barrier for primal and dual variables within the algorithm.

CPLEX measures progress by considering the primal feasibility, dual feasibility, and duality gap at each iteration. To measure feasibility, CPLEX considers the accuracy with which the primal constraints (Ax = b, x + s = u) and dual constraints (A^Ty + z - w = c) are satisfied. The optimizer stops when it finds feasible primal and dual solutions that are complementary. A complementary solution is one where the sums of the products (x_j  -l_j)z_j and (u_j  - x_j)z_j are within some tolerance of 0 (zero). Since each (x_j  -l_j), (u_j  - x_j), and z_j is strictly positive, the sum can be near zero only if each of the individual products is near zero. The sum of these products is known as the complementarity of the problem.

On each iteration of the barrier optimizer, CPLEX computes a matrix based on AA^T and then computes a Cholesky factor of it. This factored matrix has the same number of nonzeros on each iteration. The number of nonzeros in this matrix is influenced by the barrier ordering parameter.

The CPLEX barrier optimizer is appropriate and often advantageous for large problems, for example, those with more than 100 000 rows or columns. It is not always the best choice, though, for sparse models with more than 100 000 rows. It is effective on problems with staircase structures or banded structures in the constraint matrix. It is also effective on problems with a small number of nonzeros per column (perhaps no more than a dozen nonzero values per column).

In short, denseness or sparsity are not the deciding issues when you are deciding whether to use the barrier optimizer. In fact, its performance is most dependent on these characteristics:

• the number of floating-point operations required to compute the Cholesky factor;

• the presence of dense columns, that is, columns with a relatively high number of nonzero entries.

To decide whether to use the barrier optimizer on a given problem, you should look at both these characteristics, not simply at denseness, sparseness, or problem size. (How to check those characteristics is explained later in this chapter in Cholesky factor in the log file, and Nonzeros in lower triangle of A*A' in the log file).