FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Apply a binary fixing heuristic to an unpresolved MIP problem

Description

We take a production plan model and solve its LP relaxation.

Next we fix those binary variables that are very near zero to 0.0, and those that are almost one to 1.0, by changing their respective upper and lower bounds. Finally, we solve the modified problem as a MIP.

This heuristic will speed up solution - though may fail to optimse the problem.

The results are displayed on screen and the problem statistics stored in a log file.



Source Files

Data Files





fixbv.c

/***********************************************************************
   Xpress Optimizer Examples
   =========================

   file fixbv.c
   ````````````
   Apply a binary fixing heuristic to an unpresolved MIP problem.

   We take a production plan model and solve its LP relaxation.
   Next we fix those binary variables that are very
   near zero to 0.0, and those that are almost one to 1.0, by changing
   their respective upper and lower bounds. Finally, we solve the
   modified problem as a MIP.
   This heuristic will speed up solution - though may fail to optimse
   the problem.
   The results are displayed on screen and the problem statistics
   stored in a log file.

   (c) 2017 Fair Isaac Corporation
***********************************************************************/







#include <stdio.h>
#include <stdlib.h>
#include "xprs.h"                   /* Optimizer header file */

XPRSprob probg;

void XPRS_CC optimizermsg(XPRSprob prob, void* data, const char *sMsg,int nLen,int nMsgLvl);
void errormsg(const char *sSubName,int nLineNo,int nErrCode);

#define TOL 0.0005                  /* Tolerance on binary variables */


int main()
{
   int nReturn;                     /* Return value of Optimizer subroutine */
   int nOptimizerVersion;           /* Optimizer version number */
   char sProblem[]="..\\data\\coco";/* Problem name */
   char sLogFile[]="fixbv.log";     /* Log file name */
   int nExpiry;

   int nCol;                        /* Number of columns */

   /* Global problem information */
   int nGlEnt;                      /* Number of global entities: binary, integer,
                                       semi-continuous and partial integer variables */
   int nSet;                        /* Number of S1 and S2 sets */
   int *pGlInd;                     /* Column indices of the global entities */
   char *pGlType;                   /* Global entity types */

   /* Bound changes */
   int *pBndInd;                    /* Column indices of the bounds to be changed */
   char *pBndType;                  /* New bound types */
   double *pBndVal;                 /* New bound values */
   int nBnd;                        /* Bound counter */
   int i;                           /* Loop counter */
   int j;                           /* Holder for the bound indices */

   /* Solution information */
   double *x;                       /* LP solution values */
   int nGlStatus;                   /* Global status */
   int nNodes;                      /* Number of nodes solved so far in the global search */
   double dObjVal;                  /* Objective value of the best integer solution */
   char banner[256];

   /* Initialise Optimizer */
   nReturn=XPRSinit(NULL);
   XPRSgetbanner(banner); printf("%s",banner);
   if (nReturn == 8) return(1);

   nReturn=XPRScreateprob(&probg);
   if (nReturn != 0 && nReturn != 32) errormsg("XPRScreateprob",__LINE__,nReturn);

   /* Delete and define log file */
   remove(sLogFile);
   if (nReturn=XPRSsetlogfile(probg,sLogFile)) errormsg("XPRSsetlogfile",__LINE__,nReturn);

   /* Initialise Optimizer */
   /* Tell Optimizer to call optimizermsg whenever a message is output */
   nReturn=XPRSsetcbmessage(probg,optimizermsg,NULL);

   /* Get and display the Optimizer version number */
   if (nReturn=XPRSgetintcontrol(probg,XPRS_VERSION,&nOptimizerVersion))
      errormsg("XPRSgetintcontrol",__LINE__,nReturn);
   printf("Xpress Optimiser Subroutine Library Release %.2f\n\n",
      (float)nOptimizerVersion/100);

   /* Turn off presolve and permit no cuts - to slow down solution and allow
      the effect of the heuristic to be be seen */
   if (nReturn=XPRSsetintcontrol(probg,XPRS_PRESOLVE,0))
       errormsg("XPRSsetintcontrol",__LINE__,nReturn);
   if (nReturn=XPRSsetintcontrol(probg,XPRS_CUTSTRATEGY,0))
       errormsg("XPRSsetintcontrol",__LINE__,nReturn);

   /* Read the problem file */
   if (nReturn=XPRSreadprob(probg,sProblem,"")) errormsg("XPRSreadprob",__LINE__,nReturn);

   /*** Solve the LP relaxation ***/

   /* Get the number of columns */
   if (nReturn=XPRSgetintattrib(probg,XPRS_COLS,&nCol)) errormsg("XPRSgetintattrib",__LINE__,nReturn);

   /* Allocate memory for solution array and check for memory shortage */
   x=malloc(nCol * sizeof(double));
   if (!x) errormsg("malloc",__LINE__,-1);

   /* Solve the LP */
   if (nReturn=XPRSmaxim(probg,"")) errormsg("XPRSmaxim",__LINE__,nReturn);

   /* Get LP solution values */
   if (nReturn=XPRSgetsol(probg,x,NULL,NULL,NULL))
      errormsg("XPRSgetsol",__LINE__,nReturn);

   /*** Fix the binary variables that are at their bounds ***/

   /* Allocate memory for global entity arrays */
   pGlInd=malloc(nCol * sizeof(int));
   pGlType=malloc(nCol * sizeof(char));
   if (!pGlInd || !pGlType) errormsg("malloc",__LINE__,-1);

   /* Get global entity information */
   if (nReturn=XPRSgetglobal(probg,&nGlEnt,&nSet,pGlType,pGlInd,NULL,NULL,NULL,
      NULL,NULL)) errormsg("XPRSgetglobal",__LINE__,nReturn);

   /* Allocate memory for bound arrays */
   pBndInd=malloc(nGlEnt * sizeof(int));
   pBndVal=malloc(nGlEnt * sizeof(double));
   pBndType=malloc(nGlEnt * sizeof(char));
   if (!pBndInd || !pBndVal || !pBndType) errormsg("malloc",__LINE__,-1);

   /* Initialise bound counter */
   nBnd=0;

   /* Go through the global entities */
   for(i=0; i<nGlEnt; i++) {

      /* Test whether each is a binary variable */
      if (pGlType[i] == 'B') {

         /* Hold the index of the BV */
         j=pGlInd[i];

         /* If the value of the BV is within TOL of zero, store its index,
            set its upper bound to 0, and increment the bound counter */
         if (x[j]<=TOL) {
            pBndInd[nBnd]=j;
            pBndType[nBnd]='U';
            pBndVal[nBnd]=0.0;
            nBnd++;

         /* If the value of the BV is within TOL of one,store its index,
            set its lower bound to 1, and increment the bound counter */
         } else if ((1-x[j])<=TOL) {
            pBndInd[nBnd]=j;
            pBndType[nBnd]='L';
            pBndVal[nBnd]=1.0;
            nBnd++;
         }
      }
   }
   /* Instruct Optimizer to change the bounds of the appropriate BVs,
      and tell the user how many have been fixed */
   if (nReturn=XPRSchgbounds(probg,nBnd,pBndInd,pBndType,pBndVal))
      errormsg("XPRSchgbounds",__LINE__,nReturn);
   printf("Solving problem %s with a binary fixing heuristic:\n\n",sProblem);
   printf("   After the LP optimisation %d binary variables were fixed\n\n",nBnd);

   /*** Solve the modified problem as a MIP ***/

   /* Search for an integer solution */
   if (nReturn=XPRSglobal(probg)) errormsg("XPRSglobal",__LINE__,nReturn);

   /* Get the number of nodes solved in the global search */
   if (nReturn=XPRSgetintattrib(probg,XPRS_NODES,&nNodes))
       errormsg("XPRSgetintattrib",__LINE__,nReturn);

   /* Get the objective value of the best integer solution */
   if (nReturn=XPRSgetdblattrib(probg,XPRS_MIPOBJVAL,&dObjVal))
       errormsg("XPRSgetdblattrib",__LINE__,nReturn);

   /* Check the global status and display the results of the global search */
   if (nReturn=XPRSgetintattrib(probg,XPRS_MIPSTATUS,&nGlStatus))
       errormsg("XPRSgetintattrib",__LINE__,nReturn);

   switch (nGlStatus) {
      case 0:
         printf("   Problem has not been loaded");
         break;
      case 1:
         printf("   Search has not begun - LP has not been optimised");
         break;
      case 2:
         printf("   Search has not begun - LP has been optimised");
         break;
      case 3:
         printf("   Search interrupted - No integer solution was found");
         break;
      case 4:
         printf("   Search interrupted - Integer solution found: %g",dObjVal);
         break;
      case 5:
         printf("   No integer solution was found");
         break;
      case 6:
         printf("   Integer solution found: %g",dObjVal);
         break;
   }
   printf("\n\n   The MIP optimisation took %d nodes\n\n",nNodes);

   /* Free memory, close files */
   free(x);
   free(pGlInd);
   free(pGlType);
   free(pBndInd);
   free(pBndVal);
   free(pBndType);
   if (nReturn=XPRSdestroyprob(probg)) errormsg("XPRSdestroyprob",__LINE__,nReturn);
   if (nReturn=XPRSfree()) errormsg("XPRSfree",__LINE__,nReturn);

   return 0;
}


