Further modeling topics

Topics covered in this chapter:

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;
}

Special Ordered Sets

Basic functions

Special Ordered Sets of type n (n=1,2) are sets of variables of which at most n may be non-zero at an integer feasible solution. Associated with each set member is a real number (weight), establishing an ordering among the members of the set. In SOS of type 2, any positive variables must be adjacent in the sense of this ordering.

XPRBsos set1, set2;
XPRBarrvar s;

Immediate (ref. constraint)

XPRBctr c;
set1=XPRBnewsosrc(prob,"sA",XPRB_S2,s,c);

Immediate (coefficients)

double C[] = {1,2,3,4};
set2=XPRBnewsosw(prob,"sB",XPRB_S1,s,C);

Consecutive definition

set2=XPRBnewsos(prob,"sB",XPRB_S1);
XPRBaddsosarrel(set2,s,C);

Delete set definition

XPRBdelsos(set2);

Accessing sets

XPRBaddsosel(set2,s[2],4,5);
XPRBdelsosel(set1,s[0]);
XPRBgetsosname(set1);
XPRBgetsostype(set2);

Figure 3.2: Defining and accessing SOS: immediate (single function) by indicating a reference constraint; or consecutive definition by adding coefficients for all members.

In BCL, Special Ordered Sets may be defined in different ways as illustrated in Figure Defining and accessing SOS. As with arrays and constraints, they may be created either with a call to a single function (see Section Array-based SOS definition), or by adding coefficients consecutively.

In the basic, incremental definition, function XPRBnewsos marks the beginning of the definition of a set. Single members are added by function XPRBaddsosel and arrays by function XPRBaddsosarrel, each time indicating the corresponding coefficients. Single elements, or an entire set definition, can be deleted with functions XPRBdelsosel and XPRBdelsos respectively. BCL also has functions to retrieve the name of a SOS and its type (XPRBgetsosname and XPRBgetsostype). It is also possible to set branching directives for a SOS (function XPRBsetsosdir), including priorities, choice of the preferred branching direction and definition of pseudo costs.

Note:

all members that are added to a SOS must belong to the same problem as the SOS itself.

Array-based SOS definition

BCL provides two functions for creating Special Ordered Sets with a single function call: XPRBnewsosrc and XPRBnewsosw. With both functions, a new SOS is created by indicating the type (1 or 2), an array of variables and the corresponding weight coefficients for establishing an ordering among the set elements. With XPRBnewsosrc, these coefficients are taken from the variables' coefficients in the indicated reference constraint. When using function XPRBnewsosw, the user directly provides an array of weight coefficients.

Example

In the previous examples, instead of defining the delta variables as binaries, the problem can also be formulated using SOS of type 1. In this case, the delta variables are defined to be continuous as the SOS1 property and their unit sum ensure that one and only one takes the value one.

XPRBprob prob;                 /* BCL problem */
XPRBvar delta[NJ][NT];	       /* Variables for start times */
XPRBsos set[NJ];

void jobs_model(void)
{
 ...
 for(j=0;j<NJ;j++)             /*  Declare a variable for each job */
  for(t=0;t<NT-DUR[j]+1;t++)   /* and for each start time */
   delta[j][t] = XPRBnewvar(prob, XPRB_PL,
                            XPRBnewname("delta%d%d",j+1,t+1), 0, 1);
 for(j=0;j<NJ;j++)
 {                             /* Create a new SOS1 */
  set[j] = XPRBnewsos(prob, "sosj", XPRB_S1);
  for(t=0;t<NT-D[j]+1;t++)     /* Add variables to the SOS */
   XPRBaddsosel(set[j], delta[j][t], t+1);
 }
}

In order to simplify the definition of the SOS one can use the model formulation with variable arrays presented in the previous chapter. The constraints Link are employed as the reference constraints to determine the weight coefficient for each variable (the constraints need to be stored in an array, Link).

XPRBprob prob;                 /* BCL problem */
XPRBarrvar delta[NJ];	       /* Sets of var.s for start times  */
XPRBsos set[NJ];

