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

Fixbv - A binary fixing heuristic

Description
Implements a binary fixing heuristic for the complete Coco Problem (see the introductory example 'Coco'). The program changes bounds directly in the Optimizer and shows how to save and re-load bases. Model version 'xbfixbvls' adds saving and loading of MIP solutions.

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

xbfixbv.cxx

/********************************************************
Xpress-BCL C++ Example Problems
===============================

file xbfixbv.cxx

Using the complete Coco Problem, as in xbcoco.cxx,
this program implements a binary fixing heuristic.

(c) 2008 Fair Isaac Corporation
author: S.Heipcke, 2001, rev. Mar. 2011
********************************************************/

#include <iostream>
#include "xprb_cpp.h"
#include "xprs.h"

using namespace std;
using namespace ::dashoptimization;

#define TOL 5.0E-4

#define PHASE 5
/* Phase = 4: Mines may open/closed freely; when closed save 20000 per month
* Phase = 5: Once closed always closed; larger saving */

#define NP 2            /* Number of products (p) */
#define NF 2            /*           factories (f) */
#define NR 2            /*           raw materials (r) */
#define NT 4            /*           time periods (t) */

/****DATA****/
double REV[][NT] =      /* Unit selling price of product p in period t */
{{400, 380, 405, 350},
{410, 397, 412, 397}};
double CMAK[][NF] =     /* Unit cost to make product p at factory f */
{{150, 153},
{ 75,  68}};
double CBUY[][NT] =     /* Unit cost to buy raw material r in period t */
{{100,  98,  97, 100},
{200, 195, 198, 200}};
double COPEN[] =        /* Fixed cost of factory f being open for one period */
{50000, 63000};
double CPSTOCK = 2.0;   /* Unit cost to store any product p */
double CRSTOCK = 1.0;   /* Unit cost to store any raw material r */
double REQ[][NR] =      /* Requirement by unit of prod. p for raw material r */
{{1.0, 0.5},
{1.3, 0.4}};
double MXSELL[][NT] =   /* Max. amount of p that can be sold in period t */
{{650, 600, 500, 400},
{600, 500, 300, 250}};
double MXMAKE[] =       /* Max. amount factory f can make over all products */
{400, 500};
double MXRSTOCK = 300;  /* Max. amount of r that can be stored each f and t */
double PSTOCK0[][NF] =  /* Initial product p stock level at factory f */
{{50, 100},
{50,  50}};
double RSTOCK0[][NF] =  /* Initial raw material r stock level at factory f*/
{{100, 150},
{ 50, 100}};

/****VARIABLES****/
XPRBvar openm[NF][NT];

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

void modCoco(XPRBprob &pb)
{
XPRBvar make[NP][NF][NT], sell[NP][NF][NT], pstock[NP][NF][NT+1],
XPRBexpr lobj, lc;
int p,f,r,t;

/****VARIABLES****/
for(p=0;p<NP;p++)
for(f=0;f<NF;f++)
{
for(t=0;t<NT;t++)
{
make[p][f][t] = pb.newVar(XPRBnewname("make_p%d_f%d",p+1,f+1));
/* Amount of prod. p to make at factory f in period t */
sell[p][f][t] = pb.newVar(XPRBnewname("sell_p%d_f%d",p+1,f+1));
/* Amount of prod. p sold from factory f in period t */
}
for(t=0;t<NT+1;t++)
pstock[p][f][t] = pb.newVar(XPRBnewname("pstock_p%d_f%d",p+1,f+1));
/* Stock level of prod. p at factory f at start of period t */
}
for(r=0;r<NR;r++)
for(f=0;f<NF;f++)
{
for(t=0;t<NT;t++)
/* Amount of raw material r bought for factory f in period t */
for(t=0;t<NT+1;t++)
rstock[r][f][t] = pb.newVar(XPRBnewname("rstock_r%d_f%d",r+1,f+1));
/* Stock level of raw mat. r at factory f at start of per. t */
}

for(f=0;f<NF;f++)
for(t=0;t<NT;t++)
openm[f][t] = pb.newVar(XPRBnewname("open_f%d",f+1), XPRB_BV);
/* 1 if factory f is open in period t, else 0 */

/****OBJECTIVE****/
for(f=0;f<NF;f++)        /* Objective: maximize total profit */
{
for(p=0;p<NP;p++)
{
for(t=0;t<NT;t++)
lobj += REV[p][t]*sell[p][f][t] - CMAK[p][f]*make[p][f][t];
for(t=1;t<NT+1;t++)  lobj -= CPSTOCK*pstock[p][f][t];
}
if(PHASE==4)
for(t=0;t<NT;t++)  lobj += (20000-COPEN[f])*openm[f][t];
else if(PHASE==5)
for(t=0;t<NT;t++)  lobj -= COPEN[f]*openm[f][t];
for(r=0;r<NR;r++)
{
for(t=1;t<NT+1;t++)  lobj -= CRSTOCK*rstock[r][f][t];
}
}
pb.setObj(pb.newCtr("OBJ",lobj));   /* Set objective function */

/****CONSTRAINTS****/
for(p=0;p<NP;p++)        /* Product stock balance */
for(f=0;f<NF;f++)
for(t=0;t<NT;t++)
pb.newCtr("PBal",
pstock[p][f][t]+make[p][f][t] == sell[p][f][t]+pstock[p][f][t+1] );

for(r=0;r<NR;r++)        /* Raw material stock balance */
for(f=0;f<NF;f++)
for(t=0;t<NT;t++)
{
lc=0;
for(p=0;p<NP;p++)  lc += REQ[p][r]*make[p][f][t];
}

for(p=0;p<NP;p++)
for(t=0;t<NT;t++)
{                       /* Limit on the amount of product p to be sold */
lc=0;
for(f=0;f<NF;f++)  lc += sell[p][f][t];
pb.newCtr("MxSell", lc <= MXSELL[p][t]);
}

for(f=0;f<NF;f++)
for(t=0;t<NT;t++)
{                       /* Capacity limit at factory f */
lc=0;
for(p=0;p<NP;p++)  lc += make[p][f][t];
pb.newCtr("MxMake", lc <= MXMAKE[f]*openm[f][t]);
}

for(f=0;f<NF;f++)
for(t=1;t<NT+1;t++)
{                       /* Raw material stock limit */
lc=0;
for(r=0;r<NR;r++) lc += rstock[r][f][t];
pb.newCtr("MxRStock", lc <= MXRSTOCK);
}

if(PHASE==5)
for(f=0;f<NF;f++)
for(t=0;t<NT-1;t++)    /* Once closed, always closed */
pb.newCtr("Closed", openm[f][t+1] <= openm[f][t]);

/****BOUNDS****/
for(p=0;p<NP;p++)
for(f=0;f<NF;f++)
pstock[p][f][0].fix(PSTOCK0[p][f]);    /* Initial product levels */

for(r=0;r<NR;r++)
for(f=0;f<NF;f++)
rstock[r][f][0].fix(RSTOCK0[r][f]);    /* Initial raw mat. levels */

if(PHASE<=3)
for(f=0;f<NF;f++)
for(t=0;t<NT;t++)
openm[f][t].fix(1);
}

