Xpress-SLP Formulae
Xpress-SLP can handle formulae described in three different ways:
- Character strings
- The formula is written exactly as it would appear in, for example, the Extended MPS format used for text file input.
- Internal unparsed format
- The tokens within the formula are replaced by a
{token type, token value} pair. The list of types and values is in the table below. - Internal parsed format
- The tokens are converted as in the unparsed format, but the order is changed so that the resulting array forms a reverse-Polish execution stack for direct evaluation by the system.
Parsed and unparsed formulae
All formulae input into Xpress-SLP are parsed into a reverse-Polish execution stack. Tokens are identified by their type and a value. The table below shows the values used in interface functions.
All formulae are provided in the interface functions as two parallel arrays:
an integer array of token types;
a double array of token values.
The last token type in the array should be an end-of-formula token (XSLP_EOF, which evaluates to zero).
If the value required is an integer, it should still be provided in the array of token values as a double precision value.
| Type | Description | Value |
|---|---|---|
| XSLP_COL | column | index of matrix column. This respects the setting of XPRS_CSTYLE. |
| XSLP_CON | constant | (double) value. |
| XSLP_CONSTRAINT | constraint | index of constraint. Note that constraints count from 1, so that the index of matrix row n is n + XPRS_CSTYLE. |
| XSLP_CV | character variable | index of character variable. |
| XSLP_DEL | delimiter | XSLP_COMMA (1) = comma (",") |
| XSLP_COLON (2) = colon (":") | ||
| XSLP_EOF | end of formula | not required: use zero |
| XSLP_FUN | user function | index of function |
| XSLP_IFUN | internal function | index of function |
| XSLP_LB | left bracket | not required: use zero |
| XSLP_OP | operator | XSLP_UMINUS (1) = unary minus ("-") |
| XSLP_EXPONENT (2) = exponent ("**" or "^") | ||
| XSLP_MULTIPLY (3) = multiplication ("*") | ||
| XSLP_DIVIDE (4) = division ("/") | ||
| XSLP_PLUS (5) = addition ("+") | ||
| XSLP_MINUS (6) = subtraction ("-") | ||
| XSLP_RB | right bracket | not required: use zero |
| XSLP_ROW | row | index of matrix row. This respects the setting of XPRS_CSTYLE. |
| XSLP_STRING | character string | internal index of character string |
| XSLP_UNKNOWN | unidentified token | internal index of character string |
| XSLP_VAR | variable | index of variable. Note that variables count from 1, so that the index of matrix column n is n + XPRS_CSTYLE. |
| XSLP_VARREF | reference to variable | index of variable. Note that variables count from 1, so that the index of matrix column n is n + XPRS_CSTYLE. |
| XSLP_XV | extended variable array | index of XV |
| XSLP_UFARGTYPE | requirements and types of argument for a user function | bitmap of types (see below). |
| XSLP_UFEXETYPE | linkage of a user function | bitmap of linkage information (see below). |
| XSLP_XVVARTYPE | type of variable in XV | XSLP_VAR or XSLP_XV |
| XSLP_XVINTINDEX | index of XV item name | index of name in Xpress-SLP string table |
Argument types for user function definition are stored as a bit map. Each type is stored in 3 bits: bits 0-2 for argument 1, bits 3-5 for argument 2 and so on. The possible values for each argument are as follows:
| 0 | omitted |
| 1 | NULL |
| 2 | INTEGER |
| 3 | DOUBLE |
| 4 | VARIANT |
| 6 | CHAR |
The linkage type and other function information are stored as a bit map as follows:
| Bits 0-2 | type of linkage: |
| 1 = User library or DLL | |
| 2 = Excel spreadsheet | |
| 3 = Excel macro | |
| 5 = MOSEL | |
| 6 = VB | |
| 7 = COM | |
| Bits 3-4 | re-evaluation flags: |
| 0 = default | |
| 1 (Bit 3) = re-evaluation at each SLP iteration | |
| 2 (Bit 4) = re-evaluation when independent variables are outside tolerance | |
| Bits 6-7 | derivative flags: |
| 0 = default | |
| 1 (Bit 6) = tangential derivatives | |
| 2 (Bit 7) = forward derivatives | |
| Bit 8 | calling mechanism: |
| 0 = standard | |
| 1 = CDECL (Windows only) | |
| Bit 24 | set if the function is multi-valued |
| Bit 28 | set if the function is not differentiable |
Token types XSLP_ROW and XSLP_COL are used only when passing formulae into Xpress-SLP. These tokens both respect the setting of XPRS_CSTYLE. Any formulae recovered from Xpress-SLP will use the XSLP_CONSTRAINT and XSLP_VAR token types which always count from 1.
When a formula is passed to Xpress-SLP in "internal unparsed format" — that is, with the formula already converted into tokens — the full range of token types is permitted.
When a formula is passed to Xpress-SLP in "parsed format" — that is, in reverse
Polish — the following rules apply:
| XSLP_DEL | comma is optional. |
| XSLP_FUN | implies a following left-bracket, which is not included explicitly. |
| XSLP_IFUN | implies a following left-bracket, which is not included explicitly. |
| XSLP_LB | never used. |
| XSLP_RB | only used to terminate the list of arguments to a function. |
Brackets are not used in the reverse Polish representation of the formula: the order of evaluation is determined by the order of the items on the stack. Functions which need the brackets — for example XSLPgetccoef — fill in brackets as required to achieve the correct evaluation order. The result may not match the formula as originally provided.
Token type XSLP_UNKNOWN is returned by the parsing routines when a string cannot be identified as any other type of token. Token type XSLP_STRING is returned by the parsing routine where the token has been specifically identified as being a character string: the only case where this occurs at present is in the names of return arguments from user-defined multi-valued functions. The "value" field for both these token types is an index into the Xpress-SLP string table and can be accessed using the XSLPgetstring function.
Example of an arithmetic formula
x2+4y(z-3)
Written as an unparsed formula, each token is directly transcribed as follows:
| Type | Value |
|---|---|
| XSLP_VAR | index of x |
| XSLP_OP | XSLP_EXPONENT |
| XSLP_CON | 2 |
| XSLP_OP | XSLP_PLUS |
| XSLP_CON | 4 |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_VAR | index of y |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_LB | 0 |
| XSLP_VAR | index of z |
| XSLP_OP | XSLP_MINUS |
| XSLP_CON | 3 |
| XSLP_RB | 0 |
| XSLP_EOF | 0 |
Written as a parsed formula (in reverse Polish), an evaluation order is established first, for example:
x 2 ^ 4 y * z 3 - * +
and this is then transcribed as follows:
| Type | Value |
|---|---|
| XSLP_VAR | index of x |
| XSLP_CON | 2 |
| XSLP_OP | XSLP_EXPONENT |
| XSLP_CON | 4 |
| XSLP_VAR | index of y |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_VAR | index of z |
| XSLP_CON | 3 |
| XSLP_OP | XSLP_MINUS |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_OP | XSLP_PLUS |
| XSLP_EOF | 0 |
Notice that the brackets used to establish the order of evaluation in the unparsed formula are not required in the parsed form.
Example of a formula involving a simple function
y*MyFunc(z,3)
Written as an unparsed formula, each token is directly transcribed as follows:
| Type | Value |
|---|---|
| XSLP_VAR | index of y |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_FUN | index of MyFunc |
| XSLP_LB | 0 |
| XSLP_VAR | index of z |
| XSLP_DEL | XSLP_COMMA |
| XSLP_CON | 3 |
| XSLP_RB | 0 |
| XSLP_EOF | 0 |
Written as a parsed formula (in reverse Polish), an evaluation order is established first, for example:
y ) 3 , z MyFunc( *
and this is then transcribed as follows:
| Type | Value |
|---|---|
| XSLP_VAR | index of y |
| XSLP_RB | 0 |
| XSLP_CON | 3 |
| XSLP_DEL | XSLP_COMMA |
| XSLP_VAR | index of z |
| XSLP_FUN | index of MyFunc |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_EOF | 0 |
Notice that the function arguments are in reverse order, and that a right bracket is used as a delimiter to indicate the end of the argument list. The left bracket indicating the start of the argument list is implied by the XSLP_FUN token.
Example of a formula involving a complicated function
This example uses a function which takes two arguments and returns an array of results, which are identified by name. In the formula, the return value named VAL1 is being retrieved.
y*MyFunc(z,3:VAL1)
Written as an unparsed formula, each token is directly transcribed as follows:
| Type | Value |
|---|---|
| XSLP_VAR | index of y |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_FUN | index of MyFunc |
| XSLP_LB | 0 |
| XSLP_VAR | index of z |
| XSLP_DEL | XSLP_COMMA |
| XSLP_CON | 3 |
| XSLP_DEL | XSLP_COLON |
| XSLP_STRING | index of VAL1 in string table |
| XSLP_RB | 0 |
| XSLP_EOF | 0 |
Written as a parsed formula (in reverse Polish), an evaluation order is established first, for example:
y ) VAL1 : 3 , z MyFunc( *
and this is then transcribed as follows:
| Type | Value |
|---|---|
| XSLP_VAR | index of y |
| XSLP_RB | 0 |
| XSLP_STRING | index of VAL1 in string table |
| XSLP_DEL | XSLP_COLON |
| XSLP_CON | 3 |
| XSLP_DEL | XSLP_COMMA |
| XSLP_VAR | index of z |
| XSLP_FUN | index of MyFunc |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_EOF | 0 |
Notice that the function arguments are in reverse order, including the name of the return value and the colon delimiter, and that a right bracket is used as a delimiter to indicate the end of the argument list.
Example of a formula defining a user function
User function definitions in XSLPadduserfuncs and XSLPloaduserfuncs are provided through the formula structure. Assume we wish to add the function defined in Extended MPS format as
MyFunc = Func1 (DOUBLE,INTEGER) MOSEL = MyModel = MyArray
We also want to evaluate the function only when its arguments have changed outside tolerances. This also requires function instances. In the definition of a user function, there is no distinction made between parsed and unparsed format: the tokens provide information and are interpreted in the order in which they are encountered. The function definition is as follows:
| Type | Value |
|---|---|
| XSLP_STRING | index of Func1 in string table |
| XSLP_UFARGTYPE | 26 (octal 32) |
| XSLP_UFEXETYPE | 21 (Bit 4 set, and Bits 0-2 = 5) |
| XSLP_STRING | index of MyModel in string table |
| XSLP_STRING | index of MyArray in string table |
| XSLP_EOF | 0 |
The string arguments are interpreted in the order in which they appear. Therefore, if any of the function parameters (param1 to param3 in Extended MPS format) is required, there must be entries for the internal function name and any preceding function parameters. If the fields are blank, use an XSLP_STRING token with a zero value.
The name of the function itself (MyFunc in this case) is provided through the function XSLPaddnames.
Example of a formula defining an XV
An XV (extended variable array) is defined by its individual items. XV definitions in XSLPaddxvs and XSLPloadxvs are provided through the formula structure. Assume we wish to add the XV defined in Extended MPS format as:
MyXV x
MyXV y = VAR1
MyXV = = = x * 2
Then the definition in parsed format is as follows:
| Type | Value |
|---|---|
| XSLP_XVVARTYPE | XSLP_VAR |
| XSLP_XVVARINDEX | index of x |
| XSLP_EOF | 0 |
| XSLP_XVVARTYPE | XSLP_VAR |
| XSLP_XVVARINDEX | index of y |
| XSLP_XVINTINDEX | index of VAR1 in string table |
| XSLP_EOF | 0 |
| XSLP_VAR | index of x |
| XSLP_CON | 2 |
| XSLP_OP | XSLP_MULTIPLY |
| XSLP_EOF | 0 |
Parsed or unparsed format is only relevant where formulae are being provided (as in the third item above).
Example of a formula defining a DC
A DC (delayed constraint) can be activated when a certain condition is met by the solution of a preceding linear approximation. The condition is described in a formula which evaluates to zero (if the condition is not met) or nonzero (if the condition is met). Assume we wish to add the DCs described in Extended MPS format as follows:
DC ROW1 = GT(x,1)
DC ROW2 = MV(ROW99)
Then the definition in parsed format is as follows:
| Type | Value |
|---|---|
| XSLP_RB | 0 |
| XSLP_CON | 1 |
| XSLP_DEL | XSLP_COMMA |
| XSLP_VAR | index of x |
| XSLP_IFUN | index of GT |
| XSLP_EOF | 0 |
| XSLP_RB | 0 |
| XSLP_ROW | index (respecting XPRS_CSTYLE) of ROW99 |
| XSLP_IFUN | index of MV |
| XSLP_EOF | 0 |
Formula evaluation and derivatives
In many applications, the same function is used in several matrix entries. Indeed, often the only difference between the entries is the sign of the entry or a difference in (constant) scaling factor. Xpress-SLP separates any constant factor from the formula, and stores a non-linear coefficient as factor * formula. In this way, when a formula has been evaluated once, its value can be used repeatedly without the need for re-evaluation.
Xpress-SLP needs partial derivatives of all formulae in order to create the linear approximations to the problem. In the absence of any other information, derivatives are calculated numerically, by making small perturbations of the independent variables and re-evaluating the formulae.
Analytic derivatives will be used if XSLP_DERIVATIVES is set to 1. The mathematical operators and the internal functions are differentiated automatically. User functions must provide their own derivatives; if they do not, then derivatives for the functions will be evaluated numerically.
Analytic derivatives need more time to set up, but evaluation of the derivatives is then
faster particularly for formulae like:
f(xi)
N
i=1
If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.