![]() | |||||||||
| |||||||||
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.
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; }
| |||||||||
Copyright 2017 Fair Isaac Corporation. |