/**********************************************************************************\
* Name:         optimizermsg                                                       *
* Purpose:      Display Optimizer error messages and warnings.                     *
* Arguments:    const char *sMsg       Message string                              *
*               int nLen               Message length                              *
*               int nMsgLvl            Message type                                *
* Return Value: None                                                               *
\**********************************************************************************/
void XPRS_CC optimizermsg(XPRSprob prob, void* data, const char *sMsg,int nLen,int nMsgLvl)
{
   switch (nMsgLvl) {

      /* Print Optimizer error messages and warnings */
      case 4:       /* error */
      case 3:       /* warning */
         printf("%*s\n",nLen,sMsg);
         break;

      /* Ignore other messages */
      case 2:       /* dialogue */
      case 1:       /* information */
         break;
      /* Exit and flush buffers */
      default:
         fflush(NULL);
         break;
    }
}


/**********************************************************************************\
* Name:         errormsg                                                           *
* Purpose:      Display error information about failed subroutines.                *
* Arguments:    const char *sSubName   Subroutine name                             *
*               int nLineNo            Line number                                 *
*               int nErrCode           Error code                                  *
* Return Value: None                                                               *
\**********************************************************************************/
void errormsg(const char *sSubName,int nLineNo,int nErrCode)
{
   int nErrNo;   /* Optimizer error number */

   /* Print error message */
   printf("The subroutine %s has failed on line %d\n",sSubName,nLineNo);

   /* Append the error code, if it exists */
   if (nErrCode!=-1) printf("with error code %d\n",nErrCode);

   /* Append Optimizer error number, if available */
   if (nErrCode==32) {
      XPRSgetintattrib(probg,XPRS_ERRORCODE,&nErrNo);
      printf("The Optimizer error number is: %d\n",nErrNo);
   }

   /* Free memory, close files and exit */
   XPRSdestroyprob(probg);
   XPRSfree();
   exit(nErrCode);
}


Back to examples browserPrevious exampleNext example