/* ====================================================================== GENERATOR2.c, David Pisinger nov 1997 ====================================================================== */ /* This is a test generator from the paper: * * S. Martello, D. Pisinger, P. Toth * Dynamic programming and tight bounds for the 0-1 knapsack problem * submitted * * The current code generates randomly generated instances and * writes them to a file. Different capacities are considered to * ensure proper testing. * * The code has been tested on a hp9000/735, and conforms with the * ANSI-C standard apart from some of the timing routines (which may * be removed). To compile the code use: * * cc -Aa -O -o gen2 gen2.c -lm * * The code is run by issuing the command * * gen2 n r type i S * * where n: number of items, * r: range of coefficients, * type: 1=uncorrelated, 2=weakly corr, 3=strongly corr, * 4=inverse str.corr, 5=almost str.corr, 6=subset-sum, * 7=even-odd subset-sum, 8=even-odd knapsack, * 9=uncorrelated, similar weights, * 11=Avis subset-sum, 12=Avis knapsack, 13=collapsing KP, * 14=bounded strongly corr, 15=No small weights * i: instance no * S: number of tests in series (typically 1000) * output will be written to the file "test.in". * * Please do not re-distribute. A new copy can be obtained by contacting * the author at the adress below. Errors and questions are refered to: * * David Pisinger, associate professor * DIKU, University of Copenhagen, * Universitetsparken 1, * DK-2100 Copenhagen. * e-mail: pisinger@diku.dk * fax: +45 35 32 14 01 */ #include #include #include #include #include #include /* ====================================================================== macros ====================================================================== */ #define srand(x) srand48x(x) #define randm(x) (lrand48x() % (x)) #define NO(f,i) ((int) ((i+1)-f)) typedef int (*funcptr) (const void *, const void *); #define TRUE 1 #define FALSE 0 /* ====================================================================== type declarations ====================================================================== */ typedef int boolean; /* boolean variables */ typedef short itype; /* item profits and weights */ typedef long stype; /* sum of pofit or weight */ /* item */ typedef struct { itype p; /* profit */ itype w; /* weight */ boolean x; /* solution variable */ } item; /* ======================================================================= random ======================================================================= */ /* to generate the same instances as at HP9000 - UNIX, */ /* here follows C-versions of SRAND48, and LRAND48. */ unsigned long _h48, _l48; void srand48x(long s) { _h48 = s; _l48 = 0x330E; } long lrand48x(void) { _h48 = (_h48 * 0xDEECE66D) + (_l48 * 0x5DEEC); _l48 = _l48 * 0xE66D + 0xB; _h48 = _h48 + (_l48 >> 16); _l48 = _l48 & 0xFFFF; return (_h48 >> 1); } /* ====================================================================== error ====================================================================== */ void error(char *str, ...) { va_list args; va_start(args, str); vprintf(str, args); printf("\n"); va_end(args); printf("STOP !!!\n\n"); exit(-1); } /* ====================================================================== palloc ====================================================================== */ void pfree(void *p) { if (p == NULL) error("freeing null"); free(p); } void * palloc(size_t no, size_t each) { long size; long *p; size = no * (long) each; if (size == 0) size = 1; if (size != (size_t) size) error("alloc too big %ld", size); p = malloc(size); if (p == NULL) error("no memory size %ld", size); return p; } /* ====================================================================== showitems ====================================================================== */ void showitems(item *f, item *l, stype c) { item *i; stype ps, ws; FILE *out; out = fopen("test.in", "w"); if (out == NULL) error("no file"); fprintf(out,"%d\n", NO(f,l)); for (i = f; i <= l; i++) { fprintf(out, "%5d %5d %5d\n", NO(f,i), i->p, i->w); } fprintf(out,"%d\n", c); fclose(out); } /* ====================================================================== makecol ====================================================================== */ int icomp(item *a, item *b) { return b->w - a->w; } stype makecol(item *fitem, item *litem, itype rp, itype rw, stype b, int m) { register item *i, *k, *f, *l; register stype psum, wsum, csum; int h, n, nn; nn = NO(fitem,litem); if (m > nn/2) m = nn/2; litem = fitem + nn/2 + m - 1; /* only m big items */ f = fitem; l = litem; psum = 0; wsum = 0; csum = 0; n = nn / 2; k = f + n; for (i = f; i != k; i++) { i->p = randm(rp) + 1; i->w = randm(rw) + 1; i->x = 0; psum += i->p; wsum += i->w; } for (i = k, h = 1; i <= l; i++, h++) { i->w = randm(b); i->p = 0; i->x = 0; if (h > m) i->w = 0; csum += i->w; } qsort(k, n, sizeof(item), (funcptr) icomp); /* convert the problem */ for (i = f; i != k; i++) { i->p += psum; i->w += wsum; } for (i = k, h = n + 1; i <= l; i++, h++) { i->p = (3*n + 1 - h) * psum; i->w = (4*n - h) * wsum - i->w; } /* printf("psum %ld, wsum %ld, csum %ld\n", psum, wsum, csum); */ return 3*n*wsum; } /* ====================================================================== maketest ====================================================================== */ stype maketest(item *f, item *l, int r, int type, int v, int S) { register item *i, *j; register stype wsum, psum, c; register itype r1; int n, m, k, h; wsum = 0; psum = 0; r1 = r / 10; n = NO(f,l); for (i = f, h = 1; i <= l; i++, h++) { i->w = randm(r) + 1; switch (type) { case 1: i->p = randm(r) + 1; /* uncorrelated */ break; case 2: i->p = randm(2*r1+1) + i->w - r1; /* weakly corr */ if (i->p <= 0) i->p = 1; break; case 3: i->p = i->w + r1; /* strongly corr */ break; case 4: i->p = i->w; /* inverse strongly corr */ i->w = i->p + r1; break; case 5: i->p = i->w + r1 + randm(2*r/1000+1) - r/1000; /* alm str.corr */ break; case 6: i->p = i->w; /* subset sum */ break; case 7: i->w = 2*((i->w + 1)/2); /* even-odd */ i->p = i->w; break; case 8: i->w = 2*((i->w + 1)/2); /* even-odd knapsack */ i->p = i->w + r1; break; case 9: i->p = i->w; /* uncorrelated, similar weights */ i->w = randm(r1) + 100*(itype) r; break; case 11: i->w = n*(n+1) + h; /* Avis subset sum */ i->p = i->w; break; case 12: i->w = n*(n+1) + h; /* Avis knapsack */ i->p = randm(1000); break; case 13: i->p = i->w = 0; /* collapsing KP is generated separatly */ break; case 14: i->p = i->w + r1; /* bounded strongly corr */ m = randm(10)+1; for (k = 1, j = i; m != 0; k=2*k) { if (j > l) break; if (k > m) k = m; j->p = k * i->p; j->w = k * i->w; wsum += j->w; psum += j->p; m -= k; j++; } i = j-1; wsum -= i->w; psum -= i->p; /* avoid double addition */ break; case 15: i->w = randm(r/2) + r/2; /* No small weights */ i->p = randm(2*r1+1) + i->w - r1; if (i->p <= 0) i->p = 1; break; default: error("undefined problem type"); } wsum += i->w; psum += i->p; } c = (v * (double) wsum) / (S + 1); for (i = f; i <= l; i++) if (i->w > c) c = i->w; printf("test %d: wsum %ld, psum %ld, cap %ld\n", v, wsum, psum, c); switch (type) { case 1: return c; case 2: return c; case 3: return c; case 4: return c; case 5: return c; case 6: return c; case 7: return 2*(c/2) + 1; case 8: return 2*(c/2) + 1; case 9: return c; case 11: return n*(n+1) * ((n-1)/2) + ((n*(n-1))/2); case 12: return n*(n+1) * ((n-1)/2) + ((n*(n-1))/2); case 13: return makecol(f, l, 300, 1000, 10000, 100); case 14: return c; case 15: return c; default: error("undefined capacity type"); } } /* ====================================================================== main ====================================================================== */ void main(int argc, char *argv[]) { item *f, *l; int n, r, type, i, S; stype c; if (argc == 6) { n = atoi(argv[1]); r = atoi(argv[2]); type = atoi(argv[3]); i = atoi(argv[4]); S = atoi(argv[5]); printf("generator2 %d %d %d %d %d\n", n, r, type, i, S); } else { printf("generator2\n"); printf("n = "); scanf("%d", &n); printf("r = "); scanf("%d", &r); printf("t = "); scanf("%d", &type); printf("i = "); scanf("%d", &i); printf("S = "); scanf("%d", &S); } f = palloc(n, sizeof(item)); l = f + n-1; c = maketest(f, l, r, type, i, S); showitems(f, l, c); pfree(f); }