void jobs_model(void)
{
 XPRBctr Link[NJ];             /* "Link" constraints */
 ...
 for(j=0;j<NJ;j++)             /*  Declare a set of var.s for each job */
  delta[j] = XPRBnewarrvar(prob, (NT-(int)DUR[j]+1), XPRB_PL,
                           XPRBnewname("delta%d",j+1), 0, 1);

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

/* Create a SOS1 for each job using constraints "Link" as
   reference constraints */
 for(j=0;j<NJ;j++)
  set[j] = XPRBnewsosrc(prob, "sosj", XPRB_S1, delta[j], Link[j]);
}

Instead of setting directives on the binary variables, we may now define branching directives for the SOS1.

for(j=0;j<NJ;j++) XPRBsetsosdir(set[j],XPRB_DN,0);
                               /* First branch downwards on sets */

Loading solutions

Basic functions

With the Xpress Optimizer, it is possible to load external MIP solutions from memory to help the branch and bound tree search and heuristic algorithms. BCL replicates this same functionality with the XPRBloadmipsol and XPRBaddmipsol functions. In both cases, with solution we mean just the variable solution values: no objective value, slack or dual information is passed to the Optimizer as part of the solutions

.

The first function, XPRBloadmipsol, can be used when the solution values are known for all the model variables and the solution is feasible. The second one, XPRBaddmipsol, can be used even when only a partial solution is known or the "solution" is not feasible. If the provided solution is a partial solution or found to be infeasible, the Optimizer will run a limited local search heuristic in an attempt to find a close feasible integer solution.

In order to be loaded with XPRBaddmipsol, a solution must first be defined as a XPRBsol object. A new XPRBsol solution can be created with the XPRBnewsol function. Individual variables can then be added with function XPRBsetsolvar and arrays of variables with function XPRBsetsolarrvar, each time indicating the corresponding solution values. The current solution size can be obtained with XPRBgetsolsize and assigned variables can be queried or removed with functions XPRBgetsolvar and XPRBdelsolvar. Finally, the entire solution object can be deleted with function XPRBdelsol.

Note that it is also possible load external solutions from file with the XPRBreadbinsol and XPRBreadslxsol functions.

Note:

all variables that are added to a solution must belong to the same problem as the solution itself.

Example

The following code fragment shows how to create a partial solution and load it into the Optimizer with XPRBaddmipsol. It also shows how to set a callback function to receive the notification from the Optimizer on the solution loading outcome, which informs the user if the solution has been accepted and if it has been found to be feasible or required a reoptimization or local search heuristic (note that defining this callback is optional). The complete example can be found in file d1wagon2.c.

/* Callback function reporting loaded solution status */
void XPRS_CC solnotify(XPRSprob my_prob, void* my_object, const char* solname, int status)
{
  printf("Optimizer loaded solution %s with status=%d\n", solname, status);
}
	
void d1w2_solve(XPRBprob prob)
{
  int b;
  XPRBsol sol;
  ...

  /* Create a BCL solution from the heuristic solution previously found */
  sol = XPRBnewsol(prob);

  /* Set the solution values for some discrete variables */
  for (b = 0; b < NBOXES; b++) XPRBsetsolvar(sol, load[b][HeurSol[b]], 1);

  /* Send the solution to the optimizer */
  XPRBaddmipsol(prob, sol, "heurSol");

  /* Free the solution object */
  XPRBdelsol(sol);

  /* Request notification of solution status after processing */
  XPRSaddcbusersolnotify(XPRBgetXPRSprob(prob), solnotify, NULL, 0);	
  ...
}

Output and printing

BCL provides printing functions for variables, constraints, Special Ordered Sets, and index sets (XPRBprintvar, XPRBprintarrvar, XPRBprintctr, XPRBprintsos, XPRBprintidxset, XPRBprintsol) as well as the entire model definition (XPRBprintprob). Any program output may be printed with XPRBprintf in a similar way to the C function printf. The output of all functions mentioned above is intercepted by the callback XPRBdefcbmsg if this function has previously been defined by the user.

It is also possible to output the problem to a file in extended LP format or as a matrix in extended MPS format (function XPRBexportprob). Note that unlike standard LP format, the extended LP format supports Special Ordered Sets and non-standard variable types (semi-continuous, semi-integer, or partial integers). Like the standard LP format it requires the sense of the objective function to be defined.

