Data input and index sets

BCL requires the user to read data into their own structures or data arrays by using standard C functions for accessing data files. The functions XPRBreadarrlinecb and XPRBreadlinecb read data from data files in the diskdata format (see the documentation of the module mmetc in the Xpress Mosel Language Reference Manual for details). The first function reads (dense) data tables with all entries of the same type, the second reads tables with items of different types (such as text strings and numbers). In particular, XPRBreadlinecb is well suited to read sparse data tables that are indexed by so-called index sets. Roughly speaking, an index set is a set of items such as text strings that index data tables and other objects in the model in a clearer way than numerical values (for details refer to the `Xpress Mosel Language Reference Manual').

Data input from file

FILE *datafile;
char name[50];
double dval, dvals[5];
XPRBreadlinecb(XPRB_FGETS,datafile,200,"T,d",name,&dval);
XPRBreadarrlinecb(XPRB_FGETS,datafile,200,"d;",dvals,5);

Create a new index set

XPRBidx set1;
set1 = XPRBnewidxset(prob,"Set1",100);

Add index to a set

XPRBaddidxel(set1,"Prob1");

Accessing index sets

int size, ind;
ind = XPRBgetidxel(set1,"Prod1");
name = XPRBgetidxelname(set1,14);
name = XPRBgetidxsetname(set1);
size = XPRBgetidxsetsize(set1);

Figure 3.1: Data input from file and accessing index sets: creation of sets, addition of elements, retrieving elements, and the index set size.

A new index set is created by calling function XPRBnewidxset. Set elements are added with function XPRBaddidxel. An element of a set can be retrieved either by its name (XPRBgetidxel) or by its order number within the set (using the function XPRBgetidxelname). A data item may be part of several index sets. Function XPRBgetidxsetsize returns the current size (i.e. the number of set elements) of an index set.

The definition of index sets may be nested, that is while reading a data file the user may fill up several index sets at a time. The size of index sets grows automatically as required. The user sets some initial size at the creation of the set, but if less elements are added the size returned by XPRBgetidxsetsize will be smaller than this value and if more elements are added the size is increased accordingly.

Example

Taking the program example from the previous chapter, we now assume that we want to give names to the jobs, such as ABC14, DE45F, GH9IJ99, KLMN789. We further assume that these names, together with the durations, are given in a separate data file, durations.dat:

ABC14, 3
DE45F, 4
GH9IJ99, 2
KLMN789, 2

If data is read with function XPRBreadlinecb, it is possible to use comments (preceded by !) and line continuation signs (&) in the data file. (Note that single strings and numbers may not be written over several lines.) The input function also skips blanks and empty lines. If separator signs other than blanks are used, the value 0 may be omitted in the data file (for instance, a data line 0, 0, 0 could as well be written as , , or, using blanks as separators, 0 0 0). The following is functionally equivalent to the contents of durations.dat:

ABC14, 3       !  product1, duration1
DE45F,  &      !  this line is continued
4              !  in the next line
  GH9IJ99, 2   !  blanks are skipped
               !  as well as empty lines
KLMN789, 2

Separating the input data from the definition allows the same model to be rerun with different data sets without having to recompile the program code. To accommodate data in this form the model program must be written or edited appropriately. In the following program, a function for data input is added to the code seen in the previous chapter. The space for the decision variable arrays is allocated once the array sizes are known. Notice that we use the job names as the names of the decision variables.

#include <stdio.h>
#include <stdlib.h>
#include "xprb.h"
#define MAXNJ 4                /* Maximum number of jobs */
#define NT 10                  /* Time limit */
int NJ=0;                      /* Number of jobs read in */
double DUR[MAXNJ];             /* Durations of jobs */

XPRBidxset Jobs;               /* Job names */
XPRBvar *start;                /* Start times of jobs  */
XPRBvar **delta;               /* Binaries for start times */
XPRBvar z;                     /* Max. completion time */
XPRBprob prob;                 /* BCL problem */

void read_data(void)
{
 char name[100];
 FILE *datafile;
 Jobs = XPRBnewidxset(prob,"jobs",MAXNJ);
                               /*  Create a new index set */
 datafile=fopen("durations.dat","r");
                               /* Open data file for read access */
 while(NJ<MAXNJ) &&
       XPRBreadlinecb(XPRB_FGETS, datafile, 99, "T,d", name, &DUR[NJ]))
 { /*  Read in all (non-empty) lines up to the end of the file */
  XPRBaddidxel(Jobs,name);     /*  Add job to the index set */
  NJ++;
 }
 fclose(datafile);             /*  Close the input file */
 printf("Number of jobs read: %d\n", XPRBgetidxsetsize(Jobs));
}

void jobs_model(void)
{
 XPRBctr ctr;
 int j,t;
                               /* Create start time variables with bounds */
 start = (XPRBvar *)malloc(NJ * sizeof(XPRBvar));
 if(start==NULL)
 { printf("Not enough memory for 'start' variables.\n");
   exit(0); }
 for(j=0;j<NJ;j++)
  start[j] = XPRBnewvar(prob,XPRB_PL,"start",0,NT-DUR[j]+1);
 z = XPRBnewvar(prob,XPRB_PL,"z",0,NT);  /* Makespan var. */
                               /* Declare binaries for each job */
 delta = (XPRBvar **)malloc(NJ * sizeof(XPRBvar*));
 if(delta==NULL)
 { printf("Not enough memory for 'delta' variables.\n");
   exit(0); }
 for(j=0;j<NJ;j++)
 {
  delta[j] = (XPRBvar *)malloc(NT* sizeof(XPRBvar));
  if(delta[j]==NULL
   { printf("Not enough memory for 'delta_j' variables.\n");
    exit(0); }
  delta[j][t] = XPRBnewvar(XPRB_BV,
     XPRBnewname("delta%s_%d",XPRBgetidxelname(Jobs,j),t+1),
    0,1);
 }

 for(j=0;j<NJ;j++)              /* Calculate max. completion time  */
  XPRBnewprec(prob,"Makespan",start[j],DUR[j],z);
                                /* Precedence relation betw. jobs */
 XPRBnewprec(prob,"Prec",start[0],DUR[0],start[2]);

 for(j=0;j<NJ;j++)              /* Linking start times & binaries  */
 {
  ctr = XPRBnewctr(prob,"Link",XPRB_E);
  for(t=0;t<(NT-DUR[j]+1);t++)
    XPRBaddterm(ctr,delta[j][t],t+1);
  XPRBaddterm(ctr,start[j],-1);
 }

 for(j=0;j<NJ;j++)              /* Unique start time for each job  */
 {
  ctr = XPRBnewctr(prob,"One",XPRB_E);
  for(t=0;t<(NT-DUR[j]+1);t++) XPRBaddterm(ctr,delta[j][t],1);
  XPRBaddterm(ctr,NULL,1);
 }

 ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
 XPRBaddterm(ctr,z,1);
 XPRBsetobj(prob,ctr);          /* Set objective function */

 jobs_solve();                  /* Solve the problem */

 free(start);
 for(j=0;j<NJ;j++) free(delta[j]);
 free(delta);
}

int main(int argc, char **argv)
{
 prob=XPRBnewprob("Jobs");      /* Initialization */
 read_data();                   /* Read data from file */
 jobs_model();                  /* Define & solve the problem */
 return 0;
}