/**************************************************************************/
/*  Solution heuristic:                                                   */
/*    solve the LP and save the basis                                     */
/*    fix all open variables which are integer feasible at the relaxation */
/*    solve the MIP and save the best solution value                      */
/*    reset all variables to their original bounds                        */
/*    load the saved basis                                                */
/*    solve the MIP using the solution value found previously as cutoff   */
/**************************************************************************/
void solveCoco(XPRBprob &pb)
{
XPRBbasis basis;
int f,t, ifgsol;
double solval, osol[NF][2];

/****SOLVING + OUTPUT****/
/* Disable automatic cuts - we use a heuristic */
/* Switch presolve off */
pb.setSense(XPRB_MAXIM);   /* Choose the sense of the optimization */
pb.mipOptimize("l");       /* Solve the LP-relaxation */
basis=pb.saveBasis();      /* Save the current basis */

/* For t=0,1 get the solution values of the open variables: */
for(f=0;f<NF;f++)
for(t=0;t<2;t++)
{
osol[f][t]=openm[f][t].getSol();
/* Fix all variables which are integer feasible: */
if(osol[f][t] < TOL)  openm[f][t].setUB(0.0);
else if(1-osol[f][t] < TOL)  openm[f][t].setLB(1.0);
}

pb.mipOptimize("c");       /* Continue solving the MIP-problem */
ifgsol=0;
if(pb.getMIPStat()==XPRS_MIP_SOLUTION || pb.getMIPStat()==XPRS_MIP_OPTIMAL)
{                          /* If a global solution was found */
ifgsol=1;
solval=pb.getObjVal();    /* Get the value of the best solution */
}

XPRSpostsolve(pb.getXPRSprob());  /* Re-initialize the global search */

/* Reset variables to their original bounds: */
for(f=0;f<NF;f++)
for(t=0;t<2;t++)
if((osol[f][t] < TOL) || (1-osol[f][t] < TOL))
{
openm[f][t].setLB(0.0);
openm[f][t].setUB(1.0);
}

immediately passed on from BCL to the
Optimizer if the problem has not been modified
in any other way, so that there is no need to
basis.reset();             /* No need to store the saved basis any longer */
if(ifgsol==1)
/* Set the cutoff to the best known solution */
pb.mipOptimize("");        /* Solve the MIP-problem */

if(pb.getMIPStat()==XPRS_MIP_SOLUTION || pb.getMIPStat()==XPRS_MIP_OPTIMAL)
cout << "Best integer solution:" << pb.getObjVal() << endl;
else
cout << "Best integer solution: " << solval << endl;
}

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

int main(int argc, char **argv)
{
XPRBprob pb("Coco");       /* Initialize a new problem in BCL */
modCoco(pb);               /* Model the problem */
solveCoco(pb);             /* Solve the problem */

return 0;
}