File output

XPRBexportprob(prob,XPRB_MPS,"expl2");

Print model objects

XPRBvar y;
XPRBprintvar(y);

XPRBarrvar av;
XPRBprintarrvar(av);

XPRBctr c;
XPRBprintctr(c);

XPRBsos s;
XPRBprintsos(s);

XPRBidxset is;
XPRBprintidxset(is);

XPRBsol sol;
XPRBprintsol(sol);

Print a given problem

XPRBprintprob(prob);

Print program output

XPRBprintf("Print this text");

Compose a name string

int i = 3;
XPRBnewname("abc%d",i);

Figure 3.3: File output and printing.

Example

We may now augment the last few lines of the model definition (cmodel or cmodel_array) of our example with some output functions. Note that these output functions may be added at any time to print the current problem definition in BCL. The function XPRBprintprob prints the complete BCL problem definition to the standard output. The function XPRBexportprob writes the problem definition in LP format or as a matrix in extended MPS format to the indicated file.

XPRBprintprob(prob);         /* Print out the problem definition */
XPRBexportprob(prob,XPRB_MPS,"expl1");
                             /* Output matrix to MPS file */

Instead of printing the entire problem with function XPRBprintprob, it is also possible to display single variables or constraints as soon as they have been defined. The following modified extract of the model definition may serve as an example.

#include <stdio.h>
#include "xprb.h"

#define NJ    4              /* Number of jobs */
#define NT   10              /* Time limit */

double DUR[] = {3,4,2,2};    /* Durations of jobs   */
XPRBvar start[NJ];           /* Start times of jobs  */
XPRBprob prob;               /* BCL problem */
...
void cmodel(void)
{
 XPRBctr ctr;
 int j,t;

 prob=XPRBnewprob("Jobs");   /* Initialization */

 for(j=0;j<NJ;j++)           /* Create start time variables */
 {
  start[j] = XPRBnewvar(prob,XPRB_PL,"start",0,NT);
  XPRBprintvar(start[j]);
  XPRBprintf(", ");
 }
 ...
                             /* Precedence relation betw. jobs */
 ctr = XPRBnewprec(prob,"Prec",start[0],DUR[0],start[2]);
 XPRBprintctr(ctr);
 ...
}

Quadratic Programming with BCL

As an extension to LP and MIP, BCL also provides support for formulating and solving Quadratic Programming (QP) and Mixed Integer Quadratic Programming (MIQP) problems, that is, problems with linear constraints with a quadratic objective function of the form

c^Tx + x^TQx

where x is the vector of decision variables, c is the cost vector, and Q is the quadratic cost coefficient matrix. The matrix Q must be symmetric. It should also be positive semi-definite if the problem is to be minimized, and negative semi-definite if it is to be maximized, because the Xpress Optimizer solves convex QP problems. If the problem is not convex, the solution algorithms may not converge at all, or may only converge to a locally optimal solution.

Release 4.0 of BCL extends this functionality to Quadratically Constrained Quadratic Programming (QCQP) problems, that is, problems that in addition to a quadratic objevctive function have constraints of the form

a^Tx + x^TQx ≤ b

where a is the coefficient vector for the linear terms, b the constant RHS value, and the same conditions as in objective functions apply to the quadratic coefficient matrix Q (positive semi-definite in ≤ constraints, and negative semi-definite in ≥ constraints). Quadratic constraints in QCQP problems must be inequalities.

Any other quadratic form supported by the Xpress Optimizer can also be used, e.g. Second Order Cone constraints in Second Order Cone problems (SOCPs).

Add quadratic term

XPRBctr c;
XPRBvar x1;
XPRBaddqterm(c,x1,x1,3);

Set quadratic term

XPRBvar x2;
XPRBsetqterm(c,x1,x2,-7.2);

Delete a quadratic term

XPRBdelqterm(c,x2,x1);

Enumerate quadratic terms

double coeff;
const void *ref;
ref = XPRBgetnextqterm(c,ref,&x1,&x1,&coeff);

Figure 3.4: Defining and accessing quadratic terms in BCL.

