Management of zero placeholder entries

Topics covered in this chapter:

The augmented matrix structure

During the augmentation process, Xpress-SLP builds additional matrix structure to represent the linear approximation of the nonlinear constraints within the problem (see Xpress-SLP Structures). In effect, it adds a generic structure which approximates the effect of changes to variables in nonlinear expressions, over and above that which would apply if the variables were simply replaced by their current values.

As a very simple example, consider the nonlinear constraint (R1, say)
X * Y ≤ 10

The variables X and Y are replaced by X₀+δX and Y₀+δY respectively, where X₀ and Y₀ are the values of X and Y at which the approximation will be made.

The original constraint is therefore
(X₀+δX)*(Y₀+δY) ≤ 10

Expanding this into individual terms, we have
X₀*Y₀ + X₀*δY + Y₀*δX + δX*δY ≤ 10

The first term is constant, the next two terms are linear in δY and δX respectively, and the last term is nonlinear.

The augmented structure deletes the nonlinear term, so that the remaining structure is a linear approximation to the original constraint. The justification for doing this is that if δX or δY (or both) are small, then the error involved in ignoring the term is also small.

The resulting matrix structure has entries of Y₀ in the delta variable δX and X₀ in the delta variable δY. The constant entry X₀*Y₀ is placed in the special "equals" column which has a fixed activity of 1. All these entries are updated at each SLP iteration as the solution process proceeds and the problem is linearized at a new point. The positions of these entries – (R1,δX), (R1,δY) and (R1,=) – are known as placeholders.

Derivatives and zero derivatives

At each SLP iteration, the values of the placeholders are re-calculated. In the example in the previous section, the values X₀ in the delta variable δY and Y₀ in the delta variable δX were effectively determined by analytic methods – that is, we differentiated the original formula to determine what values would be required in the placeholders.

In general, analytic differentiation may not be possible: the formula may contain functions which cannot be differentiated (because, for example, they are not smooth or not continuous), or for which the analytic derivatives are not known (because, for example, they are functions providing values from "black boxes" such as databases or simulators). In such cases, Xpress-SLP approximates the differentiation process by numerical methods. The example in the previous section would have approximate derivatives calculated as follows:

The current value of X (X₀) is perturbed by a small amount (dX), and the value of the formula is recalculated in each case.

f_d = (X₀ - dX) * Y₀
f_u = (X₀ + dX) * Y₀

derivative = (f_u - f_d) / ( 2 * dX)

In this particular example, the value obtained by numerical methods is the same as the analytic derivative. For more complex functions, there may be a slight difference, depending on the magnitude of dX.

This derivative represents the effect on the constraint of a change in the value of X. Obviously, if Y changes as well, then the combined effect will not be fully represented although, in general, it will be directionally correct.

The problem comes when Y₀ is zero. In such a case, the derivative is calculated as zero, meaning that changing X has no effect on the value of the formula. This can impact in one of two ways: either the value of X never changes because there is no incentive to do so, or it changes by unreasonably large amounts because there is no effect from doing so. If X and Y are linked in some other way, so that Y becomes nonzero when X changes, the approximation using zero as the derivative can cause the optimization process to behave badly.

Xpress-SLP tries to avoid the problem of zero derivatives by using small nonzero values for variables which are in fact zero. In most cases this gives a small nonzero value for the derivative, and hence for the placeholder entry. The model then contains some effect for the change in a variable, even if instantaneously the effect is zero.

The same principle is applied to analytic derivatives, so that the values obtained by either method are broadly similar.

Placeholder management

The default action of Xpress-SLP is to retain all the calculated values for all the placeholder entries. This includes values which would be zero without the special handling described in the previous section. We will call such values "zero placeholders".

Although retaining all the values gives the best chance of finding a good optimum, the presence of a large dense area of small values often gives rise to considerable numerical instability which adversely affects the optimization process. Xpress-SLP therefore offers a way of deleting small values which is less likely to affect the final outcome whilst improving numerical stability.

Most of the candidate placeholders are in the delta variables (represented by the δX and δY variables above). Various criteria can be selected for deletion of zero placeholder entries without affecting the validity of the basis (and so making the next SLP iteration more costly in time and stability). The criteria are selected using the control parameter XSLP_ZEROCRITERION as follows:

• Bit 0 (=1) Remove placeholders in nonbasic SLP variables
  This criterion applies to placeholders which are in the SLP variable (not the delta). Any value can be deleted from a nonbasic variable without upsetting the basis, so all eligible zero placeholders can be deleted.
• Bit 1 (=2) Remove placeholders in nonbasic delta variables
  Any value can be deleted from a nonbasic variable without upsetting the basis, so all eligible zero placeholders can be deleted.
• Bit 2 (=4) Remove placeholders in a basic SLP variable if its update row is nonbasic
  If the update row is nonbasic, then generally the basic SLP variable can be pivoted in the update row, so the basis is still valid if other entries are deleted. The entry in the update row is always 1.0 and will never be deleted.
• Bit 3 (=8) Remove placeholders in a basic delta variable if its update row is nonbasic and the corresponding SLP variable is nonbasic
  If the delta is basic and the corresponding SLP variable is nonbasic, then the delta will pivot in the update row (the delta and the SLP variable are the only two variables in the update row), so the basis is still valid if other entries are deleted. The entry in the update row is always -1.0 and will never be deleted.
• Bit 4 (=16) Remove placeholders in a basic delta variable if the determining row for the corresponding SLP variable is nonbasic
  If the delta variable is basic and the determining row for the corresponding SLP variable is nonbasic then it is generally possible (although not 100% guaranteed) to pivot the delta variable in the determining row. so the basis is still valid if other entries are deleted. The entry in the determining row is never deleted even if it is otherwise eligible.

The following constants are provided for setting these bits:

There are two additional control parameters used in this procedure:

• XSLP_ZEROCRITERIONSTART
  This is the first SLP iteration at which zero placeholders will be examined for eligibility. Use of this parameter allows a balance to be made between optimality and numerical stability.
• XSLP_ZEROCRITERIONCOUNT
  This is the number of consecutive SLP iterations that a placeholder is a zero placeholder before it is deleted. So, if in the earlier example XSLP_ZEROCRITERIONCOUNT is 2, the entry in the delta variable dX will be deleted only if Y was also zero on the previous SLP iteration.

Regardless of the basis status of a variable, its delta, update row and determining row, if a zero placeholder was deleted on the previous SLP iteration, it will always be deleted in the current SLP iteration (keeping a zero matrix entry at zero does not upset the basis).

If the optimization method is barrier, or the basis is not being used, then the bit settings of XSLP_ZEROCRITERION are not used as such: if XSLP_ZEROCRITERION is nonzero, all zero placeholders will be deleted subject to XSLP_ZEROCRITERIONCOUNT and XSLP_ZEROCRITERIONSTART.