/******************************************************** BCL Example Problems ==================== file xbexpl1.c `````````````` BCL user guide example. Definition of variables and constraints, variable arrays and SOS, followed by file output, solving and printing of solutions. (c) 2008-2023 Fair Isaac Corporation author: S.Heipcke, Jan. 2000, rev. Mar. 2011 ********************************************************/ #include <stdio.h>
#include "xprb.h"

/**************************************************************************/
/* Define *one* of the following options to try out different problem     */
/* formulations:                                                          */
/**************************************************************************/
#define BASIC
#undef ARRAYC
#undef SOS
#undef ARRAY
/**************************************************************************/

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

/**** DATA ****/
double DUR[] = {3,4,2,2};    /* Durations of jobs   */
/*{4,2,3,4};
  {5,1,1,6};
  {5,5,4,4}; */
#ifdef ARRAY
XPRBarrvar start;            /* Start times of jobs  */
XPRBarrvar delta[NJ];        /* Sets of binaries for start times */
#else
XPRBvar start[NJ];           /* Start times of jobs  */
XPRBvar delta[NJ][NT];       /* Binaries for start times */
#endif

XPRBsos set[NJ];             /* Sets regrouping start times for jobs */

XPRBvar z;                   /* Maximum completion time (makespan) */

XPRBprob prob;               /* BCL problem */

void jobs_model(void);       /* Basic model formulation */
void jobs_modela(void);      /* Model using arrays of variables for some
                                constraints  */
void jobs_modelb(void);      /* Model using SOS */
void jobs_modelc(void);      /* Model using arrays of variables for
                                all variables */
void jobs_solve(void);        /* Solving and solution printing */

/*************************************************************************/

void jobs_model(void)
{
 XPRBctr ctr;
 int j,t;

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

/****VARIABLES****/
                             /* Create start time variables */
 for(j=0;j<NJ;j++) start[j] = XPRBnewvar(prob,XPRB_PL,"start",0,NT);
 z = XPRBnewvar(prob,XPRB_PL,"z",0,NT);  /* Declare the makespan variable */

 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,XPRBnewname("delta%d%d",j+1,t+1),0,1);

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

 for(j=0;j<NJ;j++)           /* Linking start times and binaries  */
 {
  ctr = XPRBnewctr(prob,XPRBnewname("Link_%d",j+1),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++)           /* One unique start time for each job  */
 {
  ctr = XPRBnewctr(prob,XPRBnewname("One_%d",j+1),XPRB_E);
  for(t=0;t<(NT-DUR[j]+1);t++) XPRBaddterm(ctr,delta[j][t],1);
  XPRBaddterm(ctr,NULL,1);
 }

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

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

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

/*************************************************************************/
void jobs_solve(void)
{
 int statmip;
 int j;
 int t;
#ifndef SOS
 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 variables for earlier start times */
#else
 for(j=0;j<NJ;j++)
  XPRBsetsosdir(set[j],XPRB_DN,0);
          /* First branch downwards on sets */
#endif

 XPRBsetsense(prob,XPRB_MINIM);
 XPRBmipoptimize(prob,"");        /* Solve the problem as MIP */
 statmip = XPRBgetmipstat(prob);  /* Get the MIP problem status */

 if((statmip == XPRB_MIP_SOLUTION) || (statmip == XPRB_MIP_OPTIMAL))
                                  /* An integer solution has been found */
 {
  printf("Objective: %g\n",XPRBgetobjval(prob));
  for(j=0;j<NJ;j++)
  {                               /* Print the solution for all start times */
   printf("%s: %g\n",XPRBgetvarname(start[j]), XPRBgetsol(start[j]));
#ifdef ARRAY
   XPRBprintarrvar(delta[j]);
#else
   for(t=0;t<NT-DUR[j]+1;t++)
    printf("%s: %g, ", XPRBgetvarname(delta[j][t]), XPRBgetsol(delta[j][t]));
   printf("\n");
#endif
  }
 }
}

/*************************************************************************/

int main(int argc, char **argv)
{
#ifdef BASIC
  jobs_model();               /* Basic problem definition */
#endif
#ifdef ARRAYC
  jobs_modela();              /* Formulation using arrays for some
                                 constraints */
#endif
#ifdef SOS
  jobs_modelb();              /* Formulation using SOS */
#endif
#ifdef ARRAY
  jobs_modelc();              /* Formulation using arrays of variables */
#endif
  jobs_solve();               /* Solve and print solution */
  return 0;
}

/*************************************************************************/

    /**** Formulation using arrays in constraint definition ****/
void jobs_modela(void)
{
 XPRBctr ctr;
 XPRBarrvar v;
 int j,t;

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

/****VARIABLES****/
                                    /* Create start time variables */
 for(j=0;j<NJ;j++) start[j] = XPRBnewvar(prob,XPRB_PL,"start",0,NT);
 z = XPRBnewvar(prob,XPRB_PL,"z",0,NT);  /* Declare the makespan variable */

 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,XPRBnewname("delta%d%d",j+1,t+1),0,1);


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

 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 binary variable to the array */
   ind[t]=t+1;                      /* Add a coefficient */
  }
  XPRBapparrvarel(v,start[j]);      /* Add a continuous var. to the array */
  XPRBendarrvar(v);                 /* Terminate definition of the array  */
  ind[NT-(int)DUR[j]+1]=-1;         /* Add another coefficient */
  XPRBnewarrsum(prob,XPRBnewname("Link_%d",j+1),v,ind,XPRB_E,0);
                                    /* Establish sum constraint using array v */
  XPRBdelarrvar(v);                 /* Free the memory allocated to the array */
 }                                  /* ... and the table of coefficients  */

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

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

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

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

