Modeling with BCL

Topics covered in this chapter:

This chapter gives an introduction to common BCL functions using BCL in the C language. Chapters BCL in C++ and BCL in Java provide versions of the program examples in this chapter for the C++ and Java interfaces of BCL respectively. Available functionality for building up constraint expressions with the object-oriented interfaces differs from what is shown here for C and there are also some specifities concerning the initialization of BCL with the different interfaces.

Problem handling

Initialization and termination

Prototypes for all BCL functions are contained in the header file, xprb.h, which needs to be included at the top of any program which makes BCL function calls. The first stage in the model building process is to initialize BCL, either explicitly with a call to XPRBinit or implicitly by creating a new problem with function XPRBnewprob (see below). During its initialization BCL also initializes the Xpress Optimizer, so if the two are to be used together, a separate call to XPRSinit is unnecessary (for further detail on using Optimizer functionality with BCL please refer to Appendix Using BCL with the Optimizer library). The initialization function checks for any necessary libraries, and runs security checks to determine license information about your Xpress installation.

Once models have been constructed and BCL routines are no longer needed, the function XPRBfree may be called to reset BCL.

Problem creation and deletion

BCL has an object-oriented design. A mathematical model is represented in BCL by a problem that contains a collection of other objects (variables, constraints, index set etc). Every BCL function takes as the first argument the object it operates on.

A problem reference in BCL is a variable of type XPRBprob. A problem is created using the XPRBnewprob function, additionally providing a problem name, in the following way:

XPRBprob prob;
   ...
prob = XPRBnewprob("MyProb");

The problem reference, prob, is subsequently provided as the first argument to functions operating on the problem.

Once use of a particular problem has ended, the problem should be removed using XPRBdelprob, freeing associated resources. It should be noted that resources associated with problems are not released with a call to XPRBfree, so failure to explicitly delete each problem may result in memory leakage. It is also possible to delete just the solution information stored by BCL after an optimization run (including all problem-related information loaded in Xpress Optimizer), if the definition of the problem is to be kept for later re-use but its solution data is not required any longer (function XPRBresetprob).

Initialize a new model

XPRBprob pb1;
...
pb1 = XPRBnewprob("Problem1");

Delete problem definition

XPRBdelprob(pb1);

Delete solution information

XPRBresetprob(pb1);

Load problem matrix

XPRBloadmat(pb1);

Fix column ordering

XPRBsetcolorder(pb1,1);

Get problem name

XPRBgetprobname(pb1);

Change problem name

XPRBsetprobname(pb1,"ProbOne");

Figure 2.1: Creating, accessing and deleting problems in BCL

Note that for every BCL problem of type XPRBprob exists a corresponding Xpress Optimizer problem (type XPRSprob). Although it is usually not necessary to access the optimizer problem directly in BCL programs, this may be required for certain advanced uses (see Appendix Using BCL with the Optimizer library for more detail).

Other basic functions

Other functions are also useful for problem handling and manipulation. With XPRBgetprobname, the name for a particular problem specified by a reference may be obtained, and with XPRBsetprobname it can be changed.

The function XPRBloadmat is really only needed by Optimizer library users. It explicitly transforms the BCL problem into the matrix representation in the Optimizer, passing the problem directly into the Optimizer. Usually this is done automatically by BCL whenever required, but it may be necessary to load the matrix without optimizing immediately, e.g. so that an advance basis can be loaded before starting the optimization. The matrix generated by BCL remains unchanged in repeated executions of the program; the column ordering criterion may be changed by setting the ordering flag to 1 (function XPRBsetcolorder) before the matrix is loaded.

Input and output settings

BCL supports a number of functions for directing the input and output of a program. Those functions are independent of the particular problem and consequently do not take the problem pointer as an argument or may be used with a NULL argument. They may be called prior to the creation of any problem using XPRBnewprob, and even prior to the initialization of BCL. Any other BCL function will result in an error if it is executed before BCL has been initialized.

