Apply a primal heuristic to a knapsack problem

The program demonstrates the use of the global log callback.

We take the knapsack problem stored in burglar.mat and instigate a global search. At each node, so long as the current solution is both LP optimal and integer infeasible, we truncate the solution values to create a feasible integer solution. We then update the cutoff, if the new objective value has improved it, and continue the search.

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

   file knapsack.c
   ````````````````
   Apply a primal heuristic to a knapsack problem.
   The program demonstrates the use of the global log callback.

   We take the knapsack problem stored in burglar.mat and instigate a
   global search. At each node, so long as the current solution is
   both LP optimal and integer infeasible, we truncate the solution
   values to create a feasible integer solution. We then update the
   cutoff, if the new objective value has improved it, and continue
   the search.

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

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

XPRSprob probg;

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

/* Global variables */
double *x;                             /* Nodal LP solution values */
double *gpObjCoef;                     /* Objective function coefficients */
double gdIntTol;                       /* Integer feasibility tolerance */
int gnCol;                             /* Number of columns */

int main()
{
   int nReturn;                        /* Return value of Optimizer subroutine */
   int nOptimizerVersion;              /* Optimizer version number */
   char sProblem[]="burglar";          /* Problem name */
   char sLogFile[]="knapsack.log";     /* Log file name */
   int nExpiry;
   char cOptMessage[200];
   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);

   /* 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 disallow cuts - to slow solution and allow the
      effect of the heuristic to be seen */
   if (nReturn=XPRSsetintcontrol(probg,XPRS_PRESOLVE,0)) errormsg("XPRSsetintcontrol",__LINE__,nReturn);
   if (nReturn=XPRSsetintcontrol(probg,XPRS_CUTSTRATEGY,0)) errormsg("XPRSsetintcontrol",__LINE__,nReturn);
   if (nReturn=XPRSsetintcontrol(probg,XPRS_HEURSTRATEGY,0)) errormsg("XPRSsetintcontrol",__LINE__,nReturn);

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

   /*** Prepare to apply the heuristic ***/

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

   /* Allocate memory to the coefficient and solution arrays */
   gpObjCoef=malloc(gnCol*sizeof(double));
   x=malloc(gnCol*sizeof(double));
   if (!gpObjCoef || !x) errormsg("malloc",__LINE__,-1);

   /* Get the objective function coefficients */
   if (nReturn=XPRSgetobj(probg,gpObjCoef,0,gnCol-1)) errormsg("XPRSgetobj",__LINE__,nReturn);

   /* Get integer feasibility tolerance */
   if (nReturn=XPRSgetdblcontrol(probg,XPRS_MIPTOL,&gdIntTol))
       errormsg ("XPRSgetdblcontrol",__LINE__,nReturn);

   /* Tell Optimizer to print global information to the log file at each node */
   if (nReturn=XPRSsetintcontrol(probg,XPRS_MIPLOG,3)) errormsg ("XPRSsetintcontrol",__LINE__,nReturn);

   /* Tell Optimizer to call truncsol at each node and apply the heuristic */
   if (nReturn=XPRSsetcboptnode(probg,&truncsol,NULL)) errormsg ("XPRSsetcboptnode",__LINE__,nReturn);

   /*** Perform the global search - in the course of which the heuristic will
    be applied ***/
   if (nReturn=XPRSchgobjsense(probg,XPRS_OBJ_MAXIMIZE)) errormsg ("XPRSchgobjsense",__LINE__,nReturn);
   printf("Applying a primal heuristic to problem %s:-\n\n",sProblem);
   if (nReturn=XPRSmipoptimize(probg,"")) errormsg("XPRSmipoptimize",__LINE__,nReturn);

   /* free memory and close files */
   free(gpObjCoef);
   free(x);

   if (nReturn=XPRSdestroyprob(probg)) errormsg("XPRSdestroyprob",__LINE__,nReturn);
   if (nReturn=XPRSfree()) errormsg("XPRSfree",__LINE__,nReturn);

   return 0;
}

