Apply a primal heuristic to a knapsack problem
|
|
|
| Type: | Knapsack problem |
| Rating: | 3 (intermediate) |
| Description: | The program demonstrates the use of the global log callback. We take the knapsack problem stored in burglar.mps 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. |
| File(s): | knapsack.c |
| Data file(s): | burglar.mps |
|
|
|
| knapsack.c |
/***********************************************************************
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.mps 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[XPRS_MAXBANNERLENGTH];
/* 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);
}
|