/******************************************************** * Program fcmkp_Solver.c * * * * # This program generates random instances of the * * * * Fixed Charge Multiple Knapsack Problem * * * * and output the instances in * * * * MOS (MPS) file format * * * * to be used as input for solvers such as * * * * XPRESS-MP and CPLEX * * * * # To compile: cc -O fcmkp_Solver.c -Aa -lm * * # To run: a.out seed * ********************************************************/ #include #include #include #include #include /****** Constants ******/ #define w_max 1000 /* Weight: [1,w_max] */ #define p_max 1000 /* Profit: [1,p_max] */ #define UNCOR 0 #define WEAK 1 #define STRONG 2 /****** Problem description *****/ #define N 20 /* No. of items */ #define M 8 /* No. of knapsacks */ #define D 0.50 /* Parameter for total knapsack capacitie*/ #define KP_Capa D*(double)(w_max*N/2) /* Total knapsack capacities */ #define CORR WEAK /* Correlation type */ #define PRINT_PROB 1 /* Text file of problem */ #define XPRESS 1 /* Output file : X_SEED.mos */ #define CPLEX 1 /* Output file : C_SEED.mps */ /****** Data structure ******/ struct goods{/* Item */ int class,id; /* used in Surrogate */ long int w,W; /* (cumulative) weight */ double p,P; /* (cumulative) profit */ double r; /* efficiency (p/w) */ double theta; /* thresholds */ int x; int fix; /* Peg result */ }; struct knap{/* Knapsack*/ int id; long int W,Capa,Cost; /* Capacity, cost */ double P,r,cc,theta; int fix; }; /****** Prototypes ******/ /* Generate random instance */ void Setup_Prob(); /* Prepare an instance */ void srandx(unsigned seed); /* Random number generator */ int randx(void); void Quick(struct goods item[],int left,int right); void Quick2(struct knap knap[],int left,int right); void Print_Prob(); /* Show the instance */ void Make_XPRESS_MP(void); void Make_CPLEX(); /****** Global variables ******/ int SEED; struct goods item[N+1]; /* Items */ struct knap knap[M+1]; /* Knapsacks */ static unsigned long nextx=1; /* Random number generator */ /* ------------------------------------ * * Main routine * * ------------------------------------ */ int main(int argc,char *argv[]) { SEED = atoi(argv[1]); srandx(SEED); Setup_Prob(); /* Prepare an instance */ if (PRINT_PROB) Print_Prob(); /* Display the instance */ if(XPRESS) Make_XPRESS_MP(); if(CPLEX) Make_CPLEX(); return 0; } void Setup_Prob() { /* Prepare a random instance */ int i,j; long int P,W; double xi,sum; for (j=1;j<=N;j++){ item[j].w = randx() % w_max + 1; if (CORR==UNCOR) item[j].p = randx()%p_max + 1; else if (CORR==WEAK) item[j].p = item[j].w + randx()%200; else item[j].p = item[j].w + 20; } /* Item efficiency */ for (j=1;j<=N;j++) item[j].r = (double)item[j].p/(double)item[j].w ; /* Sort in the descending order of efficiency */ Quick(item,1,N); /* Cumulative weights and profits */ P=0; W=0; for (j=1;j<=N;j++){ P+=item[j].p; W+=item[j].w; item[j].P=P; item[j].W=W; item[j].id = j; } /* Knapsack capacity, costs */ sum =0.0; for (i=1;i<=M;i++){ knap[i].r = randx()%w_max + 1.0; sum += knap[i].r; } for (i=1;i<=M;i++){ knap[i].id = i; knap[i].r /= sum; knap[i].Capa = KP_Capa*knap[i].r; xi = (double)randx()/32767.0 + 0.5; knap[i].Cost = xi*(double)knap[i].Capa; } /* Knapsack efficiency */ for (i=1;i<=M;i++) knap[i].cc = (double)knap[i].Capa/(double)knap[i].Cost; /* Sort in non-increasing order of efficiency */ Quick2(knap,1,M); /* Knapsacks */ for (i=1;i<=M;i++) knap[i].id = i; } int randx(void) { nextx = nextx*1103515245L + 12345; return (unsigned)(nextx / 65536L) % 32768U; } void srandx(unsigned seed) { nextx=seed; } void Quick(struct goods item[],int left,int right) { /* Quick sort for items */ int i,j; double s; struct goods t; if (lefts); while(item[--j].r=j) break; t = item[i]; item[i] = item[j]; item[j] = t; } Quick(item,left,i-1); Quick(item,j+1,right); } } void Quick2(struct knap knap[],int left,int right) { /* Quick sort for knapsacks */ int i,j; double s; struct knap t; if (lefts); while(knap[--j].cc=j) break; t = knap[i]; knap[i] = knap[j]; knap[j] = t; } Quick2(knap,left,i-1); Quick2(knap,j+1,right); } } void Print_Prob() {/* Display problem */ int i,j,Cap; printf("********** Fixed Charge Multiple Knapsack Problem **********\n"); printf("* CORR=%d, D=%5.2f, N=%d, M=%d, SEED=%d\n",CORR,D,N,M,SEED); printf("*** Items ***\n # profit p weight w cumul. P cumul. W efficiency r\n"); for(j=1;j<=N;j++) printf("%3d %10d %10d %10d %10d %20f\n",j,(int)item[j].p,item[j].w,(int)item[j].P,item[j].W,item[j].r); printf("\n*** knapsacks ***\n # capacity C cost r relativ cost\n"); Cap=0; for(i=1;i<=M;i++){ printf("%3d %10d %10d %10f\n",i,knap[i].Capa,knap[i].Cost,1.0/knap[i].cc); Cap += knap[i].Capa; } printf(" v %10d\n\n",Cap); } void Make_XPRESS_MP(void) {/* Output MOS file for use in XPRESS-MP */ int i,j; char outfile[50]; FILE *fp; sprintf(outfile,"X_%d.mos",SEED); /* output file */ if((fp = fopen(outfile,"w")) == NULL){ printf(" ! failed to open file\n"); exit(1); } fprintf(fp,"model MKSP\n"); fprintf(fp,"uses \"mmxprs\",\"mmsystem\"\n\n"); fprintf(fp,"\tdeclarations\n"); fprintf(fp,"\t\titemn = 1..%d\n",N); fprintf(fp,"\t\titemm = 1..%d\n",M); fprintf(fp,"\t\tobj : array(itemn) of integer\n"); fprintf(fp,"\t\tr : array(itemm) of integer\n"); fprintf(fp,"\t\tw : array(itemn) of integer\n"); fprintf(fp,"\t\tc : array(itemm) of integer\n"); fprintf(fp,"\t\tx : array(itemm,itemn) of mpvar\n"); fprintf(fp,"\t\ty : array(itemm) of mpvar\n"); fprintf(fp,"\tend-declarations\n\n"); fprintf(fp,"\tobj := ["); for(j = 1;j < N;j++){ if(!(j % 10 - 1)){ fprintf(fp,"\n\t\t "); } fprintf(fp,"%4d,",(int)item[j].p); } fprintf(fp,"%4d",(int)item[N].p); fprintf(fp,"]\n"); fprintf(fp,"\tr := ["); for(i = 1;i < M;i++){ if(!(i % 10 - 1)){ fprintf(fp,"\n\t\t "); } fprintf(fp,"%4d,",knap[i].Cost); } fprintf(fp,"%4d",knap[M].Cost); fprintf(fp,"]\n"); fprintf(fp,"\tw := ["); for(j = 1;j < N;j++){ if(!(j % 10 - 1)){ fprintf(fp,"\n\t\t "); } fprintf(fp,"%4d,",item[j].w); } fprintf(fp,"%4d",item[N].w); fprintf(fp,"]\n"); fprintf(fp,"\tc := ["); for(i = 1;i < M;i++){ if(!(i % 10 - 1)){ fprintf(fp,"\n\t\t "); } fprintf(fp,"%4d,",knap[i].Capa); } fprintf(fp,"%4d",knap[M].Capa); fprintf(fp,"]\n"); fprintf(fp,"\tforall(i in itemm,j in itemn) x(i,j) is_binary\n"); fprintf(fp,"\tforall(i in itemm) y(i) is_binary\n\n"); fprintf(fp,"\tTotalObj := sum(i in itemm,j in itemn) x(i,j) * obj(j) - sum(i in itemm) r(i) * y(i)\n\n"); fprintf(fp,"\tforall (i in itemm) sum(j in itemn) w(j) * x(i,j) <= c(i) * y(i)\n"); fprintf(fp,"\tforall (j in itemn) sum(i in itemm) x(i,j) <= 1\n"); fprintf(fp,"\tStarttime := gettime;\n\n"); fprintf(fp,"\t setparam(\"XPRS_MAXTIME\",600)\n\n");/* timeout = 600sec. */ fprintf(fp,"\tmaximize (TotalObj);\n\n"); fprintf(fp,"\twriteln(strfmt(getobjval,0,2),strfmt(gettime - Starttime,7,2));\n"); fprintf(fp,"end-model\n"); fclose(fp); } void Make_CPLEX() {/* Output MPS file for use in CPLEX (also, MPS file can be used in XPRESS-MP) */ int i,j,k,i1,j1,cnt,bdd; FILE *fp1; char xx,outfile1[40]; sprintf(outfile1,"C_%d.mps",SEED); if ((fp1 = fopen(outfile1,"w")) == NULL){ printf(" Failed to open file\n"); exit(1); } fprintf(fp1,"NAME MULTIPLE_KNAPSACK_SELECTION\n"); /* Comment out the following two lines for an MPS file for XPRESS-MP */ fprintf(fp1,"OBJSENSE\n MAX\n"); fprintf(fp1,"OBJNAME \n F\n"); /* ROWS section */ fprintf(fp1,"ROWS\n"); fprintf(fp1," N F\n"); for (i=1;i<=M;i++) fprintf(fp1," L W%04d\n",i); for (j=1;j<=N;j++) fprintf(fp1," L C%04d\n",j); /* COLUMNS section */ fprintf(fp1,"COLUMNS\n"); fprintf(fp1," MARK0000 'MARKER' 'INTORG'\n"); for (i=1;i<=M;i++){ for (j=1;j<=N;j++){ fprintf(fp1," X%02d%03d F %4d.\n",i,j,(int)item[j].p); for (i1=1;i1<=M;i1++){ if (i1==i) fprintf(fp1," X%02d%03d W%04d %4d.\n",i,j,i1,item[j].w); else fprintf(fp1," X%02d%03d W%04d %4d.\n",i,j,i1,0); } for (j1=1;j1<=N;j1++){ if (j1==j) fprintf(fp1," X%02d%03d C%04d %4d.\n",i,j,j1,1); else fprintf(fp1," X%02d%03d C%04d %4d.\n",i,j,j1,0); } } } for (i=1;i<=M;i++){ fprintf(fp1," Y%05d F %4d.\n",i,-knap[i].Cost); for (i1=1;i1<=M;i1++){ if (i1==i) fprintf(fp1," Y%05d W%04d %4d.\n",i,i1,-knap[i1].Capa); else fprintf(fp1," Y%05d W%04d %4d.\n",i,i1,0); } for (j1=1;j1<=N;j1++){ fprintf(fp1," Y%05d C%04d %4d.\n",i,j1,0); } } fprintf(fp1," MARK0001 'MARKER' 'INTEND'\n"); /* RHS section */ fprintf(fp1,"RHS\n"); for (i=1;i<=M;i++) fprintf(fp1," B W%04d %4d.\n",i,0); for (j=1;j<=N;j++) fprintf(fp1," B C%04d %4d.\n",j,1); /* BOUNDS section */ fprintf(fp1,"BOUNDS\n"); for (i=1;i<=M;i++){ fprintf(fp1," UP BND1 Y%05d 1.\n",i); } fprintf(fp1,"ENDATA\n"); fprintf(fp1," \n"); fprintf(fp1," \n"); close(fp1); }