In BCL, the quadratic part of constraints is defined termwise, much like what we have seen for the definition of linear constraints in Section Constraints. The coefficient of a quadratic term is either set to a given value (XPRBsetqterm) or its value is augmented by the given value (XPRBaddqterm). Quadratic objective functions are set in the same way as linear ones with a call to XPRBsetobj. Note that the definition of the quadratic constraint terms should always be preceded by the definition of the corresponding variables.

The coefficient of a quadratic constraint term can be retrieved with XPRBgetqcoeff. The quadratic terms of a constraint can be enumerated with XPRBgetnextqterm.

Functions XPRBprintprob, XPRBprintobj, XPRBexportprob, and XPRBprintctr will print or output to a file the complete problem / constraint definition, including the quadratic terms.

Example

We wish to distribute a set of points represented by tuples of x-/y-coordinates on a plane minimizing the total squared distance between all pairs of points. For each point i we are given a target location (CX_i,CY_i) and the (square of the) maximum allowable distance R_i to this location.

In mathematical terms, we have two decision variables x_i and y_i for the coordinates of every point i. The objective to minimize the total squared distance between all points is expressed by the following sum.

N-1

∑

i=1

N

∑

j=i+1

((x_i-x_j)² + (y_i-y_j)²)

For every point i we have the following quadratic inequality.

(x_i-CX_i)² + (y_i-CY_i)² ≤ R_i

The following BCL program (xbairport.c) implements and solves this problem.

#include <stdio.h>
#include "xprb.h"

#define N 42
double CX[N], CY[N], R[N];

...                                   /* Initialize the data arrays */

int main(int argc, char **argv)
{
 int i,j;
 XPRBprob prob;
 XPRBvar x[N],y[N];                /* x-/y-coordinates to determine */
 XPRBctr cobj, c;

 prob=XPRBnewprob("airport");    /* Initialize a new problem in BCL */

/**** VARIABLES ****/
 for(i=0;i<N;i++)
  x[i] = XPRBnewvar(prob, XPRB_PL, XPRBnewname("x(%d)",i), -10, 10);
 for(i=0;i<N;i++)
  y[i] = XPRBnewvar(prob, XPRB_PL, XPRBnewname("y(%d)",i), -10, 10);

/****OBJECTIVE****/
/* Minimize the total distance between all points */
 cobj = XPRBnewctr(prob, "TotDist", XPRB_N);
  for(i=0;i<N-1;i++)
   for(j=i+1;j<N;j++)
   {
    XPRBaddqterm(cobj, x[i], x[i], 1);
    XPRBaddqterm(cobj, x[i], x[j], -2);
    XPRBaddqterm(cobj, x[j], x[j], 1);
    XPRBaddqterm(cobj, y[i], y[i], 1);
    XPRBaddqterm(cobj, y[i], y[j], -2);
    XPRBaddqterm(cobj, y[j], y[j], 1);
   }
 XPRBsetobj(prob, cobj);             /* Set the objective function */

/**** CONSTRAINTS ****/
/* All points within given distance of their target location */
 for(i=0;i<N;i++)
 {
  c = XPRBnewctr(prob, XPRBnewname("LimDist_%d",i), XPRB_L);
  XPRBaddqterm(c, x[i], x[i], 1);
  XPRBaddterm(c, x[i], -2*CX[i]);
  XPRBaddterm(c, NULL, -CX[i]*CX[i]);
  XPRBaddqterm(c, y[i], y[i], 1);
  XPRBaddterm(c, y[i], -2*CY[i]);
  XPRBaddterm(c, NULL, -CY[i]*CY[i]);
  XPRBaddterm(c, NULL, R[i]);
 }

/****SOLVING + OUTPUT****/
 XPRBsetsense(prob, XPRB_MINIM);          /* Sense of optimization */
 XPRBlpoptimize(prob,"");                     /* Solve the problem */

 printf("Solution: %g\n", XPRBgetobjval(prob));
 for(i=0;i<N;i++)
  printf(" %d: %g, %g\n", i, XPRBgetsol(x[i]), XPRBgetsol(y[i]));

 return 0;
}

User error handling

