Identifying LPs for Barrier Optimization

> Continuous Optimization > Solving LPs: Barrier Optimizer > Identifying LPs for Barrier Optimization

Identifying LPs for Barrier Optimization

The ILOG CPLEX Barrier Optimizer is well suited to large, sparse problems. An alternative to the simplex optimizers, it 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.

ILOG 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, ILOG 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.

ILOG CPLEX measures progress by considering the primal feasibility, dual feasibility, and duality gap at each iteration. To measure feasibility, ILOG 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 (xj -lj)zj and (uj - xj)zj are within some tolerance of 0(zero). Since each (xj -lj), (uj - xj), and zj 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, ILOG 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 ILOG CPLEX Barrier Optimizer is appropriate and often advantageous for large problems, for example, those with more than 1000 rows or columns. 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.

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. (How to check those characteristics is explained later in this chapter in Cholesky Factor in the Log File, and Nonzeros in Lower Triangle of AAT in the Log File).

Barrier Simplex Crossover

Since many users prefer basic solutions because they can be used to restart simplex optimization, the ILOG CPLEX Barrier Optimizer includes basis crossover algorithms. By default, the barrier optimizer automatically invokes a primal crossover when the barrier algorithm terminates (unless termination occurs abnormally because of insufficient memory or numerical difficulties). Optionally, you can also execute barrier optimization with a dual crossover or with no crossover at all. The section Controlling Crossover explains how to control crossover in the Interactive Optimizer.

Differences between Barrier and Simplex Optimizers

The barrier optimizer and the simplex optimizers (primal and dual) are fundamentally different approaches to solving linear programming problems. The key differences between them have these implications:

Simplex and barrier optimizers differ with respect to the nature of solutions. Barrier solutions tend to be midface solutions. In cases where multiple optima exist, barrier solutions tend to place the variables at values between their bounds, whereas in basic solutions from a simplex technique, the values of the variables are more likely to be at either their upper or their lower bound. While objective values will be the same, the nature of the solutions can be very different.

The fact that barrier without crossover does not produce a basic solution has other consequences. Without a basis, you will not be able to optimize the same or similar problems repeatedly using advanced start information. You will also not be able to obtain range information for performing sensitivity analysis.

Simplex and barrier optimizers have different numerical properties, sensitivity, and behavior. For example, the barrier optimizer is sensitive to the presence of unbounded optimal faces, whereas the simplex optimizers are not. As a result, problems that are numerically difficult for one method may be easier to solve by the other.
Simplex and barrier optimizers have different memory requirements. Depending on the size of the Cholesky factor, the barrier optimizer can require significantly more memory than the simplex optimizers.
Simplex and barrier optimizers work well on different types of problems. The barrier optimizer works well on problems where the AAT remains sparse. Also, highly degenerate problems that pose difficulties for the primal or dual simplex optimizers may be solved quickly by the barrier optimizer. In contrast, the simplex optimizers will probably perform better on problems where the AAT and the resulting Cholesky factor are relatively dense, though it is sometimes difficult to predict from the dimensions of the model when this will be the case.

PREVIOUS NEXT