FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Els - An economic lot-sizing problem solved by cut-and-branch and branch-and-cut heuristics

Description
The version 'xbels' of this example shows how to implement cut-and-branch (= cut generation at the root node of the MIP search) and 'xbelsc' implements a branch-and-cut (= cut generation at the MIP search tree nodes) algorithm using the cut manager.

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

xbelsc.c

/********************************************************
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++)
D[s][t] += DEMAND[k];

/****VARIABLES****/
for(t=0;t<T;t++)
{
prod[t]=XPRBnewvar(prob,XPRB_PL, XPRBnewname("prod%d",t+1),0,XPRB_INFINITY);
setup[t]=XPRBnewvar(prob,XPRB_BV, XPRBnewname("setup%d",t+1),0,1);
}

/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);   /* Minimize total cost */
for(t=0;t<T;t++)
{
}
XPRBsetobj(prob,ctr);

/****CONSTRAINTS****/
/* Production in period t must not exceed the total demand for the
remaining periods; if there is production during t then there
is a setup in t */
for(t=0;t<T;t++)
{
ctr = XPRBnewctr(prob,"Production",XPRB_L);
}

/* Production in periods 0 to t must satisfy the total demand
during this period of time */
for(t=0;t<T;t++)
{
ctr = XPRBnewctr(prob,"Demand",XPRB_G);
for(s=0;s<=t;s++)
}

}

/**************************************************************************/
/*  Cut generation loop at the tree node:                                 */
/*    get the solution values                                             */
/*    identify and set up violated constraints                            */
/*    add cuts to the matrix                                              */
/**************************************************************************/
int XPRS_CC cb_node(XPRSprob oprob, void *mobj)
{
struct myobj *mo;
double objval;                  /* Objective value */
int t,l;
int ncut;                       /* Counters for cuts */
double solprod[T], solsetup[T]; /* Solution values for var.s prod & setup */
double ds;
int depth,node;
XPRBcut cut[T];

mo=(struct myobj *)mobj;
XPRBbegincb(mo->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++)
{
for (ds=0.0, t=0; t<=l; t++)
{
if(solprod[t] < D[t][l]*solsetup[t] + 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);
for(t=0;t<=l;t++)
{
if (solprod[t] < D[t][l]*solsetup[t] + mo->tol)
else
}
ncut++;
}
}

/* Add cuts to the problem */
if(ncut>0)
{
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_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);
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;
}

`