/*************************************************************************/

    /**** SOS-formulation ****/
void jobs_modelb(void)
{
 XPRBctr ctr;
 int j,t;

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

/****VARIABLES****/
                                    /* Create start time variables */
 for(j=0;j<NJ;j++) start[j] = XPRBnewvar(prob,XPRB_PL,"start",0,NT);
 z = XPRBnewvar(prob,XPRB_PL,"z",0,NT);  /* Declare the makespan variable */

 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_PL,XPRBnewname("delta%d%d",j+1,t+1),0,1);

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

 for(j=0;j<NJ;j++)                  /* Linking start times and binaries  */
 {
  ctr = XPRBnewctr(prob,XPRBnewname("Link_%d",j+1),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++)                  /* One unique start time for each job  */
 {
  ctr = XPRBnewctr(prob,XPRBnewname("One_%d",j+1),XPRB_E);
  for(t=0;t<(NT-DUR[j]+1);t++) XPRBaddterm(ctr,delta[j][t],1);
  XPRBaddterm(ctr,NULL,1);
 }

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


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

/****SETS****/
 for(j=0;j<NJ;j++)
 {
  set[j] = XPRBnewsos(prob,"sosj",XPRB_S1);
  for(t=0;t<(NT-DUR[j]+1);t++)
   XPRBaddsosel(set[j],delta[j][t],t+1);
 }

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

/*************************************************************************/
#ifdef ARRAY
void jobs_modelc(void)
{
 XPRBctr ctr;
 int j;

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

/****VARIABLES****/
                                    /* Create a table of start time variables */
 start = XPRBnewarrvar(prob,NJ,XPRB_PL,"start",0,NT);
 z = XPRBnewvar(prob,XPRB_PL,"z",0,NT);  /* Declare the makespan variable */

 for(j=0;j<NJ;j++)                  /* Declare a set of binaries for each job */
  delta[j] = XPRBnewarrvar(prob,(NT-(int)(DUR[j])+1),XPRB_BV,XPRBnewname("delta%d",j+1),0,1);

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

/* Alternative constraint formulation: (linking start times and binaries) */
/*
 for(j=0;j<NJ;j++)
 {
  int t;
  double c[NT];

  ctr = XPRBnewctr(prob,XPRBnewname("Link_%d",j+1),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);
 }
*/

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

 for(j=0;j<NJ;j++)                  /* One unique start time for each job  */
  XPRBnewsum(prob,"One",delta[j],XPRB_E,1);

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

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

/****SETS****/
/* Alternative SOS formulation: define delta as continuous variables! */
/*
 for(j=0;j<NJ;j++)
  XPRBnewsosrc(prob,"sosj",XPRB_S1,delta[j],
               XPRBgetbyname(prob,XPRBnewname("Link_%d",j+1),XPRB_PL)); */
        /* Create an SOS-1 for each job with a reference row from ctr.s Link */

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