/********************************************************
  BCL Example Problems
  ====================

  file xbcutex.c
  ``````````````
  Simplified version of xbexpl1.c showing how
  to define cuts with BCL.

  (c) 2008-2023 Fair Isaac Corporation
      author: S.Heipcke, 2000, rev. Mar. 2011
********************************************************/

#include <stdio.h> #include "xprb.h" #include "xprs.h" #define NJ 4 /* Number of jobs */ #define NT 10 /* Time limit */ /**** DATA ****/ double D[] = {3,4,2,2}; /* Durations of jobs */ XPRBvar start[NJ]; /* Start times of jobs */ XPRBvar delta[NJ][NT]; /* Binaries for start times */ XPRBvar z; /* Maximum completion time (makespan) */ /***********************************************************************/ int XPRS_CC usrcme(XPRSprob oprob, void* vd) { XPRBcut ca[2]; int num; int i=0; XPRBprob bprob; /* In terms of an example, we add a few additional constraints (without any relation to the original problem) at the second node of the MIP search tree. These constraints/cuts are applied at this node and all its child nodes. */ bprob = (XPRBprob)vd; XPRBbegincb(bprob, oprob); XPRSgetintattrib(oprob, XPRS_NODES, &num); if(num == 2) { /* ca0: s_1+2 <= s_0 */ ca[0] = XPRBnewcutprec(bprob, start[1], 2, start[0], 2); ca[1] = XPRBnewcut(bprob, XPRB_L, 2); /* ca1: 4*s_2 - 5,3*s_3 <= -17 */ XPRBaddcutterm(ca[1], start[2], 4); XPRBaddcutterm(ca[1], start[3], -5,3); XPRBaddcutterm(ca[1], NULL, -17); printf("Adding constraints:\n"); for(i=0;i<2;i++) XPRBprintcut(ca[i]); if(XPRBaddcuts(bprob, ca, 2)) printf("Problem with adding cuts.\n"); } XPRBendcb(bprob); return 0; } /*************************************************************************/ void cmodel1(XPRBprob prob) { XPRBctr ctr; int j,t; /****VARIABLES****/ /* Create start time variables */ for(j=0;j<NJ;j++) start[j] = XPRBnewvar(prob, XPRB_PL, "start", 0, NT);
                            /* Declare the makespan variable */
 z = XPRBnewvar(prob, XPRB_PL, "z", 0, NT);

 for(j=0;j<NJ;j++)          /* Declare binaries for each job  */
  for(t=0;t<(NT-D[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, "C1", start[j], D[j], z);
                            /* Precedence relation between jobs  */
 XPRBnewprec(prob, "C2", start[0], D[0], start[2]);

 for(j=0;j<NJ;j++)          /* Linking start times and binaries  */
 {
  ctr = XPRBnewctr(prob, XPRBnewname("C3_%d",j+1), XPRB_E);
  for(t=0;t<(NT-D[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("C4_%d",j+1), XPRB_E);
  for(t=0;t<(NT-D[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-D[j]+1);
                            /* Upper bounds on start time variables */
}

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

void csolve(XPRBprob bprob)
{
 int statmip;
 int j;
 int t;
 XPRSprob oprob;

 oprob = XPRBgetXPRSprob(bprob);
 XPRSsetintcontrol(oprob, XPRS_HEUREMPHASIS, 0);
 XPRSsetintcontrol(oprob, XPRS_CUTSTRATEGY, 0);
                             /* Switch heuristics and cut generation off:
                                otherwise this problem is solved in the
                                first node of the MIP search tree */

 XPRBsetsense(bprob, XPRB_MINIM);
 XPRBsetcutmode(bprob, 1);   /* Switch presolve off, enable cut manager */
 XPRSsetcbcutmgr(oprob, usrcme, bprob);
 XPRBmipoptimize(bprob, "");       /* Solve the problem as MIP */

 statmip = XPRBgetmipstat(bprob);  /* 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(bprob));
  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-D[j]+1;t++)
    printf("%s: %g, ", XPRBgetvarname(delta[j][t]), XPRBgetsol(delta[j][t]));
   printf("\n");
  }
 }
}

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

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

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

 cmodel1(prob);                  /* Basic problem definition */
 csolve(prob);                   /* Solve and print solution */

 return 0;
}