/******************************************************** BCL Example Problems ==================== file xbexpl1i.c ``````````````` BCL user guide example. Version using index sets. (c) 2008 Fair Isaac Corporation author: S.Heipcke, 2003, rev. Mar. 2011 ********************************************************/ #include <stdio.h>
#include <stdlib.h>
#include "xprb.h"

#define MAXNJ 4              /* Maximum number of jobs */
#define NT   10              /* Time limit */

#define DATAFILE XPRBDATAPATH "/jobs/durations.dat"

/**** DATA ****/
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;                   /* Maximum completion time (makespan) */
XPRBprob prob;               /* BCL problem */

void read_data(void);        /* Read data from file  */
void jobs_model(void);       /* Model formulation */
void jobs_solve(void);       /* Solving and solution printing */

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

void read_data(void)
{
 char name[100];
 FILE *datafile;
                             /* Create a new index set */
 Jobs = XPRBnewidxset(prob, "jobs", MAXNJ);

 datafile=fopen(DATAFILE,"r");  /* Open the 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;

/****VARIABLES****/
                             /* Create start time variables (incl. 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);  /* Declare the makespan variable */

                             /* 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); }
  for(t=0;t<(NT-DUR[j]+1);t++)
   delta[j][t] = XPRBnewvar(prob,XPRB_BV,
                  XPRBnewname("delta%s_%d",XPRBgetidxelname(Jobs,j),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 */

 jobs_solve();               /* Solve the problem */

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

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

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

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

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

/****SOLUTION PRINTING****/
 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]));
   for(t=0;t<NT-DUR[j]+1;t++)
    printf("%s: %g, ", XPRBgetvarname(delta[j][t]), XPRBgetsol(delta[j][t]));
   printf("\n");
  }
 }
}

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

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