/* Copyright (C) 2001 Dale Schuurmans, Finnegan Southey */ /* This work is licensed under the Gnu General Public License (see gpl.txt). */ /* Heuristically solve a Constrained Optimization Problem (COP) */ #include #include #include #include "cop.h" int n, m, N, M; int *X, *A, *nCs, **Cs, **Ccoefs; int *B, *nXs, **Xs, **Xcoefs; int MaxCoef, MaxB, MinB; int steps, dsteps, considered, r; int opt, haveopt, minfeasobj; /*********************************************************/ void alloc_and_readCOP(in) FILE *in; { int x, c, var, coef; while (getc(in) != '('); fscanf(in, "%d %d", &n, &m); while (getc(in) != ')'); while (getc(in) != '('); fscanf(in, "%d %d", &N, &M); while (getc(in) != ')'); if (!M) M = MAX_CONS_PER_VAR; if (!N) N = MAX_VARS_PER_CON; /***** allocate COP *****/ X = (int *) calloc(n, sizeof(int)); A = (int *) calloc(n, sizeof(int)); nCs = (int *) calloc(n, sizeof(int)); Cs = (int **) calloc(n, sizeof(int *)); for (x = 0; x < n; x++) Cs[x] = (int *) calloc(M, sizeof(int)); Ccoefs = (int **) calloc(n, sizeof(int *)); for (x = 0; x < n; x++) Ccoefs[x] = (int *) calloc(M, sizeof(int)); B = (int *) calloc(m, sizeof(int)); nXs = (int *) calloc(m, sizeof(int)); Xs = (int **) calloc(m, sizeof(int *)); for (c = 0; c < m; c++) Xs[c] = (int *) calloc(N, sizeof(int)); Xcoefs = (int **) calloc(m, sizeof(int *)); for (c = 0; c < m; c++) Xcoefs[c] = (int *) calloc(N, sizeof(int)); /***** read COP *****/ while (getc(in) != '('); for (x = 0; x < n; x++) fscanf(in, "%d", A+x); while (getc(in) != ')'); MaxCoef = MaxB = 0; MinB = N; for (c = 0; c < m; c++) { while (getc(in) != '('); fscanf(in, "%d %d", B+c, nXs+c); if (nXs[c] > N) { printf("Error: #vars exceeds max vars=%d\n", N); exit(1); } if (B[c] > MaxB) MaxB = B[c]; else if (B[c] < MinB) MinB = B[c]; for (x = 0; x < nXs[c]; x++) { while (getc(in) != '('); fscanf(in, "%d %d", &var, &coef); if (var >= n || var < 0) { printf("Error: illegal variable number=%d out of range\n", var); exit(1); } if (abs(coef) > MaxCoef) MaxCoef = abs(coef); Xs[c][x] = var; Xcoefs[c][x] = coef; Cs[var][nCs[var]] = c; Ccoefs[var][nCs[var]] = coef; nCs[var]++; if (nCs[var] > M) { printf("Error: #constraints exceeds max constraints=%d\n", M); exit(1); } while (getc(in) != ')'); } while (getc(in) != ')'); } /***** Check for known optimal value. *****/ haveopt = 0; while (!feof(in) && getc(in) != '('); if (!feof(in)) { double rawopt; haveopt = 1; fscanf(in, "%lg", &rawopt); opt = (int)rawopt; while (getc(in) != ')'); } if (!haveopt) opt = INT_MIN + 1; /* +1 to avoid overflow issues */ } /*********************************************************/ void freeCOP() { int x, c; free(X); free(A); free(B); free(nXs); free(nCs); for (x = 0; x < n; x++) free(Cs[x]); free(Cs); for (x = 0; x < n; x++) free(Ccoefs[x]); free(Ccoefs); for (c = 0; c < m; c++) free(Xs[c]); free(Xs); for (c = 0; c < m; c++) free(Xcoefs[c]); free(Xcoefs); }