/******************************************************** BCL Example Problems ==================== file xbelsc.c ````````````` Economic lot sizing, ELS, problem, solved by adding (l,S)-inequalities) in a branch-and-cut heuristic (using the cut manager). ELS considers production planning over a horizon of T periods. In period t, t=1,...,T, there is a given demand DEMAND[t] that must be satisfied by production prod[t] in period t and by inventory carried over from previous periods. There is a set-up up cost SETUPCOST[t] associated with production in period t. The unit production cost in period t is PRODCOST[t]. There is no inventory or stock-holding cost. *** This model cannot be run with a Community Licence *** (c) 2008-2024 Fair Isaac Corporation author: S.Heipcke, 2005, rev. Mar. 2011 ********************************************************/ #include <stdio.h>
#include <stdlib.h>
#include "xprb.h"
#include "xprs.h"

#define T 6                             /* Number of time periods */

/****DATA****/
int DEMAND[]    = { 1, 3, 5, 3, 4, 2};  /* Demand per period */
int SETUPCOST[] = {17,16,11, 6, 9, 6};  /* Setup cost per period */
int PRODCOST[]  = { 5, 3, 2, 1, 3, 1};  /* Production cost per period */
int D[T][T];                            /* Total demand in periods t1 - t2 */

XPRBvar prod[T];                        /* Production in period t */
XPRBvar setup[T];                       /* Setup in period t */

struct myobj
{
 XPRBprob prob;
 double tol;
};

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

void mod_els(XPRBprob prob)
{
 int s,t,k;
 XPRBctr ctr;

 for(s=0;s<T;s++) for(t=0;t<T;t++) for(k=s;k<=t;k++) +=DEMAND[k]; prod[t]=XPRBnewvar(prob,XPRB_PL, setup[t]=XPRBnewvar(prob,XPRB_BV, ctr=XPRBnewctr(prob,"OBJ",XPRB_N); Minimize total cost Production in period t must not exceed the demand for remaining if there is production during then a setup periods to satisfy this of time for(s=0;s<=t;s++) Cut generation loop at tree node: get solution values identify and set up violated constraints add cuts matrix int XPRS_CC void struct myobj double Objective value Counters Solution var.s prod XPRBcut mo=(struct>prob, oprob);

 ncut = 0;
 XPRSgetintattrib(oprob,XPRS_NODEDEPTH, &depth);
 XPRSgetintattrib(oprob,XPRS_NODES, &node);

      /* Get the solution values */
 XPRBsync(mo->prob, XPRB_XPRS_SOL);
 for(t=0;t<T;t++) solprod[t]=XPRBgetsol(prod[t]); solsetup[t]=XPRBgetsol(setup[t]); Search for violated constraints: for(l=0;l<T;l++) (ds=0.0, t=0; t<=l; mo->tol)  ds += solprod[t];
    else  ds += D[t][l]*solsetup[t];
   }

      /* Add the violated inequality: the minimum of the actual production
         prod[t] and the maximum potential production D[t][l]*setup[t]
         in periods 0 to l must at least equal the total demand in periods
         0 to l.
         sum(t=1:l) min(prod[t], D[t][l]*setup[t]) >= D[0][l]
       */
   if(ds < D[0][l] - mo->tol)
   {
    cut[ncut] = XPRBnewcut(mo->prob, XPRB_G, 1);
    XPRBaddcutterm(cut[ncut], NULL, D[0][l]);
    for(t=0;t<=l;t++)
    {
     if (solprod[t] < D[t][l]*solsetup[t] + mo->tol)
      XPRBaddcutterm(cut[ncut], prod[t], 1);
     else
      XPRBaddcutterm(cut[ncut], setup[t], D[t][l]);
    }
    ncut++;
   }
 }

/* Add cuts to the problem */
 if(ncut>0)
 {
   XPRBaddcuts(mo->prob, cut, ncut);
   XPRSgetdblattrib(oprob, XPRS_LPOBJVAL, &objval);
   printf("Cuts added : %d (depth %d, node %d, obj. %g)\n",
          ncut, depth, node, objval);
 }
 XPRBendcb(mo->prob);

 return 0;
}

/***********************************************************************/
void tree_cut_gen(XPRBprob prob)
{
 XPRSprob oprob;
 struct myobj mo;
 double feastol;
 int starttime,t;

 starttime=XPRBgettime();

 oprob = XPRBgetXPRSprob(prob);                   /* Get Optimizer problem */

 XPRSsetintcontrol(oprob, XPRS_LPLOG, 0);
 XPRSsetintcontrol(oprob, XPRS_MIPLOG, 3);

 XPRSsetintcontrol(oprob, XPRS_CUTSTRATEGY, 0);   /* Disable automatic cuts */
 XPRSsetintcontrol(oprob, XPRS_PRESOLVE, 0);      /* Switch presolve off */
 XPRSsetintcontrol(oprob, XPRS_EXTRAROWS, 5000);  /* Reserve extra rows */

 XPRSgetdblcontrol(oprob, XPRS_FEASTOL, &feastol);  /* Get zero tolerance */
 feastol*= 10;

 mo.prob=prob;
 mo.tol=feastol;
 XPRBsetcutmode(prob,1);
 XPRSsetcbcutmgr(oprob, cb_node, &mo);
 XPRBmipoptimize(prob,"");                        /* Solve the MIP */
 printf("(%g sec) MIP status %d, best solution: %1,3f\n",
   (XPRBgettime()-starttime)/1000.0, XPRBgetmipstat(prob), XPRBgetobjval(prob));
 for(t=0;t<T;t++)
  printf("Period %d: prod %g (demand: %d, cost: %d), setup %g (cost: %d)\n",
      t+1, XPRBgetsol(prod[t]), DEMAND[t], PRODCOST[t], XPRBgetsol(setup[t]),
      SETUPCOST[t]);
}


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

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

 prob=XPRBnewprob("Els");         /* Initialize a new problem in BCL */
 mod_els(prob);                   /* Model the problem */
 tree_cut_gen(prob);              /* Solve the problem */

 return 0;
}