/* Linear Assignment Problem * * Given a set of n agents and n tasks, assign tasks to agent such that * every agent has a unique task --- and, of course, every task has * someone performing it. Find the optimal such assignment --- for our * purposes here, the one with the largest total benefit. * * There is a global matrix benefit[MAX_SIZE][MAX_SIZE] which contains * for each value of row and col the benefit of assigning agent row to * task col. Because of how C behaves, this has been set to a maximum * size, given in a #define. Also at the global level is a vector to * receive the solution and a variable to hold the value of the solution * --- this is updated as the backtracking discovered permutations with * a better value that the presently stored permutation. * * The initial solution is generated as one of the two trivial solutions * --- either the diagonal solution (0, 1, 2, ...) or the antidiagonal * solution (...,2, 1, 0), whichever has the higher value --- as the sum * over k of benefit[k][solution[k]]. As a known solution, this * provides a lower limit when considering potential permutations. * * One can also quickly obtain an upper limit on a partial permutation. * While we are positioning values as [index], the known value for the * permutation will be the sum up to index of benefit[k][solution[k]]. * Rows from [index+1] to [size-1] have not been assigned yet, and * correspondingly columns from perm[index+1] to perm[size-1] have not * been assigned. One can obtain the column maximum value for each of * those columns and add them together. The complete permutation cannot * possibly have a value greater than the total of its fixed part and * these column maxima, though it well might have one less. If this * number is less than the already-known solution (lowerLimit), one can * immediately prune the decision tree --- discard this partial solution. * * Language: ANSI C * * Author: Timothy Rolfe */ #include // clock() etc. #include #include // memcpy() #include #ifdef _WIN32 // NOT the Unix environment // Use a macro to get double seconds from clock() #define wallClock() ((double)clock()/CLOCKS_PER_SEC) #else #include "cpuTimes.c" #endif // Diagonal/antidiagonal permutation sets solution and lowerLimit #define MAX_SIZE 35 int solution[MAX_SIZE], lowerLimit; int size, benefit[MAX_SIZE][MAX_SIZE]; enum { FALSE, TRUE }; int DEBUG; // Prototype of the permutation exploration procedure void explore(int index, int *vect, int prefix); int main (int argc, char** argv) { const char* filename = argc == 1 ? "Asg5.in" : argv[1]; FILE *input = fopen(filename, "r"); int antisum, row, col, k, *work; double start, elapsed; // Set global variables DEBUG = FALSE; lowerLimit = 0; if (input == NULL) { printf("Failed to open %s\n", filename); exit(0); } fscanf(input, "%d", &size); work = (int*) calloc(size, sizeof *work); // Read in the data. generate the diagonal solution // (row == col) and generate the diagonal total and // the antidiagonal total (row + col == size-1). antisum = 0; k = size; for (row = lowerLimit = 0; row < size; row++) { solution[row] = row; for (col = 0; col < size; col++) fscanf (input, "%d", &benefit[row][col]); lowerLimit += benefit[row][row]; antisum += benefit[row][--k]; } // If the antidiagonal sum is the larger, make that the // initial solution and lowerLimit. if (antisum > lowerLimit) { lowerLimit = antisum; for (row = 0, k = size; row < size; row++) solution[row] = --k; } // Copy it into the global solution vector memcpy(work, solution, size * sizeof *work); // Capture the processing time. start = wallClock(); explore(0, work, 0); elapsed = wallClock() - start; printf("Solution found with value %d\n", lowerLimit); for (row = 0; row < size; row++) printf("%3d", solution[row]); printf("\n%3.3f seconds\n", elapsed); return 0; } // Used by explore in generating the permutations void swap(int *x, int j, int k) { int temp = x[j]; x[j] = x[k]; x[k] = temp; } // Isolate the logic for the total of column maxima int colMaxSum(int start, int *work) { int sum = 0, k; for (k = start; k < size; k++) {//Initial guess: maximum right HERE. int row, col = work[k], columnMaximum = benefit[start][col]; // Update as required. for (row = start+1; row < size; row++) if (columnMaximum < benefit[row][col]) columnMaximum = benefit[row][col]; // Add into the developing sum. sum += columnMaximum; } return sum; } void explore(int index, int vect[], int prefix) { int k, // Loop variable for swapping [index]..[size-1] j, // Spare loop variable hold; // Value of fixed portion of a permutation, // then used undoing the right rotation for ( k = index; k < size; k++ ) { int upperBound; swap(vect, index, k); // Get the next value into place // Add together column maxima upperBound = colMaxSum(index+1, vect); hold = prefix + benefit[index][vect[index]]; // Selecting [size-2] also fixes [size-1] --- // a permutation has been completed. if (index == size-2) { // If this is a BETTER solution than the one in hand if ( lowerLimit < hold+upperBound ) { // Add in the last piece hold += benefit[size-1][vect[size-1]]; if (DEBUG) { printf("Replacing %d with %d: ", lowerLimit, hold); for (j = 0; j < size; j++) printf("%3d", vect[j]); putchar('\n'); } lowerLimit = hold; memcpy(solution, vect, size * sizeof *vect); } else if (DEBUG) { printf("Reject %d: ", hold+upperBound); for (j = 0; j < size; j++) printf("%3d", vect[j]); putchar('\n'); } } // Otherwise we still just have a partial permutation. // If it has potential for finding a better one, pursue it. else if (hold + upperBound > lowerLimit) explore(index+1, vect, hold); else if (DEBUG) { printf("Prune at %d, upper limit %d: ", index, hold + upperBound); for (j = 0; j < size; j++) printf("%3d", vect[j]); putchar('\n'); } } // Undo the one-cell rightward rotation done above hold = vect[index]; for (k = index+1; k < size; k++) vect[k-1] = vect[k]; vect[size-1] = hold; }