Understanding Solution Quality from the Barrier LP Optimizer

When ILOG CPLEX successfully solves a problem with the ILOG CPLEX Barrier Optimizer, it reports the optimal objective value and solution time in a log file, as it does for other LP optimizers.

Because barrier solutions (prior to crossover) are not basic solutions, certain solution statistics associated with basic solutions are not available for a strictly barrier solution. For example, reduced costs and dual values are available for strictly barrier LP solutions, but range information about them is not.

To help you evaluate the quality of a barrier solution more readily, ILOG CPLEX offers a special display of information about barrier solution quality. To display this information in the Interactive Optimizer, use the command display solution quality after optimization. When using the Component Libraries, use the method cplex.getQuality() or use the routines CPXgetintquality() for integer information and CPXgetdblquality() for double-valued information.

Table 4.11 Barrier Solution Quality Display
Item	Meaning
primal objective	primal objective value cTx
dual objective	dual objective value bTy - uTw + lTz
duality gap	difference between primal and dual objectives
complementarity	sum of column and row complementarity
column complementarity (total)	sum of \|(xj - lj )· zj\| + \|(uj - xj )· wj\|
column complementarity (max)	maximum of \|(xj - lj )· zj\| and \|(uj - xj )· wj\| over all variables
row complementarity (total)	sum of \|slacki · yi\|
row complementarity (max)	maximum of \|slacki · yi\|
primal norm \|x\| (total)	sum of absolute values of all primal variables
primal norm \|x\| (max)	maximum of absolute values of all primal variables
dual norm \|rc\| (total)	sum of absolute values of all reduced costs
dual norm \|rc\| (max)	maximum of absolute values of all reduced costs
primal error (Ax = b) (total, max)	total and maximum error in satisfying primal equality constraints
dual error (A'pi + rc = c) (total, max)	total and maximum error in satisfying dual equality constraints
primal x bound error (total, max)	total and maximum error in satisfying primal lower and upper bound constraints
primal slack bound error (total, max)	total and maximum violation in slack variables
dual pi bound error (total, max)	total and maximum violation with respect to zero of dual variables on inequality rows
dual rc bound error (total, max)	total and maximum violation with respect to zero of reduced costs
primal normalized error (Ax = b) (max)	accuracy of primal constraints
dual normalized error (A'pi + rc = c) (max)	accuracy of dual constraints

Table 4.11 lists the items ILOG CPLEX displays and explains their meaning. In the solution quality display, the term pi refers to dual solution values, that is, the y values in the conventional barrier problem-formulation. The term rc refers to reduced cost, that is, the difference z - w in the conventional barrier problem-formulation. Other terms are best understood in the context of primal and dual LP formulations.

Normalized errors, for example, represent the accuracy of satisfying the constraints while considering the quantities used to compute Ax on each row and yTA on each column. In the primal case, for each row, we consider the nonzero coefficients and the xj values used to compute Ax. If these numbers are large in absolute value, then it is acceptable to have a larger absolute error in the primal constraint.

If ILOG CPLEX returned an optimal solution, but the primal error seems high to you, the primal normalized error should be low, since it takes into account the scaling of the problem and solution.

After a simplex optimization-whether primal, dual, or network-or after a crossover, the display command will display information related to the quality of the simplex solution.