/* Copyright (C) 2001 Dale Schuurmans, Finnegan Southey */ /* This work is licensed under the Gnu General Public License (see gpl.txt). */ /* An independent re-implementation of the Casanova solver. */ /* (Hoos & Boutlier 2000) */ #include #include #include #include #include "cop.h" typedef double REAL; int n, m, N, M; int *X, *A, *nCs, **Cs, **Ccoefs; int *B, *nXs, **Xs, **Xcoefs; int MaxCoef, MinB, MaxB; int steps, dsteps, considered, r; int opt, minfeasobj; int *touch, **competitors, *numcompet, *loss; int *xout, *whereout, *time, *solution; int *AA, maxopt; REAL *score; void ALLOCATE(double par1, double par2, int par3, int par4, double par5, int par6, int par7) { int x, xx, i, c, j; AA = (int *) calloc(n, sizeof(int)); loss = (int *) calloc(n, sizeof(int)); for (x = 0; x < n; x++) AA[x] = -A[x]; maxopt = -opt; touch = (int *) calloc(n, sizeof(int)); competitors = (int **) calloc(n, sizeof(int *)); numcompet = (int *) calloc(n, sizeof(int)); for (x = 0; x < n; x++) competitors[x] = (int *) calloc(n, sizeof(int)); xout = (int *) calloc(n, sizeof(int)); whereout = (int *) calloc(n, sizeof(int)); time = (int *) calloc(n, sizeof(int)); solution = (int *) calloc(n, sizeof(int)); score = (REAL *) calloc(n, sizeof (REAL)); for (x = 0; x < n; x++) { numcompet[x] = 0; for (xx = 0; xx < n; xx++) if (xx == x) touch[xx] = 1; else touch[xx] = 0; for (j = 0; j < nCs[x]; j++) { c = Cs[x][j]; for (i = 0; i < nXs[c]; i++) if ( !touch[ xx = Xs[c][i] ] ) { competitors[x][ numcompet[x]++ ] = xx; touch[xx] = 1; }; } } } void SEARCH(double par1, double par2, int par3, int par4, double par5, int par6, int par7) { int R = par3; int T = par4; double wp = par1; double np = par2; int WP = (int) (1.0/wp + 0.5); int NP = (int) (1.0/np + 0.5); int x, xx, i, j, numout, xflip, x2, t; int curval, maxval, curloss, numsolution; REAL maxscore, score2; steps = considered = dsteps = maxval = 0; for (r = 0; r < R; r++) { /*******************************************/ for (x = 0; x < n; x++) { X[x] = -1; xout[x] = x; whereout[x] = x; time[x] = 0; loss[x] = 0; } numout = n; curval = 0; considered++; for (t = 0; t < T; t++) { /***************************/ if (maxval >= -opt) break; maxscore = score2 = -DBL_MAX; xflip = x2 = -1; if (lrand48()%WP == 0) { xflip = xout[lrand48()%numout]; } else { for (i = 0; i < numout; i++) { x = xout[i]; score[x] = (AA[x] - loss[x]) / (REAL) nCs[x]; if (score[x] > maxscore || (score[x] == maxscore && time[x] < time[xflip])) { score2 = maxscore; maxscore = score[x]; x2 = xflip; xflip = x; } else if (score[x] > score2 || (score[x] == score2 && time[x] < time[x2])) { score2 = score[x]; x2 = x; } } if (time[xflip] > time[x2] && lrand48()%NP == 0) { xflip = x2; } } steps++; considered += numout; X[xflip] = 1; time[xflip] = t; loss[xflip] = 0; numout--; xout[whereout[xflip]] = xout[numout]; whereout[xout[numout]] = whereout[xflip]; xout[numout] = xflip; whereout[xflip] = numout; curloss = 0; for (i = 0; i < numcompet[xflip]; i++) { x = competitors[xflip][i]; loss[x] += AA[xflip]; if (X[x] > 0) { X[x] = -1; curloss += AA[x]; xout[whereout[x]] = xout[numout]; whereout[xout[numout]] = whereout[x]; xout[numout] = x; whereout[x] = numout; numout++; for (j = 0; j < numcompet[x]; j++) { xx = competitors[x][j]; if (xx != xflip) loss[xx] -= AA[x]; } } } curval += AA[xflip] - curloss; if (curval > maxval) { maxval = curval; for (i = 0; i < n - numout; i++) solution[i] = xout[numout+i]; numsolution = n - numout; /* checkval = 0; for (i = numout; i < n; i++) checkval += A[xout[i]]; printf("r%d t%d mv%d: ", r, t, checkval); for (i = numout; i < n; i++) printf("x%d ", xout[i]); printf("\n"); */ } } /***************************/ if (maxval >= -opt) break; } /*******************************************/ minfeasobj = -maxval; /* checkval = 0; for (i = 0; i < numsolution; i++) checkval += A[solution[i]]; printf("final value=%d\n", checkval); printf("bids: "); for (i = 0; i < numsolution; i++) printf("%d ", solution[i]); printf("\n"); */ } void CLEANUP() { int x; free(AA); free(loss); free(touch); free(numcompet); free(xout); free(whereout); free(time); free(solution); free(score); for (x = 0; x < n; x++) free(competitors[x]); free(competitors); }