Creating the linear part of the problem

The linear part of the problem, and the definitions of the rows and columns of the problem are carried out using the normal Xpress Optimizer functions.

#define MAXROW 20
#define MAXCOL 20
#define MAXELT 50
  int nRow, nCol, nSide, nRowName, nColName;
  int Sin, Cos;
  char RowType[MAXROW];
  double RHS[MAXROW], OBJ[MAXCOL], Element[MAXELT];
  double Lower[MAXCOL], Upper[MAXCOL];
  int ColStart[MAXCOL+1], RowIndex[MAXELT];
  char RowNames[500], ColNames[500];

In this example, we have set the dimensions by using #define statements, rather than working out the actual sizes required from the number of sides and then allocating the space dynamically.

  nSide = 5;
  nRowName = 0;
  nColName = 0;

By making the number of sides a variable (nSide) we can create other polygons by changing its value.

It is useful – at least while building a model – to be able to see what has been created. We will therefore create meaningful names for the rows and columns. nRowName and nColName count along the character buffers RowNames and ColNames.

  nRow = nSide-2 + (nSide-1)*(nSide-2)/2 + 1;
  nCol = (nSide-1)*2 + 2;
  for (i=0; i<nRow; i++) RHS[i] = 0;

The number of constraints is:

The number of columns is:

We are using "C"-style numbering for rows and columns, so the counting starts from zero.

  nRow = 0;
  RowType[nRow++] = 'E'; /* OBJEQ */
  nRowName = nRowName + 1 + sprintf(&RowNames[nRowName], "OBJEQ");
  for (i=1; i<nSide-1; i++) {
    RowType[nRow++] = 'G'; /* T2T1 .. T4T3 */
    RHS[i] = 0.001;
    nRowName = nRowName + 1 + sprintf(&RowNames[nRowName], "T%dT%d", i+1, i);
  }

This sets the row type indicator for OBJEQ and the theta relationships, with a right hand side of 0.001. We also create row names in the RowNames buffer. Each name is terminated by a NULL character (automatically placed there by the sprintf function). sprintf returns the length of the string written, excluding the terminating NULL character.

  for (i=1; i<nSide-1; i++) {
    for (j=i+1; j<nSide; j++) {
      RowType[nRow] = 'L';
      RHS[nRow++] = 1.0;
      nRowName = nRowName + 1 + sprintf(&RowNames[nRowName], "V%dV%d", i, j);
    }
  }

This defines the L-type rows which constrain the distances between pairs of vertices. The right hand side is 1.0 (the maximum value) and the names are of the form ViVj.

  for (i=0; i<nCol; i++) {
    OBJ[i] = 0;        /* objective function */
    Lower[i] = 0;      /* lower bound normally zero */
    Upper[i] = XPRS_PLUSINFINITY; /* upper bound = infinity */
  }

This sets up the standard column data, with objective function entries of zero, and default bounds of zero to plus infinity. We shall change these for the individual items as required.

  nCol = 0;
  nElement = 0;
  ColStart[nCol] = nElement;
  OBJ[nCol] = 1.0;
  Lower[nCol++] = XPRS_MINUSINFINITY; /* free column */
  Element[nElement] = -1.0;
  RowIndex[nElement++] = 0;
  nColName = nColName + 1 + sprintf(&ColNames[nColName], "OBJX");

This starts the construction of the matrix elements. nElement counts through the Element and RowIndex arrays, nCol counts through the ColStart, OBJ, Lower and Upper arrays. The first column, OBJX, has the objective function value of +1 and a value of -1 in the OBJEQ row. It is also defined to be "free", by making its lower bound equal to minus infinity.

  iRow = 0
  for (i=1; i<nSide; i++) {
    nColName = nColName + 1 + sprintf(&ColNames[nColName], "THETA%d", i);
    ColStart[nCol++] = nElement;
    if (i < nSide-1) {
      Element[nElement] = -1;
      RowIndex[nElement++] = iRow+1;
    }
    if (i > 1) {
      Element[nElement] = 1;
      RowIndex[nElement++] = iRow;
    }
    iRow++;
  }

This creates the relationships between adjacent thetas. The tests on i are to deal with the first and last thetas which do not have relationships with both their predecessor and successor.

  Upper[nCol-1] = 3.1415926;

This sets the bound on the final theta to be π. The column index is nCol-1 because nCol has already been incremented.

  nColName = nColName + 1 + sprintf(&ColNames[nColName], "=");
  ColStart[nCol] = nElement;
  Lower[nCol] = Upper[nCol] = 1.0; /* fixed at 1.0 */
  nCol++;

This creates the "equals column" – its name is "=" and it is fixed at a value of 1.0.

  for (i=1; i<nSide; i++) {
    Lower[nCol] = 0.01;         /* lower bound */
    Upper[nCol] = 1;
    ColStart[nCol++] = nElement;
    nColName = nColName + 1 + sprintf(&ColNames[nColName], "RHO%d", i);
  }
  ColStart[nCol] = nElement;

The remaining columns – the rho variables – have only non-linear coefficients and so they do not appear in the linear section except as empty columns. They are bounded between 0.01 and 1.0 but have no entries. The final entry in ColStart is one after the end of the last column.

  XPRSsetintcontrol(mprob, XPRS_MPSNAMELENGTH, 16);

If you are creating your own names – as we are here – then you need to make sure that Xpress Optimizer can handle both the names you have created and the names that will be created by Xpress NonLinear. Typically, Xpress NonLinear will create names which are three characters longer than the names you have used. If the longest name would be more than 8 characters, you should set the Xpress Optimizer name length to be larger – it comes in multiples of 8, so we have used 16 here. If you do not make the name length sufficiently large, then the XPRSaddnames function will return an error either here or during the Xpress NonLinear "construct" phase.

  XPRSloadlp(mprob, "Polygon", nCol, nRow, RowType, RHS, NULL,
    OBJ, ColStart, NULL, RowIndex, Element, Lower, Upper);

This actually loads the model into Xpress Optimizer. We are not using ranges or column element counts, which is why the two arguments are NULL.

  XPRSaddnames(mprob, 1, RowNames, 0, nRow-1);
  XPRSaddnames(mprob, 2, ColNames, 0, nCol-1);

The row and column names can now be added.