/******************************************************** BCL Example Problems ==================== file xbels.c ```````````` Economic lot sizing, ELS, problem, solved by adding (l,S)-inequalities) in several rounds looping over the root node. 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. (c) 2008-2024 Fair Isaac Corporation author: S.Heipcke, 2001, rev. Mar. 2011 ********************************************************/ #include <stdio.h>
#include "xprb.h"
#include "xprs.h"

#define EPS    1e-6

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

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

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 top node: solve LP and save basis get solution values identify set up violated constraints load modified problem saved void double Objective value int Counters cuts passes Solution var.s prod XPRBbasis XPRBctr starttime=XPRBgettime(); Disable automatic we use our own Switch presolve off ncut=npass do npcut=0; Solve Save current objval=XPRBgetobjval(prob); Get objective values: solprod[t]=XPRBgetsol(prod[t]); solsetup[t]=XPRBgetsol(setup[t]); Search constraints: for(l=0;l<T;l++) (ds=0.0, t<=l; ds else Add inequality: minimum actual maximum potential l least equal l. sum(t=1:l)>= D[0][l]
       */
   if(ds < D[0][l] - EPS)
   {
    cut = XPRBnewctr(prob,XPRBnewname("cut%d",ncut+1), XPRB_G);
    XPRBaddterm(cut, NULL, D[0][l]);
    for(t=0;t<=l;t++)
    {
     if (solprod[t] < D[t][l]*solsetup[t] + EPS)
      XPRBaddterm(cut, prod[t], 1);
     else
      XPRBaddterm(cut, setup[t], D[t][l]);
    }
    ncut++;
    npcut++;
   }
  }

  printf("Pass %d (%g sec), objective value %g, cuts added: %d (total %d)\n",
   npass, (XPRBgettime()-starttime)/1000.0, objval, npcut, ncut);

  if(npcut==0)
   printf("Optimal integer solution found:\n");
  else
  {
   XPRBloadmat(prob);             /* Reload the problem */
   XPRBloadbasis(basis);          /* Load the saved basis */
   XPRBdelbasis(basis);           /* No need to keep the basis any longer */
  }
 } while(npcut>0);

      /* Print out the solution: */
 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 */
 solve_els(prob);                 /* Solve the problem */

 return 0;
}