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

Loading MIP solutions into the Optimizer

Description
At each node of the global search a variable fixing heuristic is applied to a copy of the problem. If an integer solution is found for the modified (sub)problem then this solution is loaded into the original problem.

loadmipsol.zip[download all files]

Source Files

Data Files





loadmipsol.c

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

   file loadmipsol.c
   ````````````````
   Implement a rounding type heuristic in the optnode callback
   to demonstrate how to load solutions into the optimizer.

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


#include "stdlib.h"
#include "stdio.h"
#include "memory.h"
#include "math.h"
#include "xprs.h"

#if defined(WIN32) || defined(_WIN32)
#include "windows.h"
#else
#include "pthread.h"
#endif

/**********************************************************************************\
* 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(XPRSprob probg, const char *sSubName,int nLineNo,int nErrCode)
{
  int nErrNo = -1;             /* Optimizer error number */

  /* Append Optimizer error number, if available */
  if(probg && nErrCode==32) {
    XPRSgetintattrib(probg,XPRS_ERRORCODE,&nErrNo);
  }

  /* Print error message */
  printf("ERROR:%s(%d):Failure in function '%s' : Return : %d : Error : %d\n", __FILE__, __LINE__, sSubName, nErrCode, nErrNo);

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

#define GetProb_XPRSchgbounds(a1,a2,a3,a4,a5) a1
#define GetProb_XPRScopycontrols(a1,a2) a1
#define GetProb_XPRScopyprob(a1,a2,a3) a1
#define GetProb_XPRScreateprob(a1) *(a1)
#define GetProb_XPRSgetbanner(a1) NULL
#define GetProb_XPRSgetdblattrib(a1,a2,a3) a1
#define GetProb_XPRSgetdblcontrol(a1,a2,a3) a1
#define GetProb_XPRSgetglobal(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10) a1
#define GetProb_XPRSgetintattrib(a1,a2,a3) a1
#define GetProb_XPRSgetlpsol(a1,a2,a3,a4,a5) a1
#define GetProb_XPRSgetmipsol(a1,a2,a3) a1
#define GetProb_XPRSgetprobname(a1,a2) a1
#define GetProb_XPRSglobal(a1) a1
#define GetProb_XPRSinit(a1) NULL
#define GetProb_XPRSloadmipsol(a1,a2,a3) a1
#define GetProb_XPRSminim(a1,a2) a1
#define GetProb_XPRSpostsolve(a1) a1
#define GetProb_XPRSreadbasis(a1,a2,a3) a1
#define GetProb_XPRSreadprob(a1,a2,a3) a1
#define GetProb_XPRSsetcbmessage(a1,a2,a3) a1
#define GetProb_XPRSsetcboptnode(a1,a2,a3) a1
#define GetProb_XPRSsetdblcontrol(a1,a2,a3) a1
#define GetProb_XPRSsetintcontrol(a1,a2,a3) a1
#define GetProb_XPRSsetprobname(a1,a2) a1
#define GetProb_XPRSwritebasis(a1,a2,a3) a1


#define ERROR_EXIT(msg)                                                      \
{                                                                            \
  printf("ERROR:%s(%d):%s\n", __FILE__, __LINE__, msg);                      \
  exit(1);                                                                   \
}                                                                            \