Printout of BCL status information, warnings or error messages may be turned off (function XPRBsetmsglevel). With function XPRBdefcbmsg, the user may define the message callback function to intercept all output printed by BCL (including messages from the Optimizer library and output from the user's program printed with function XPRBprintf, the latter not being influenced by the setting of the message print level). Section User error handling in the next chapter shows an example of a message callback.

The formating of real numbers used by the BCL output functions (including matrix export) can be set with the function XPRBsetrealfmt.

For data input in BCL (using functions XPRBreadlinecb and XPRBreadarrlinecb), it is possible to switch from the (default) Anglo-American standard of using a decimal point to some other character, such as a decimal comma (XPRBsetdecsign).

Set number format

XPRBsetrealfmt(prob, "%8.4f");

Set decimal sign

XPRBsetdecsign(',');

Set printout level

XPRBsetmsglevel(prob,1);

Set error handling

XPRBseterrctrl(0);

Error handling callback

void myerror(XPRBprob my_prob, void *my_object, int num,
int type, const char *txt);
XPRBdefcberr(prob,myerror,object);

Printing callback

void myprint(XPRBprob my_prob, void *my_object, const char *msgtext);
XPRBdefcbmsg(prob,myprint,object);

Get version number

const char *version;
version = XPRBgetversion();

Figure 2.2: Input and output settings, and error handling in BCL

Error handling

By default, BCL stops the program execution if an error occurs. With function XPRBseterrctrl the user may change this behavior: the error messages are still produced but the user's program has to provide the error handling. This setting may be useful, for instance, if an BCL program is embedded into some other application or executed under Windows.

Error handling by the user's program may either be implemented by checking the return values of all BCL functions, or preferably, by defining a callback (with function XPRBdefcberr) to intercept all warnings and errors produced by BCL. This function is not influenced by XPRBsetmsglevel, that is the user may turn off message printing and still be notified about any errors that occur. Section User error handling in the next chapter shows an example of an error callback.

When reporting problems with the software, the user should always give the version of BCL. This information can be obtained with the function XPRBgetversion.

Variables

Basic functions

In BCL, variables are created one-by-one with a call to the function XPRBnewvar. These variables may belong to multi-dimensional arrays declared within C. Since one-dimensional arrays of variables are used as input to a number of functions, BCL also provides a specific object for this purpose, the type XPRBarrvar. This object stores a one-dimensional array of variables together with information about its size. That means such an array of variables may be used as a parameter to a function without having to specify its size separately. Details on specific functions for creating and accessing variable arrays are given in the following Section Variable arrays.

The length of variable names (like the names of all BCL objects) is unlimited. If no name is specified the system generates default names ("VAR" followed by an index). A name may occur repeatedly and, if so, BCL starts indexing the name, commencing with an index of 0.

All types of branching directives available in Xpress can be set via the function XPRBsetvardir, including priorities, choice of the preferred branching direction and definition of pseudo costs. Bounds on variables are redefined by functions XPRBsetub, XPRBsetlb, XPRBfixvar, and XPRBsetlim. Function XPRBsetlim only applies to partial integer, semi-continuous and semi-integer variables, setting the lower bound of the continuous part or the semi-integer lower bound. Function XPRBgetbyname retrieves variables or arrays of variables via their name. Information on variables can be accessed with function XPRBgetvarname, XPRBgetvartype, XPRBgetcolnum, XPRBgetbounds, and XPRBgetlim. Function XPRBsetvartype changes the variable type. Figure Functions for creation, update, deletion and access of variables within BCL gives an overview of functions related to the creation, update and deletion of variables and arrays of variables.

Creating variables

XPRBvar y, s[4];
y = XPRBnewvar(prob,XPRB_PL,"y",1,10);
for(i=0;i<4;i++)
s[i]=XPRBnewvar(prob,XPRB_UI,"st",1,10);

Creating variable arrays

XPRBarrvar av1, av2;
av1=XPRBnewarrvar(prob,5,XPRB_SC,"a1",0,7);
av2=XPRBstartarrvar(prob,3,"a2");
XPRBapparrvarel(av2,y);
XPRBsetarrvarel(av2,2,s[3]);
XPRBendarrvar(av2);

Accessing variables

double ubd, lbd, lim;
XPRBgetvarname(y);
XPRBgetvartype(s[1]);
XPRBgetcolnum(av2[0]);
XPRBgetbounds(y,&lbd,&ubd);
XPRBgetlim(y,&lim);
XPRBsetvartype(av1[1],XPRB_BV);

Accessing arrays

XPRBgetarrvarname(av2);
XPRBgetarrvarsize(av1);

Delete a variable array

XPRBdelarrvar(av2);

Find by name

XPRBvar y1; XPRBarrvar a1;
y1 = XPRBgetbyname(prob,"y",XPRB_VAR);
a1 = XPRBgetbyname(prob,"a1",XPRB_ARR);

Branching directives

XPRBsetvardir(s[0],PR,1);
XPRBcleardir(prob);

Setting bounds

XPRBsetlb(y,4);
XPRBsetub(s[0],9);
XPRBfixvar(av[2],6);
XPRBsetlim(y,5);

Figure 2.3: Functions for creation, update, deletion and access of variables within BCL

Variable arrays

BCL provides a specific object for representing one-dimensional arrays of variables, as these are used as input to a number of functions. Variable arrays can be created either in one go, with a single function call to XPRBnewarrvar, or incrementally by copying single references to previously defined variables into an array of type XPRBarrvar.

If a variable array is created by a call to XPRBnewarrvar, all of the variables in the array receive the same type and bounds (these can be modified individually following creation). Otherwise, if the array is being defined incrementally, any previously defined variables (including elements of variable arrays) may be added to the array in an arbitrary order. In this case, the definition of the array is started by indicating its model name and size in XPRBstartarrvar and terminated by XPRBendarrvar. Entries can be positioned via XPRBsetarrvarel or simply placed at the first available free position by XPRBapparrvarel. For instance, assume we have defined four continuous variables s[0],..., s[3] and a binary variable b. We may then wish to create an array av with the following three elements: av[0] = b, av[1] = s[2], av[2] = s[0]. Regrouping different variables this way into a single data structure may help render the formulation of constraints or the access to information about model objects more transparent.

A variable may be copied into several arrays (function XPRBsetarrvarel or XPRBapparrvarel), but it is created only once as a variable or part of a variable array (using function XPRBnewvar or XPRBnewarrvar).

Function XPRBgetbyname retrieves arrays of variables via their name. It is also possible to obtain the name of an array (XPRBgetarrvarname) and its size, that is, the number of variables it contains (XPRBgetarrvarsize).

Note:

all variables that are added to an array of variables must belong to the same problem as the array itself.

Constraints

Basic functions

Constraints are created either by a call to a specialized constraint function (see Section Predefined constraint functions) or by subsequently adding all the desired terms to a constraint. In the latter case, a new constraint is started with function XPRBnewctr by indicating its type and (optionally) its name, variable and constant terms are added with functions XPRBaddterm, XPRBsetterm and XPRBaddarrterm. Function XPRBaddterm adds the indicated coefficient value to the coefficient of the variable, whereas XPRBsetterm overrides any previously defined coefficient for the variable in the constraint. It is also possible to add an entire array of variables at once to a constraint, together with the corresponding coefficients (function XPRBaddarrterm). Figure Constraint definition gives some examples of constraint creation.

Currently defined coefficients of linear constraint terms can be retrieved with XPRBgetcoeff, for a single term, or the terms can be enumerated with XPRBgetnextterm.

∑_i=0³ s_i ≤ 20

XPRBctr ctr

XPRBnewsum(prob,"S1",s,XPRB_L,20);

ctr = XPRBnewctr(prob,"S1",XPRB_L);
for(i=0;i<=3;i++)
XPRBaddterm(ctr,s[i],1);
XPRBaddterm(ctr,NULL,20);

∑_i=0³ D_i · s_i = 9

XPRBnewarrsum(prob,"S2",s,D, XPRB_E,9);

ctr = XPRBnewctr(prob,"S2",XPRB_E);
XPRBaddarrterm(ctr,s,D);
XPRBaddterm(ctr,NULL,9);

s₀ + D₀ ≤ y

XPRBnewprec(prob,"Prc",s[0],D[0],y);

ctr=XPRBnewctr(prob,"Prc",XPRB_L);
XPRBaddterm(ctr,s[0],1);
XPRBaddterm(ctr,y,-1);
XPRBaddterm(ctr,NULL,-D[0]);

Figure 2.4: Constraint definition using the constraint functions provided by BCL (left column) or by adding coefficients (right column)

Since all functions for constraint definition identify the corresponding constraint via its model name, constraint definitions may be nested.

The length of constraint names is unlimited. If no name is specified the system generates default names ("CTR" followed by an index). A name may occur repeatedly and if so, BCL starts indexing the name, commencing with an index of 0. Variables and variable arrays used in the definition of a constraint must be defined previously. Any other variables not occurring in this constraint may be defined later in the model.

After a constraint has been defined, its type may be changed to a range constraint by indicating the lower and upper bounds in a call to function XPRBsetrange. Function XPRBgetbyname retrieves constraints via their name and function XPRBgetnextctr can be used to enumerate all constraints defined in a problem.

A coefficient can be deleted with XPRBdelterm, or an entire constraint definition by XPRBdelctr. It is possible to retrieve the constraint name (XPRBgetctrname), the matrix row index (XPRBgetrownum), the constraint size (XPRBgetctrsize), the constraint type (XPRBgetctrtype), the range values (XPRBgetrange, only applicable to ranged constraints) and right hand side value (XPRBgetrhs), as well as changing the constraint type (XPRBsetctrtype). A constraint can be transformed into a model cut (XPRBsetmodcut) and function XPRBgetmodcut indicates whether a constraint has been defined as a model cut. Similarly, a constraint can be transformed into a delayed row, include vars or indicator constraint with functions XPRBsetdelayed, XPRBsetincvars or XPRBsetindicator; and it can be checked if a constraint is of these types with functions XPRBgetdelayed, XPRBgetincvars and XPRBgetindicator.

In addition to the functions for handling linear constraints listed here, BCL also lets you define quadratic constraints for the formulation of QP and QCQP problems, see Section Quadratic Programming with BCL for further detail.

Note:

all terms that are added to a constraint must belong to the same problem as the constraint itself.

Set objective function

XPRBctr c;
XPRBsetobj(prob,c);

Set objective sense

XPRBsetsense(prob,XPRB_MAXIM);

Access objective sense

int dir;
dir = XPRBgetsense(prob);

Locate constraint

XPRBctr c;
c = XPRBgetbyname(prob,"Sum1",XPRB_CTR);

Enumerate constraints

XPRBctr c = NULL;
c = XPRBgetnextctr(prob,c);

Define range constraint

XPRBsetrange(c,1,5,15);

Delete a constraint

XPRBdelctr(c);

Delete a constraint term

XPRBvar y;
XPRBdelterm(c,y);

Accessing constraints

double bdl, bdu;
XPRBgetctrname(c);
XPRBgetrange(c,&bdl,&bdu);
XPRBgetrownum(c);
XPRBgetctrsize(c);
XPRBgetctrtype(c);
XPRBsetctrtype(c,XPRB_L);

Enumerate constraint terms

double coeff; const void *ref;
ref = XPRBgetnextterm(c,ref,&y,&coeff);

Special constraints

XPRBgetmodcut(c);
XPRBsetmodcut(c,1);
XPRBgetdelayed(c);
XPRBsetdelayed(c,1);
XPRBgetincvars(c);
XPRBsetincvars(c,1);
XPRBgetindicator(c);
XPRBgetindvar(c);
XPRBsetindicator(c,1,y);

Figure 2.5: Defining the objective function and functions for modifying and accessing constraints

Predefined constraint functions

Besides the functions described above for defining constraints incrementally, BCL also provides some predefined constraint functions for formulating constraints `in one go'. The function XPRBnewarrsum creates a standard linear constraint with the indicated coefficients. The function XPRBnewsum creates a straight sum of the variables with each coefficient set to one. The function XPRBnewprec creates a so-called precedence constraint in which a variable plus a constant are less than or equal to a second variable (typically, this relation is established between start time variables in scheduling problems, hence the name).

Objective function

The objective function (Figure Defining the objective function and functions for modifying and accessing constraints) may be interpreted as a special type of constraint. It is defined like any other constraint, usually choosing the constraint type XPRB_N. But it is also possible to take a constraint of any other type. In the latter case, the variable terms of the constraint form the objective function but the equation or inequality expressed by the constraint also remains part of the problem. The objective function is declared via functions XPRBsetobj. If a different objective has been defined previously, it is replaced by the new choice.

The sense of the objective function can be set to be minimization (default) or maximization with function XPRBsetsense. Function XPRBgetsense returns the sense of the objective function.

All solution functions (XPRBlpoptimize, XPRBmipoptimize) and the problem output with XPRBexportprob require the objective to be defined. If the sense of the optimization has not been set, the problem is minimized by default.

Solving and solution information

As well as enabling model definition, BCL also provides common solving and solution information functions, as summarized in Figure Solving and solution information. For more advanced tasks the user may employ the corresponding Optimizer library functions, once the matrix has been loaded into the Optimizer (function XPRBloadmat). However, only the BCL functions can reference the BCL model objects when retrieving the solution information.

Solve active problem

XPRBlpoptimize(prob,"p");
XPRBmipoptimize(prob,"");

Status information

XPRBgetprobstat(prob);
XPRBgetlpstat(prob);
XPRBgetmipstat(prob);

Get objective value

XPRBgetobjval(prob);

Load solutions

int ncol; double *d; XPRBsol s;
XPRBloadmipsol(prob,d,ncol,1);
XPRBaddmipsol(prob,s);

Solution reading and writing

XPRBreadbinsol(prob,"","");
XPRBreadslxsol(prob,"","");
XPRBwritesol(prob,"","");
XPRBwritebinsol(prob,"","");
XPRBwriteprtsol(prob,"","");
XPRBwriteslxsol(prob,"","");

Solution information

XPRBvar y; XPRBctr c;
XPRBgetsol(y); XPRBgetdual(c);
XPRBgetrcost(y); XPRBgetslack(c);
XPRBgetact(c);

Ranging information

XPRBgetvarrng(y,XPRB_UCOST);
XPRBgetctrrng(c,XPRB_LOACT);

Fix MIP entities

XPRBfixmipentities(prob,1);

Advanced bases

XPRBbasis b;
b=XPRBsavebasis(prob);
XPRBloadbasis(b);
XPRBdelbasis(b):

Figure 2.6: Solving and solution information

Before any solution function is called, the objective function must be selected using XPRBsetobj. It is also required to set the sense of the objective, that is, whether to minimize (default) or to maximize the objective. All solution functions XPRBlpoptimize, and XPRBmipoptimize can be parameterized to choose the type of solution algorithm. Once the problem has been solved, the following solution information can be obtained: the optimal objective function value (XPRBgetobjval), values for all the problem variables (XPRBgetsol), slack values (XPRBgetslack), reduced costs (XPRBgetrcost, LP only), constraint activity (XPRBgetact), and dual values (XPRBgetdual, LP only). It is also possible to obtain ranging information for variables (XPRBgetvarrng) and constraints (XPRBgetctrrng) after solving an LP problem.

If the objective function value or solution information for variables or constraints is accessed during the optimization (for instance from Xpress Optimizer callbacks) the solution information in BCL needs to be updated with a call to XPRBsync with the parameter XPRB_XPRS_SOL or XPRB_XPRS_SOLMIP (see Appendix Using BCL with the Optimizer library for more detail).

Before solving or accessing solution information it may be helpful to check the current problem and/or solution status (using functions XPRBgetprobstat, XPRBgetlpstat and XPRBgetmipstat). It may happen that a variable defined in the model does not appear in any constraint, or a constraint only contains 0-valued coefficients so that is ignored when loading the problem into the Optimizer. In these cases the object's column or row index is negative and no solution information can be obtained. It is possible to force the loading of some variables into the Optimizer by creating a type XPRB_N constraint, adding the variables to this constraint (with any non-zero coefficients) and setting the constraint to be an include vars constraint with XPRBsetincvars. Include vars constraints are not loaded into the Optimizer but all variables they contain are always loaded (even if they don't appear in other constraints).

When solving MIP problems, the function XPRBfixmipentities fixes all the MIP entities to the values of the last found MIP solution. This is useful for example for finding the reduced costs of the continuous variables after the discrete variables have been fixed to their optimal values.

It is possible to load solutions from memory with function XPRBloadmipsol, which loads a solution into BCL or the Optimizer, or XPRBaddmipsol which can also load partial or infeasible solutions into the Optimizer. Solutions can also be written and read from file with XPRBwritesol, XPRBwritebinsol, XPRBwriteprtsol, XPRBwriteslxsol, XPRBreadslxsol.

With BCL, it is also possible to save the current basis of a problem in memory and reload (and/or delete) it after some changes have been carried out to the problem. These changes may include, for instance, the addition or deletion of variables and constraints.

For more advanced functionality using Optimizer library functions refer to the Optimizer Reference Manual.

Example

The following example is an extract of a scheduling problem: four jobs with different durations need to scheduled with the objective to minimize the makespan (= completion time of the last job). The complete model also includes resource constraints that are omitted here for clarity's sake. For every job j its duration DUR_j is given. We define decision variables startj representing the start time of jobs and binary variables delta_jt indicating whether job j starts in time period t (delta_jt=1). We also define a variable z for the maximum makespan. The makespan can be expressed as a `dummy job' of duration 0 that is the successor of all other jobs (constraints Makespan in the model below). We also formulate a precedence relation between two jobs (constraint Prec). The start time variables need to be linked to the binary variables (constraints Link). And finally, the binary variables are used to express that every job has a unique start time (constraints One).

Model formulation using basic functions

#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  */
XPRBvar delta[NJ][NT];       /* Binaries for start times */
XPRBvar z;                   /* Max. completion time */
XPRBprob prob;               /* BCL problem */

void jobs_model(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);
 z = XPRBnewvar(prob, XPRB_PL, "z", 0, NT);  /* Makespan var. */

 for(j=0;j<NJ;j++)           /* Declare binaries for each job  */
  for(t=0;t<(NT-DUR[j]+1);t++)
   delta[j][t] = XPRBnewvar(prob, XPRB_BV, "delta", 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 */

                             /* Upper bounds on start time variables */
 for(j=0;j<NJ;j++) XPRBsetub(start[j], NT-DUR[j]+1);
} 

Using variable arrays

In the subsequent code, we replace the variables start_j and delta_jt by arrays of variables start and delta_j. Note that the variables can still be addressed in the same way as before. The main advantage of this formulation is that now some of the predefined constraint functions may be used in the model definition. Changes to the previous version are highlighted in bold.

#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   */
XPRBarrvar start;            /* Start times of jobs  */
XPRBarrvar delta[NJ];        /* Sets of binaries */
XPRBvar z;                   /* Maxi. completion time */
XPRBprob prob;               /* BCL problem */

void jobs_model_array(void)
{
 XPRBctr ctr;
 int j,t;
 double c[NT];

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

                             /* Create start time variables */
 start = XPRBnewarrvar(prob, NJ, XPRB_PL, "start", 0, NT);
 z = XPRBnewvar(prob, XPRB_PL, "z", 0, NT);  /* Makespan var. */

 for(j=0;j<NJ;j++)           /* Set of binaries for each job */
  delta[j] = XPRBnewarrvar(prob, (NT-(int)(DUR[j])+1), XPRB_BV,
                           "delta", 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++) c[t]=t+1;
  XPRBaddarrterm(ctr, delta[j], c);
  XPRBaddterm(ctr, start[j], -1);
 }
/* Alternative constraint formulation:
 for(j=0;j<NJ;j++)
 {
  ctr = XPRBnewsumc(prob, "Link", delta[j], 1, XPRB_E, 0);
  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 */

                            /* Upper bounds on start time variables */
 for(j=0;j<NJ;j++) XPRBsetub(start[j], NT-DUR[j]+1);
}

