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.