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 */