 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.

xbels.java

/********************************************************
Xpress-BCL Java Example Problems
================================

file xbels.java

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 Fair Isaac Corporation
author: S.Heipcke, 2001, rev. Mar. 2011
********************************************************/

import com.dashoptimization.*;

public class xbels {
static final double EPS = 1e-6;
static final int T = 6;                 /* Number of time periods */

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

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

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

static void modEls(XPRBprob p) throws XPRSexception {
int s,t,k;
XPRBexpr cobj,le;

D = new int[T][T];
for(s=0;s<T;s++)
for(t=0;t<T;t++)
for(k=s;k<=t;k++)
D[s][t] += DEMAND[k];

/****VARIABLES****/
prod = new XPRBvar[T];
setup = new XPRBvar[T];
for(t=0;t<T;t++) {
prod[t]=p.newVar("prod" + (t+1));
setup[t]=p.newVar("setup" +(t+1), XPRB.BV);
}

/****OBJECTIVE****/
cobj = new XPRBexpr();
for(t=0;t<T;t++)                      /* Minimize total cost */
p.setObj(cobj);

/****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++)
p.newCtr("Production", prod[t] .lEql(setup[t].mul(D[t][T-1])) );

/* Production in periods 0 to t must satisfy the total demand
during this period of time */
for(t=0;t<T;t++) {
le = new XPRBexpr();
p.newCtr("Demand", le.gEql(D[t]) );
}
}

/**************************************************************************/
/*  Cut generation loop at the top node:                                  */
/*    solve the LP and save the basis                                     */
/*    get the solution values                                             */
/*    identify and set up violated constraints                            */
/**************************************************************************/
static void solveEls(XPRBprob p) throws XPRSexception {
double objval;               /* Objective value */
int t,l;
int starttime;
int ncut, npass, npcut;      /* Counters for cuts and passes */
double[] solprod, solsetup;  /* Solution values for var.s prod & setup */
double ds;
XPRSprob op;
XPRBbasis basis;
XPRBexpr le;

starttime=XPRB.getTime();
op=p.getXPRSprob();
op.setIntControl(XPRS.CUTSTRATEGY, 0);
/* Disable automatic cuts - we use our own */
op.setIntControl(XPRS.PRESOLVE, 0);
/* Switch presolve off */
ncut = npass = 0;
solprod = new double[T];
solsetup = new double[T];

do {
npass++;
npcut = 0;
p.lpOptimize("p");          /* Solve the LP */
basis = p.saveBasis();      /* Save the current basis */
objval = p.getObjVal();     /* Get the objective value */

/* Get the solution values: */
for(t=0;t<T;t++) {
solprod[t]=prod[t].getSol();
solsetup[t]=setup[t].getSol();
}

/* 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] + EPS)  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[l]
*/
if(ds < D[l] - EPS) {
le = new XPRBexpr();
for(t=0;t<=l;t++) {
if (solprod[t] < D[t][l]*solsetup[t] + EPS)
else
}
p.newCtr("cut" +(ncut+1), le.gEql(D[l]) );
ncut++;
npcut++;
}
}

System.out.println("Pass " +npass + " (" +(XPRB.getTime()-starttime)/1000.0
+ " sec), objective value " + objval + ", cuts added: " + npcut
+ " (total " + ncut +")");

if(npcut==0)
System.out.println("Optimal integer solution found:");
else {
basis = null;                /* No need to keep the basis any longer */
}
} while(npcut>0);

/* Print out the solution: */
for(t=0;t<T;t++)
System.out.println("Period " + (t+1) + ": prod " + prod[t].getSol()
+ " (demand: " + DEMAND[t] + ", cost: " + PRODCOST[t] + "), setup "
+ setup[t].getSol() + " (cost: " + SETUPCOST[t] + ")");
}

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

public static void main(String[] args) throws XPRSprobException, XPRSexception {
try (XPRBprob p = new XPRBprob("Els"); /* Initialize BCL and create a new problem */
XPRS xprs = new XPRS()) {         /* Initialize Xpress-Optimizer */
modEls(p);                     /* Model the problem */
solveEls(p);                   /* Solve the problem */
}
}
}

`   