Basic formulation

Standard MPS format uses a fixed format text file to hold the problem information. Extended MPS format has two main differences from the standard form:

• The records in the file are free-format – that is, the fields are not necessarily in fixed columns or of fixed size, and each field is delimited by one or more spaces.
• The standard MPS format allows only numbers to be used in the "coefficient" fields – extended MPS format allows the use of formulae.
• There is an optional extra section in extended MPS format, holding additional data and structures for Xpress NonLinear.

We shall tend to use a fairly fixed format, to aid readability.

NAME POLYGON

The first record of any MPS file is the NAME record, which has the name which may be used to create file names where no other name is specified, and is also written into the matrix and solution files.

ROWS

The ROWS record introduces the list of rows of the problem – this includes the objective function as well as all the constraints.

N OBJ
E OBJEQ
G T2T1
G T3T2
G T4T3
L V1V2
L V1V3
L V2V3
L V2V4
L V3V4

The first character denotes the type of constraint. The possible values are:

N	not constraining (always used for the objective function, but may be used elsewhere).
E	equality: the left hand side (LHS) is equal to the right hand side (RHS).
L	less than or equal to: the LHS is less than or equal to the RHS.
G	greater than or equal to: the LHS is greater than or equal to the RHS.

The second field is the name used for the constraint. In MPS file format, everything has a name. Therefore, within each type of entity (rows, columns, etc) each name must be unique. In general, you should try to ensure that names are unique across all entities, to avoid possible confusion.

You should also try to make the names meaningful, so that you can understand what they mean.

In the example:
OBJ	is the objective function.
OBJEQ	is the "equality" version of the objective function which, as explained below, is required because we are trying to optimize a non-linear objective.
TiTj	is the constraint that will ensure θi ≥ θj (j=i-1).
ViVj	is the constraint that will ensure that the distance between Vi and Vj is ≤ 1.

COLUMNS

The COLUMNS record introduces the list of columns and coefficients in the matrix. In a normal linear problem, all the variables will appear explicitly as columns in this section. However, in non-linear problems, it is possible for variables to appear only in formulae and so they may not appear explicitly. In the example, the variables THETA1 to THETA4 appear explicitly, the variables RHO1 to RHO4 appear only in formulae. Constraints which involve only one variable in a linear way (that is, they limit the value of a variable to a minimum value, a maximum value or both – possibly equal – values) are usually put in a separate "BOUNDS" section which appears later.

  OBJX OBJ   1.0
  OBJX OBJEQ -1.0

The first field is the name of the column. All "COLUMNS" records for a column must be together. The second field is the name of the row (which was defined in the ROWS section). The third field is the value. It is not necessary to include zero values – only the non-zeros are required

If the coefficients are constant, then it is possible to put two on each record, by putting a second row name and value after the first (as in the example for THETA2 and THETA3 below).

The constraints putting θ_i in order are all linear – that is, the coefficients are all constant.

  THETA1  T2T1   -1
  THETA2  T2T1   1       T3T2   -1
  THETA3  T3T2   1       T4T3   -1
  THETA4  T4T3   1

The RHS of any constraint must be constant. Therefore, to write THETA2 ≥ THETA1, we must actually write THETA2 - THETA1 ≥ 0. The constraint T2T1 has coefficient -1 in THETA1 and +1 in THETA2.

We want to maximise the area of the polygon. The formula for this is the sum of the areas of the triangles with one vertex at V5 – i.e.:

  0.5 * RHO1 * RHO2 * SIN ( THETA2 - THETA1 ) +
  0.5 * RHO2 * RHO3 * SIN ( THETA3 - THETA2 ) +
  0.5 * RHO3 * RHO4 * SIN ( THETA4 - THETA3 )

– which is a non-linear function. Xpress NonLinear does not itself have a problem with non-linear objective functions, but Xpress distinguishes between the original N-type row which contains the objective function coefficients when the matrix is read in, and the objective function which is actually optimized. To avoid any confusion between these two "objectives", Xpress NonLinear also requires that the objective function as passed to Xpress Optimizer is linear. What we want to do is:

We create a new variable – called in this example OBJX – and write:

and then: maximize OBJX, where OBJX is just a variable.

The constraint linking OBJX and AREA was defined as the equality constraint OBJEQ in the ROWS section, and AREA is the formula given above. This is where the coefficient of -1 in column OBJX comes from.

Every item in the matrix has to be in a coefficient – that is, it is the multiplier of a variable. However, the formula for area, as written, is not a coefficient of anything. There are several ways of dealing with this situation. We shall start by breaking the formula up into coefficient form – that is, to write it as X1*formula1 + X2*formula2 + .... Our formula could then be:

  RHO1 * ( 0.5 * RHO2 * SIN ( THETA2 - THETA1 ) ) +
  RHO2 * ( 0.5 * RHO3 * SIN ( THETA3 - THETA2 ) ) +
  RHO3 * ( 0.5 * RHO4 * SIN ( THETA4 - THETA3 ) )

which is of the right form and can be written in the COLUMNS section as follows:

  RHO1 OBJEQ = 0.5 * RHO2 * SIN ( THETA2 - THETA1 )
  RHO2 OBJEQ = 0.5 * RHO3 * SIN ( THETA3 - THETA2 )
  RHO3 OBJEQ = 0.5 * RHO4 * SIN ( THETA4 - THETA3 )