The set of constraints Link (linking start time variables and binaries) can also be formulated using arrays and the constraint relation XPRBnewarrsum. These arrays are created by copying references to previously defined variables. In the example below, they serve only to create this set of constraints so that there is no need for storing them. If these arrays were to be used later on, they should be given different names, perhaps using an array av[NJ].

Note that the example below works with both formulations of the model, using single variables or arrays of variables for start times start and indicator variables delta.

for(j=0;j<NJ;j++)
{
 double ind[NT];
 v = XPRBstartarrvar(prob, NT-(int)(DUR[j])+2, "v1");
                     /* Define an array of size NT-DUR[j]+2 */
 for(t=0;t<(NT-(int)(DUR[j])+1);t++)
 {
   XPRBapparrvarel(v, delta[j][t]); /* Add a variable to v */
   ind[t]=t+1;                      /* Add a coefficient */
  }
  XPRBapparrvarel(v, start[j]);     /* Add "start" variable */
  XPRBendarrvar(v);                 /* Terminate array def. */
  ind[NT-(int)DUR[j]+1]=-1;         /* Add another coeff. */
  XPRBnewarrsum(prob, "Link", v, ind, XPRB_E, 0);
                                    /* Def. constraint using array v */
  XPRBdelarrvar(v);                 /* Free the allocated memory  */
 } 