In this section we use a small, infeasible problem to demonstrate how the error handling and all printed messages produced by BCL can be intercepted by the user's program. This is done by defining the corresponding BCL callback functions and changing the error handling flag. If error handling by BCL is disabled, then the definition of the error callback replaces the necessity to check for the return values of the BCL functions called by a program.

User error handling may be required if a BCL program is embedded in some larger application or if the program is run under Windows from an application with windows. In all other cases it will usually be sufficient to use the error handling provided by BCL.

#include <stdio.h>
#include <setjmp.h>
#include <string.h>
#include "xprb.h"

jmp_buf model_failed;             /* Marker for the longjump */

void modinf(XPRBprob prob)
{
 XPRBvar x[3];
 XPRBctr ctr[2], cobj;
 int i;

 for(i=0;i<2;i++)                 /* Create two integer variables */
  x[i]=XPRBnewvar(prob, XPRB_UI, XPRBnewname("x_%d",i),0,100);
                                  /* Create the constraints:
                                     C1: 2x0 + 3x1 >= 41
                                     C2:  x0 + 2x1  = 13 */
 ctr[0]=XPRBnewctr(prob,"C1",XPRB_G);
 XPRBaddterm(ctr[0],x[0],2);
 XPRBaddterm(ctr[0],x[1],3);
 XPRBaddterm(ctr[0],NULL,41);

 ctr[1]=XPRBnewctr(prob,"C2",XPRB_E);
 XPRBaddterm(ctr[1],x[0],1);
 XPRBaddterm(ctr[1],x[1],2);
 XPRBaddterm(ctr[1],NULL,13);

/* Uncomment the following line to cause an error in the model
   that triggers the user error handling: */
/* x[2]=XPRBnewvar(prob, XPRB_UI, "x_2", 10, 1); */

                                  /* Objective: minimize x0+x1 */
 cobj = XPRBnewctr(prob,"OBJ",XPRB_N);
 for(i=0;i<2;i++) XPRBaddterm(cobj, x[i], 1);
 XPRBsetobj(prob,cobj);           /* Select objective function */
 XPRBsetsense(prob,XPRB_MINIM);   /* Obj. sense: minimization */

 XPRBprintprob(prob);             /* Print current problem */

 XPRBlpoptimize(prob,"");         /* Solve the LP */
 XPRBprintf(prob,
   "problem status: %d  LP status: %d  MIP status: %d\n",
    XPRBgetprobstat(prob), XPRBgetlpstat(prob),
    XPRBgetmipstat(prob));

/* This problem is infeasible, that means the following command
   will fail. It prints a warning if the message level is at
   least 2 */
 XPRBprintf(prob, "Objective: %g\n", XPRBgetobjval(prob));

 for(i=0;i<2;i++)                 /* Print solution values */
  XPRBprintf(prob, "%s:%g, ", XPRBgetvarname(x[i]),
             XPRBgetsol(x[i]));
 XPRBprintf(prob, "\n");
}

/**** User error handling function ****/
void XPRB_CC usererror(XPRBprob prob, void *vp, int num,
                       int type, const char *t)
{
 printf("BCL error %d: %s\n", num, t);
 if(type==XPRB_ERR) longjmp(model_failed,1);
}

/**** User printing function ****/
void XPRB_CC userprint(XPRBprob prob, void *vp, const char *msg)
{
 static int rtsbefore=1;

    /* Print 'BCL output' whenever a new output line starts,
       otherwise continue to print the current line. */
 if(rtsbefore)
  printf("BCL output: %s", msg);
 else
  printf("%s",msg);
 rtsbefore=(msg[strlen(msg)-1]=='\n');
}

int main(int argc, char **argv)
{
 XPRBprob prob;

 XPRBseterrctrl(0);              /* Switch to error handling by the
                                    user's program */
 XPRBsetmsglevel(NULL,2);        /* Set the printing flag to
                                    printing errors and warnings */
 XPRBdefcbmsg(NULL, userprint, NULL);
                                 /* Define the printing callback func. */

 if((prob=XPRBnewprob("ExplInf"))==NULL)
 {                               /* Initialize a new problem in BCL */
  fprintf(stderr,"I cannot create the problem\n");
  return 1;
 }
 else
  if(setjmp(model_failed))       /* Set a marker at this point */
  {
   fprintf(stderr,"I cannot build the problem\n");
   XPRBdelprob(prob);           /* Delete the part of the problem
                                   that has been created */
   XPRBdefcberr(prob, NULL, NULL);
                                /* Reset the error callback */
   return 1;
  }
  else
  {
   XPRBdefcberr(prob, usererror, NULL);
                                /* Define the error handling callback */
    modinf(prob);               /* Formulate and solve the problem */
   XPRBdefcberr(prob, NULL, NULL);
                                /* Reset the error callback */
   return 0;
  }
}