Notice that the formula begins with an equals sign. When this is used in the coefficient field, it always means that a formula is being used rather than a constant. The formula must be written on one line – it does not matter how long it is – and each token (variable, constant, operator, bracket or function name) must be delimited by spaces.

When a formula is used, you can only write one coefficient on the record – the option of a second coefficient only applies when both coefficients are constants.

The constraints for the distances between pairs of vertices are relationships of the form:

RHO1 * RHO1 + RHO2 * RHO2 - 2 * RHO1 * RHO2 * COS ( THETA2 - THETA1 ) <= 1

These can again be split into coefficients, for example:

RHO1 * ( RHO1 - 2 * RHO2 * COS ( THETA2 - THETA1 ) ) + RHO2 * ( RHO2 )

This looks a little strange, because RHO2 appears as a coefficient of itself, but that is perfectly all right. This section of the matrix contains a set of records (one for each of the ViVj constraints) like this:

RHO1   V1V2 = RHO1 - 2 * RHO2 * COS ( THETA2 - THETA1 )
RHO2   V1V2 = RHO2

Note that because the records for each column must all appear together, the coefficients for – for example – RHO1 in this segment must be merged in with those in the previous (OBJEQ) segment.

RHS

The RHS record introduces the right hand side section.

The RHS section is formatted very much like a COLUMNS section with constant coefficients. There is a column name – it is actually the name of the right hand side – and then one or two entries per record. Again, only the non-zero entries are actually required.

RHS1 T2T1 .001  T3T2 .001
RHS1 T4T3 .001  V1V2 1
RHS1 V1V3 1     V1V4 1
RHS1 V2V3 1     V2V4 1
RHS1 V3V4 1

RHS1 is the name we have chosen for the right hand side. It is possible – although beyond the scope of this guide – to have more than one right hand side, and to select the one you want. Note that, in order to ensure we do have a polygon with N sides, we have made the relationship between theta(i) and theta(i-1) a strict inequality by adding 0.001 as the right hand side. If we did not, then two of the vertices could coincide and so the polygon would effectively lose one of its sides.

BOUNDS

The BOUNDS record introduces the BOUNDS section which typically holds the values of constraints which involve single variables.

Like the RHS section, it is possible to have more than one set of BOUNDS, and to select the one you want to use. There is therefore in each record a bound name which identifies the set of bounds to which it belongs. We shall be using only ones set of bounds, called BOUND1.

Bounds constrain a variable by providing a lower limit or an upper limit to its value. By providing a limit of -∞ for the lower bound, it is possible to create a variable which can take on any value – a "free" variable. The following bound types are provided:

LO	a lower bound.
UP	an upper bound.
FX	a fixed bound (the upper and lower limits are equal).
FR	a free variable (no lower or upper limit).
MI	a "minus infinity" variable – it can take on any non-positive value.

There are other types of bound which are used with integer programming, which is beyond the scope of this guide.

FR BOUND1 OBJX
LO BOUND1 RHO1    0.01
UP BOUND1 RHO1    1
LO BOUND1 RHO2    0.01
UP BOUND1 RHO2    1
LO BOUND1 RHO3    0.01
UP BOUND1 RHO3    1
LO BOUND1 RHO4    0.01
UP BOUND1 RHO4    1
UP BOUND1 THETA4  3.1415926

A record in a BOUNDS section can contain up to four fields. The first one is the bound type (from the list above). The second is the name of the BOUNDS set being used (ours is always BOUND1). The third is the name of the variable or column being bounded. Unless the bound type is FR or MI, there is a fourth field which contains the value of the bound.

Although we know that the area is always positive (or at least non-negative), a more complicated problem might have an objective function which could be positive or negative – you could make a profit or a loss – and so OBJX needs to be able to take on po sitive and negative values. The fact that it is marked as "free" here does not mean that it can actually take on any value, because it is still constrained by the rest of the problem.

The upper bounds on RHO1 to RHO4 provide the rest of the restrictions which ensure that the distances between any two vertices are = 1, and the limit on THETA4 ensures that the whole polygon is above the X-axis. Just to make sure that we do not "lose" a side because the value of RHOi becomes zero, we set a lower bound of 0.01 on all the rhos, performing a similar function to the RHS values of .001 for TiTj.

ENDATA

The last record in the file is the ENDATA record.

Although this is sufficient to define the model, it is usually better to give Xpress NonLinear some idea of where to start – that is, to provide a set of initial values for the variables. You do not have to provide values for everything, but you should try to provide them for every variable which appears in a non-linear coefficient, or which has a non-linear coefficient. In our current example, that means everything except OBJX.

SLPDATA

The SLPDATA record introduces a variety of different special items for Xpress NonLinear. It comes as the last section in the model (before the ENDATA record). We are using it at this stage for defining initial values. These are done with an IV record.

 IV IVSET1 RHO1 0.555
 IV IVSET1 RHO2 0.888
 IV IVSET1 RHO3 1
 IV IVSET1 RHO4 0.888

Just as with the RHS and BOUNDS sections, it is possible to have more than one set of initial values – perhaps because the same structure is used to solve a whole range of problems where the answers are so different that it does not make much sense to start always from the same place. In this example, we are using only one set – IVSET1.

The IV record contains four fields. The first one is IV, which indicates the type of SLPDATA being provided. The second is the name of the set of initial values. The third is the name of the variable and the fourth is the value being provided.

In the case of IV records, it is possible – and indeed perhaps necessary – to provide initial values which are zero. The default value (which is used if no value is provided) is not zero, so if you want to start with a zero value you must say so.