/**********************************************************************************\
* Name:         truncsol                                                           *
* Purpose:      Truncate the LP nodal solution values to create a feasible integer *
*               solution, and update the cutoff value if the new objective value   *
*               has improved it. The heuristic is only applied when the nodal      *
*               solution is both LP optimal and integer infeasible.                *
*               This function is called at each node in the global search.         *
* Arguments:    None                                                               *
* Return Value: 0                                                                  *
\**********************************************************************************/

int XPRS_CC truncsol(XPRSprob prob, void* data, int *feas)
{
   int nReturn;               /* Return value of Optimizer subroutine */
   int nNodNum;               /* Number of nodes solved */
   double dObjVal;            /* Objective value */
   double dCutoff;            /* Cutoff value */
   int nLPStatus;             /* LP solution status */
   int nIntInf;               /* Number of integer infeasibilities */
   int i;                     /* Loop counter */
   int solfile;               /* save SOLUTIONFILE status */
   double dHeurObj;           /* Objective value after the solution values
                                 have been truncated*/
   char *sLPStatus[]=         /* LP solution status - literal version */
                {"Optimal","Infeasible","Objective worse than cutoff",
                 "Unfinished","Unbounded","Cutoff in dual"};

   /* Get the current node number  */
   if (nReturn=XPRSgetintattrib(prob,XPRS_NODES,&nNodNum))
   		errormsg("XPRSgetintattrib",__LINE__,nReturn);

   /* Get objective value at the current node */
   if (nReturn=XPRSgetdblattrib(prob,XPRS_LPOBJVAL,&dObjVal))
   		errormsg("XPRSgetdblattrib",__LINE__,nReturn);

   /* Get the current cutoff value */
   if (nReturn=XPRSgetdblcontrol(prob,XPRS_MIPABSCUTOFF,&dCutoff))
   		errormsg("XPRSgetdblcontrol",__LINE__,nReturn);

   /* Get LP solution status and the number of integer infeasibilities */
   if (nReturn=XPRSgetintattrib(prob,XPRS_LPSTATUS,&nLPStatus))
   		errormsg("XPRSgetintattrib",__LINE__,nReturn);
   if (nReturn=XPRSgetintattrib(prob,XPRS_MIPINFEAS,&nIntInf))
   		errormsg("XPRSgetintattrib",__LINE__,nReturn);

   /* Apply heuristic if nodal solution is LP optimal and integer infeasible */
   if (nLPStatus == 1 && nIntInf>0) {

      /* Get LP solution */
      if (nReturn=XPRSgetlpsol(prob,x,NULL,NULL,NULL))
         errormsg("XPRSgetlpsol",__LINE__,nReturn);

      /* Truncate each solution value - making allowance for the integer
         tolerance - and calculate the new "heuristic" objective value */
      for (dHeurObj=0, i=0; i<gnCol; i++) {
         dHeurObj += gpObjCoef[i] * (int) (x[i] + gdIntTol);
      }
      printf("   Node %d: Objective Value: ORIGINAL %g;  HEURISTIC %g\n\n",
         nNodNum,dObjVal,dHeurObj);

      /* If the "heuristic" objective value is better, update the cutoff -
         we assume that all the objective coefficents are integers */
      if( dHeurObj > dCutoff) {
         if (nReturn=XPRSsetdblcontrol(prob,XPRS_MIPABSCUTOFF,dHeurObj + 0.9999))
            errormsg("XPRSsetdblcontrol",__LINE__,nReturn);
         printf("              ** Cutoff updated to %g **\n\n",dHeurObj+1.0);
      }
   }

   /* If the nodal solution is not LP optimal do not apply the heuristic */
   else if (nLPStatus != 1) {
      printf("   Node %d: LP solution not optimal, not applying heuristic\n",nNodNum);
      printf("           (%s)\n\n",sLPStatus[nLPStatus-1]);
   }

   /* If the nodal solution is integer feasible print the objective value */
   else if (nIntInf == 0)
      printf("   Node %d: Integer solution found: Objective Value %g\n\n",
         nNodNum,dObjVal);

   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 Type:  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);
}