Since this example defines the printing level and the printing callback function before creating the problem (that is, before BCL is initialized), we pass NULL as first argument.

Efficent modeling with BCL

This section discusses some recommendations for the efficient use of BCL. Such considerations are particularly important when working with large-size optimization problems or when solving a large number of models / model instances in a single application. Our criteria for measuring efficiency are:

• model execution speed
• memory consumption

Please note that this section is only concerned with modeling aspects. For issues relating to the solving process, such as the performance of the underlying optimization algorithms, the reader is refered to the Xpress Optimizer Reference Manual.

Names dictionaries

BCL works with two names dictionaries, the main names dictionary (storing the names of constraints, decision variables, etc.) and a dedicated dictionary for index set elements. The former is active by default wheras the latter gets activated only if a model uses index sets. The following remarks refer principally to the names dictionary.

Disabling the names dictionary

If an application does not make use of the names of modeling objects the names dictionary can be disabled to save memory. The function XPRBsetdictionarysize for resetting the dictionary size can only be called immediately after the creation of the corresponding problem. Once the dictionary has been disabled it cannot be enabled any more. All methods relative to the names cannot be used if this dictionary has been disabled and BCL will not generate any unique names at the creation of model objects.

• C:  XPRBsetdictionarysize(prob, XPRB_DICT_NAMES, 0);
• C++:  XPRBprob.setDictionarySize(XPRB_DICT_NAMES, 0);
• Java:  XPRBprob.setDictionarySize(XPRB.DICT_NAMES, 0);
• C#:  XPRBprob.setDictionarySize(BCLconstant.DICT_NAMES, 0);

Setting the names dictionary size

If you wish to use the names dictionary we recommend to choose a size close to the number of variables+constraints in your problem, preferrably a prime number. (Too small values will slow down access to the names dictionary, larger values imply higher memory usage.)

Handling of problems

Resetting a problem

You should reset a problem to free up memory if the solution information is no longer required (function XPRBresetprob). Resetting a problem deletes any solution information stored in BCL; it also deletes the corresponding Xpress Optimizer problem and removes any auxiliary files that may have been created by optimization runs.

• C:  XPRBresetprob(prob);
• C++/Java/C#:  XPRBprob.reset();

Other functions for freeing memory of auxiliary/intermediate structures: XPRBcleardir, XPRBdelarrvar, XPRBdelbasis, XPRBdelcut

Releasing a problem

With C a problem may be deleted explicictly (XPRBdelprob) to free up all memory used by it. In the object-oriented interfaces make sure to release all references to a problem to enable garbage collection on the object.

The Java interface also publishes the problem finalizer: XPRBprob.finalize().

Constraint definition

Object-oriented interfaces

Overloaded operators and the more algebraic-style definition of constraints via expressions in the object-oriented interfaces of BCL lead to more easily human-readable models but unfortunately, they also create many intermediate objects, making them computationally less efficient. With constraint/expression sizes upwards of 1000 terms a slowdown tends to become noticeable and alternative ways of constraint formulation should be sought.

The best alternative is to use the addTerm and setTerm methods for constraints or expressions (these avoid the creation of intermediate objects, such as terms or expressions, thus reducing memory consumption and most often leading to a speed up).

Example:

• C++:
  Replace
    ctr += 17*x;
  by
    ctr.addTerm(17, x);
• Java:
  Replace
    ctr.add(x.mul(17));
  by
    ctr.addTerm(x, 17); // or: ctr.addTerm(17, x);

Order of enumeration

In pre-Release 2008 versions of BCL it is recomended to enumerate / access decision variables within loops in the order of their creation. This recommendation does not apply to BCL 4.0 and newer.