#define CHECKED_RETURN(function, args)                                       \
{                                                                            \
  int _nReturn;                                                              \
  if ( ((_nReturn = function args) != 0 ) )  {                               \
    XPRSprob prob_with_failure = GetProb_##function args;                    \
    errormsg(prob_with_failure, #function,__LINE__,_nReturn);                \
  }                                                                          \
}                                                                            \

struct FixedSearchMainContext_s {
  char sProbName[256];
  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 */
};


struct FixedSearchLocalContext_s {
  char sProbName[256];
  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 - always 'B', since both the upper and lower bounds are to be changed */
  double *pBndVal;                    /* New bound values */

  /* Solution information */
  double *x;                          /* MIP and LP solution values */
};

void *GetCurrentThreadHandle()
{
#if defined(WIN32) || defined(_WIN32)
  return (void *) GetCurrentThreadId();
#else
  return (void *) pthread_self();
#endif
}

void XPRS_CC Message(XPRSprob prob, void* my_object, const char *msg, int len, int msgtype)
{
  struct FixedSearchMainContext_s *Context = (struct FixedSearchMainContext_s *) my_object;
  switch(msgtype)
  {
  case 4: /* error */
  case 3: /* warning */
  case 2: /* dialogue */
  case 1: /* information */
    printf("%0p:%s\n", GetCurrentThreadHandle(), msg);
    break;
  default: /* exiting - buffers need flushing */
    fflush(stdout);
    break;
  }
}

void AllocateLocalContext(struct FixedSearchMainContext_s *MainContext, struct FixedSearchLocalContext_s *LocalContext,  const int bAllocateOtherwiseDeallocate)
{
  if(!bAllocateOtherwiseDeallocate) {
    free(LocalContext->x);
    free(LocalContext->pBndInd);
    free(LocalContext->pBndVal);
    free(LocalContext->pBndType);
  } else {

    LocalContext->pGlInd = MainContext->pGlInd;
    LocalContext->pGlType = MainContext->pGlType;

    memcpy(LocalContext->sProbName, MainContext->sProbName, sizeof(LocalContext->sProbName));
    LocalContext->nCol = MainContext->nCol;
    LocalContext->nGlEnt = MainContext->nGlEnt;
    LocalContext->nSet = MainContext->nSet;

    /* Allocate memory for MIP solution array and check for memory shortage */
    LocalContext->x=malloc(LocalContext->nCol * sizeof(double));
    if (!LocalContext->x) ERROR_EXIT("malloc");

    /* Allocate memory for bound arrays */
    LocalContext->pBndInd=malloc(LocalContext->nGlEnt * sizeof(int));
    LocalContext->pBndVal=malloc(LocalContext->nGlEnt * sizeof(double));
    LocalContext->pBndType=malloc(LocalContext->nGlEnt * sizeof(char));
    if (!LocalContext->pBndInd || !LocalContext->pBndVal || !LocalContext->pBndType) ERROR_EXIT("malloc");
  }
}

void AllocateMainContext(XPRSprob prob, struct FixedSearchMainContext_s *Context, const int bAllocateOtherwiseDeallocate)
{
  if(!bAllocateOtherwiseDeallocate) {
    free(Context->pGlInd);
    free(Context->pGlType);
  } else {

    CHECKED_RETURN( XPRSgetprobname, (prob, Context->sProbName) );
    CHECKED_RETURN( XPRSgetintattrib, (prob,XPRS_COLS,&Context->nCol) );
    CHECKED_RETURN( XPRSgetintattrib, (prob,XPRS_MIPENTS,&Context->nGlEnt) );
    CHECKED_RETURN( XPRSgetintattrib, (prob,XPRS_SETS,&Context->nSet) );

    /* Allocate memory for global entity arrays */
    Context->pGlInd=malloc(Context->nCol * sizeof(int));
    Context->pGlType=malloc(Context->nCol * sizeof(char));
    if (!Context->pGlInd || !Context->pGlType) ERROR_EXIT("malloc");

    /* Retrieve global entity information */
    CHECKED_RETURN( XPRSgetglobal, (prob,&Context->nGlEnt,&Context->nSet,Context->pGlType,Context->pGlInd,NULL,NULL,NULL,NULL,NULL) );
  }
}

void FixedSearch(XPRSprob parent, struct FixedSearchMainContext_s *MainContext)
{
  int nBnd, i, j, iMipInfeas, iMipSols, iLoadMipSolStatus, bHasMipIncumbent;
  XPRSprob probg, emptyprob;
  double dRounded, dMipTol, dMipIncumbent;
  char sTempProbName[256 + 32 + 1];
  struct FixedSearchLocalContext_s LocalContext;

  /* Only run the search for solutions with small numbers of integer infeasibilities */
  CHECKED_RETURN( XPRSgetintattrib, (parent,XPRS_MIPINFEAS,&iMipInfeas) );
  if(iMipInfeas > 0.25*MainContext->nGlEnt) {
    goto exit_with_skip_search;
  }

  /* Create resources we need */
  AllocateLocalContext(MainContext, &LocalContext,  1);

  /* Create a problem containing the original problem */
  CHECKED_RETURN( XPRScreateprob, (&probg) );
  CHECKED_RETURN( XPRScopyprob, (probg, parent, LocalContext.sProbName) );
  CHECKED_RETURN( XPRSpostsolve, (probg) );

  /* Reset the controls of the problem and restore the name of the problem */
  CHECKED_RETURN( XPRScreateprob, (&emptyprob) );
  CHECKED_RETURN( XPRScopycontrols, (probg, emptyprob) );
  XPRSdestroyprob(emptyprob);

  /* Rename the problem so we don't get collisions with temporary files produced by the optimizer */
  sprintf(sTempProbName, "%s_%0p",LocalContext.sProbName, GetCurrentThreadHandle());
  CHECKED_RETURN( XPRSsetprobname, (probg,sTempProbName) );

  /* Tell Optimizer to call Message whenever a message is output */
  CHECKED_RETURN( XPRSsetcbmessage, (probg,Message,&LocalContext) );

  /* Get information from the solution at the current node of 'parent' problem */
  CHECKED_RETURN( XPRSgetintattrib, (parent,XPRS_MIPSOLS,&bHasMipIncumbent) );
  CHECKED_RETURN( XPRSgetdblattrib, (parent,XPRS_MIPOBJVAL,&dMipIncumbent) );

  CHECKED_RETURN( XPRSgetlpsol, (parent,LocalContext.x,NULL,NULL,NULL) );

  /* Initialise bound counter */
  nBnd = 0;

  CHECKED_RETURN( XPRSgetdblcontrol, (parent,XPRS_MIPTOL,&dMipTol) );

  /* Go through global entities */
  for(i=0; i<LocalContext.nGlEnt; i++) {
    /* Test whether each is a binary or integer variable */
    if (LocalContext.pGlType[i] == 'B' || LocalContext.pGlType[i] == 'I') {
      j = LocalContext.pGlInd[i];

      /* Fix variables that are fractional */
      dRounded = (double) (int)(LocalContext.x[j]+0.5);
      if(fabs(dRounded - LocalContext.x[j]) <= dMipTol) {
        continue;
      }
      LocalContext.pBndInd[nBnd] = j;
      LocalContext.pBndVal[nBnd] = dRounded;
      LocalContext.pBndType[nBnd] = 'B';
      nBnd++;
    }
  }

  /* Instruct Optimizer to change the bounds */
  CHECKED_RETURN( XPRSchgbounds, (probg,nBnd,LocalContext.pBndInd,LocalContext.pBndType,LocalContext.pBndVal) );
  printf("%0p:After global the %d binary and integer variables were fixed\n",GetCurrentThreadHandle(), nBnd);

  /*
  Ensure we only do a small search in the fixed problem and
  use the current incumbent objective from the main problem
  */
  CHECKED_RETURN( XPRSsetintcontrol, (probg,XPRS_MAXNODE,100) );
  CHECKED_RETURN( XPRSsetintcontrol, (probg,XPRS_MAXMIPSOL,1) );
  if(bHasMipIncumbent) {
    /* Set a cut-off to help the fixed search */
    CHECKED_RETURN( XPRSsetdblcontrol, (probg,XPRS_MIPABSCUTOFF,dMipIncumbent) );
  }
  CHECKED_RETURN( XPRSsetintcontrol, (probg,XPRS_MIPLOG,3) );

  /* Read the basis for the LP relaxation to reduce run time */
  CHECKED_RETURN( XPRSreadbasis, (probg,LocalContext.sProbName,"") );

  /* Run the optimizer */
  CHECKED_RETURN( XPRSminim, (probg,"g") );

  /* If we found a solution then load it into the main problem */
  CHECKED_RETURN( XPRSgetintattrib, (probg,XPRS_MIPSOLS,&iMipSols) );
  if(iMipSols > 0) {
    CHECKED_RETURN( XPRSgetmipsol, (probg,LocalContext.x,NULL) );
    CHECKED_RETURN( XPRSloadmipsol, (parent,LocalContext.x, &iLoadMipSolStatus) );
  }

  /* Free the resources we have created */
  XPRSdestroyprob(probg);
  AllocateLocalContext(MainContext, &LocalContext,  0);

exit_with_skip_search:;
  return;
}

void XPRS_CC OptNodeCb(XPRSprob my_prob, void *my_object, int *feas)
{
  struct FixedSearchMainContext_s *Context = (struct FixedSearchMainContext_s *) my_object;
  FixedSearch(my_prob, Context);
}

int main(void) {
  XPRSprob prob;
  int iMipStat;
  char banner[256];
  const char *sProbName = "loadmipsol";
  struct FixedSearchMainContext_s Context = {0};

  CHECKED_RETURN( XPRSinit, ("") );

  CHECKED_RETURN( XPRSgetbanner, (banner) );
  printf("%s\n", banner);

  CHECKED_RETURN( XPRScreateprob, (&prob) );

  CHECKED_RETURN( XPRSreadprob, (prob,sProbName,"") );

  /* Register the message callback */
  CHECKED_RETURN( XPRSsetcbmessage, (prob,Message,&Context) );

  /* Register the fixed search routine to the optimal node callback */
  CHECKED_RETURN( XPRSsetcboptnode, (prob,OptNodeCb,&Context) );

  /* Make the problem difficult for the optimizer to solve */
  CHECKED_RETURN( XPRSsetintcontrol, (prob,XPRS_CUTSTRATEGY,0) );
  CHECKED_RETURN( XPRSsetintcontrol, (prob,XPRS_HEURSTRATEGY,0) );
  CHECKED_RETURN( XPRSsetintcontrol, (prob,XPRS_SBBEST,0) );
  CHECKED_RETURN( XPRSsetintcontrol, (prob,XPRS_MIPTHREADS,20) );

  /* Log every node in the branch-and-bound search */
  CHECKED_RETURN( XPRSsetintcontrol, (prob,XPRS_MIPLOG,3) );

  /* Setup some resources we need in the callbacks */
  AllocateMainContext(prob, &Context, 1);

  /* Solve the LP and write out the basis (to reduce solve time of the fixed problems) */
  CHECKED_RETURN( XPRSminim, (prob,"") );
  CHECKED_RETURN( XPRSwritebasis, (prob,"","") );

  /* Run the MIP search */
  CHECKED_RETURN( XPRSglobal, (prob) );

  /* Free the resources */
  AllocateMainContext(prob, &Context, 0);
  XPRSdestroyprob(prob);
  XPRSfree();

  return 0;
}

Back to examples browserPrevious exampleNext example