Completing the example: problem solving and output

We now want to solve the example problem and retrieve the solution values (objective function and start times of all jobs). We do this with a separate function, jobs_solve. To complete the program we write a main that calls the model definition and the solution functions.

void jobs_solve(void)
{
 int statmip;
 int j;

 XPRBsetsense(prob, XPRB_MINIM);
 XPRBmipoptimize(prob, "");       /* Solve the problem as MIP */
  statmip = XPRBgetmipstat();     /* Get the problem status */
 if((statmip == XPRB_MIP_SOLUTION) ||
    (statmip == XPRB_MIP_OPTIMAL))
 {            /*  An integer solution has been found */
  printf("Objective: %g\n", XPRBgetobjval());
  for(j=0;j<NJ;j++)
  printf("%s: %g\n", XPRBgetvarname(s[j]), XPRBgetsol(s[j]));
                /*  Print out the solution for all start times */
 }
}

int main(int argc, char **argv)
{
 jobs_model();                   /* Problem definition */
 jobs_solve();                   /* Solve and print solution */
 return 0;
}

If we want to influence the branch-and-bound tree search, we may try setting some branching directives. To prioritize branching on variables that represent early start times the following lines can be added to csolve before the solution algorithm is started.

for(j=0;j<NJ;j++)
 for(t=0;t<NT-DUR[j]+1;t++)
  XPRBsetvardir(delta[j][t], XPRB_PR, 10*(t+1));
   /* Give highest priority to var.s for earlier start times */