/********************************************************
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 Fair Isaac Corporation
author: S.Heipcke, 2001, rev. Mar. 2011
********************************************************/
#include
#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= 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 |
/********************************************************
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.
(c) 2008 Fair Isaac Corporation
author: S.Heipcke, 2005, rev. Mar. 2011
********************************************************/
#include
#include
#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;sprob, 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;ttol) 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) Global status %d, best solution: %1.3f\n",
(XPRBgettime()-starttime)/1000.0, XPRBgetmipstat(prob), XPRBgetobjval(prob));
for(t=0;t |
