Inputting and solving a Linear Programming problem

In this chapter we take the example formulated in Chapter 2 and show how to input and solve this problem with Xpress Optimizer. In detail, we shall discuss the following topics:

• transformation of an LP model into matrix format,
• LP problem input with Xpress Optimizer,
• solving and solution output.

Chapter 3 shows how to formulate and solve this example with Mosel and Chapter 10 does the same for BCL.

Matrix representation

As a first step in the transformation of the mathematical problem into the form required by the LP problem input function of Xpress Optimizer we write the problem in the form of a table where the columns represent the decision variables and the rows are the constraints. All non-zero coefficients are then entered into this table, resulting in the problem matrix, completed by the operators and the constant terms (the latter are usually refered to as the right hand side, RHS, values).

The matrix specified to Xpress Optimizer does not consist of the full number_of_ rows x number_of_columns table; instead, only the list of non-zero coefficients is given and an indication where they are located. The superscripts in the table above indicate the order of the matrix entries in this list. The coefficient values will be stored in the array matval, the corresponding row numbers in the array rowidx, the values of the first few entries of these arrays are printed in italics to highlight them (see the code example in the following section for the full definition of these arrays). To complete this information, the array colbeg contains the index of the first entry per column and the array nelem the number of entries per column.

Implementation with Xpress Optimizer

The following C program foliolp.c shows how to input and solve this LP problem with Xpress Optimizer. We have also added printing of the solution. Before trying to access the solution, the LP problem status is checked (see the `Optimizer Reference Manual' for further explanation). To use Xpress Optimizer, we need to include the header file xprs.h.

To load a problem into Xpress Optimizer we need to perform the following steps:

1. Initialize Xpress Optimizer.
2. Create a new problem.
3. Load the matrix data.

#include <stdio.h>
#include <stdlib.h>
#include "xprs.h"

int main(int argc, char **argv)
{
 XPRSprob prob;
 int s, status;
 double objval, *sol;

 /* Problem parameters */
 int ncol = 10;
 int nrow = 3;

 /* Row data */
 char rowtype[] = {  'L','G','E'};
 double rhs[]   = {1.0/3,0.5, 1};

 /* Column data */
 double obj[] = {  5, 17, 26, 12,  8,  9,  7,  6, 31, 21};
 double lb[]  = {  0,  0,  0,  0,  0,  0,  0,  0,  0,  0};
 double ub[]  = {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3};

 /* Matrix coefficient data */
 int colbeg[]    = {0,  2,    5,    8,    11,12,13,14,15,  17,  19};
 int rowidx[]    = {1,2,0,1,2,0,1,2,0,1,2, 2, 2, 2, 2, 0,2, 0,2};
 double matval[] = {1,1,1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1,1, 1,1};

 XPRSinit(NULL);                         /* Initialize Xpress Optmizer */
 XPRScreateprob(&prob);                  /* Create a new problem */

                                         /* Load the problem matrix */
 XPRSloadlp(prob, "FolioLP", ncol, nrow, rowtype, rhs, NULL,
            obj, colbeg, NULL, rowidx, matval, lb, ub);

 XPRSchgobjsense(prob, XPRS_OBJ_MAXIMIZE);  /* Set sense to maximization */
 XPRSlpoptimize(prob, "");               /* Solve the problem */

 XPRSgetintattrib(prob, XPRS_LPSTATUS, &status);  /* Get LP sol. status */

 if(status == XPRS_LP_OPTIMAL)
 {
  XPRSgetdblattrib(prob, XPRS_LPOBJVAL, &objval); /* Get objective value */
  printf("Total return: %g\n", objval);

  sol = (double *)malloc(ncol*sizeof(double));
  XPRSgetlpsol(prob, sol, NULL, NULL, NULL);      /* Get primal solution */
  for(s=0;s<ncol;s++) printf("%d: %g%%\n", s+1, sol[s]*100);
 }

 XPRSdestroyprob(prob);                  /* Delete the problem */
 XPRSfree();                             /* Terminate Xpress */

 return 0;
}

Instead of defining colbeg with one extra entry for the last+1 column we may give the numbers of coefficients per column in the array nelem:

 /* Matrix coefficient data */
 int colbeg[]    = {0,  2,    5,    8,    11,12,13,14,15,  17};
 int nelem[]     = {2,  3,    3,    3,     1, 1, 1, 1, 2,   2};
 int rowidx[]    = {1,2,0,1,2,0,1,2,0,1,2, 2, 2, 2, 2, 0,2, 0,2};
 double matval[] = {1,1,1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1,1, 1,1};

 ...
                                         /* Load the problem matrix */
 XPRSloadlp(prob, "FolioLP", ncol, nrow, rowtype, rhs, NULL,
            obj, colbeg, nelem, rowidx, matval, lb, ub);

The seventh argument of the function XPRSloadlp remains empty for our problem since it is reserved for range information on constraints.

The second argument of the optimization function XPRSlpoptimize indicates the algorithm to be used: an empty string stands for the default LP algorithm. After solving the problem we check whether the LP has been solved and if so, we retrieve the objective function value and the primal solution for the decision variables.

Compilation and program execution

If you have followed the standard installation procedure of Xpress Optimizer, you may compile this file with the following command under Windows:

cl /MD /I%XPRESSDIR%\include %XPRESSDIR%\lib\xprs.lib foliolp.c

For Linux or Solaris use

cc -D_REENTRANT -I${XPRESSDIR}/include -L${XPRESSDIR}/lib foliolp.c -o foliolp -lxprs

For other systems please refer to the example makefile provided with the corresponding distribution.

Running the resulting program will generate the following output:

Total return: 14.0667
1: 30%
2: 0%
3: 20%
4: 0%
5: 6.66667%
6: 30%
7: 0%
8: 0%
9: 13.3333%
10: 0%

Under Unix this is preceded by the log of Xpress Optimizer:

Reading Problem FolioLP
Problem Statistics
           3 (      0 spare) rows
          10 (      0 spare) structural columns
          19 (      0 spare) non-zero elements
Global Statistics
           0 entities        0 sets        0 set members
Maximizing LP FolioLP
Original problem has:
         3 rows           10 cols           19 elements
Presolved problem has:
         3 rows           10 cols           19 elements

   Its         Obj Value      S   Ninf  Nneg        Sum Inf  Time
     0         42.600000      D      2     0        .000000     0
     5         14.066667      D      0     0        .000000     0
Uncrunching matrix
     5         14.066667      D      0     0        .000000     0
Optimal solution found

Windows users can retrieve the Optimizer log by redirecting it to a file. Add the following line to your program immediately after the problem creation:

 XPRSsetlogfile(prob, "logfile.txt");

The Optimizer log displays the size of the matrix, 3 rows (i.e. constraints) and 10 columns (i.e. decision variables), and the log of the LP solution algorithm (here: `D' for dual Simplex). The output produced by our program tells us that the maximum return of 14.0667 is obtained with a portfolio consisting of shares 1, 3, 5, 6, and 9. 30% of the total amount are spent in shares 1 and 6 each, 20% in 3, 13.3333% in 9 and 6.6667% in 5. It is easily verified that all constraints are indeed satisfied: we have 50% of North-American shares (1 and 3) and 33.33% of high-risk shares (3 and 9).