tsp_c.c
/ *版权所有2019，Gurobi 狗万app足彩Optimization，LLC * / / *使用延迟约束在随机生成的点组上解决旅行推销员问题。基础MIP模型仅包括'度-2'约束，要求每个节点具有完全两个入射边缘。此模型的解决方案可能包含子台楼 - 游览每个节点的旅行。延迟约束回调会增加新约束以关闭它们。* / #include #include #include #include“gurobi_c.h”/ *定义了将数据传递给回调函数* / struct callback_data {int n;};/ *给出了一个整数可行的解决方案'sol'，找到最小的子旅行。结果在“巡回赛”中返回，“巡回赛”返回。* /静态void findsubtour（int n，double * sol，int * tourlenp，int * tour）{int i，node，len，开始;int bestind，bestlen; int *seen = NULL; seen = (int *) malloc(n*sizeof(int)); if (seen == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } for (i = 0; i < n; i++) seen[i] = 0; start = 0; bestlen = n+1; bestind = -1; while (start < n) { for (node = 0; node < n; node++) if (seen[node] == 0) break; if (node == n) break; for (len = 0; len < n; len++) { tour[start+len] = node; seen[node] = 1; for (i = 0; i < n; i++) { if (sol[node*n+i] > 0.5 && !seen[i]) { node = i; break; } } if (i == n) { len++; if (len < bestlen) { bestlen = len; bestind = start; } start += len; break; } } } for (i = 0; i < bestlen; i++) tour[i] = tour[bestind+i]; *tourlenP = bestlen; free(seen); } /* Subtour elimination callback. Whenever a feasible solution is found, find the shortest subtour, and add a subtour elimination constraint if that tour doesn't visit every node. */ int __stdcall subtourelim(GRBmodel *model, void *cbdata, int where, void *usrdata) { struct callback_data *mydata = (struct callback_data *) usrdata; int n = mydata->n; int *tour = NULL; double *sol = NULL; int i, j, len, nz; int error = 0; if (where == GRB_CB_MIPSOL) { sol = (double *) malloc(n*n*sizeof(double)); tour = (int *) malloc(n*sizeof(int)); if (sol == NULL || tour == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } GRBcbget(cbdata, where, GRB_CB_MIPSOL_SOL, sol); findsubtour(n, sol, &len, tour); if (len < n) { int *ind = NULL; double *val = NULL; ind = (int *) malloc(len*(len-1)/2*sizeof(int)); val = (double *) malloc(len*(len-1)/2*sizeof(double)); if (ind == NULL || val == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } /* Add subtour elimination constraint */ nz = 0; for (i = 0; i < len; i++) for (j = i+1; j < len; j++) ind[nz++] = tour[i]*n+tour[j]; for (i = 0; i < nz; i++) val[i] = 1.0; error = GRBcblazy(cbdata, nz, ind, val, GRB_LESS_EQUAL, len-1); free(ind); free(val); } free(sol); free(tour); } return error; } /* Euclidean distance between points 'i' and 'j'. */ static double distance(double *x, double *y, int i, int j) { double dx = x[i] - x[j]; double dy = y[i] - y[j]; return sqrt(dx*dx + dy*dy); } int main(int argc, char *argv[]) { GRBenv *env = NULL; GRBmodel *model = NULL; int i, j, len, n, solcount; int error = 0; char name[100]; double *x = NULL; double *y = NULL; int *ind = NULL; double *val = NULL; struct callback_data mydata; if (argc < 2) { fprintf(stderr, "Usage: tsp_c size\n"); exit(1); } n = atoi(argv[1]); if (n == 0) { fprintf(stderr, "Argument must be a positive integer.\n"); } else if (n > 100) { printf("It will be a challenge to solve a TSP this large.\n"); } x = (double *) malloc(n*sizeof(double)); y = (double *) malloc(n*sizeof(double)); ind = (int *) malloc(n*sizeof(int)); val = (double *) malloc(n*sizeof(double)); if (x == NULL || y == NULL || ind == NULL || val == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } /* Create random points */ for (i = 0; i < n; i++) { x[i] = ((double) rand())/RAND_MAX; y[i] = ((double) rand())/RAND_MAX; } /* Create environment */ error = GRBloadenv(&env, "tsp.log"); if (error) goto QUIT; /* Create an empty model */ error = GRBnewmodel(env, &model, "tsp", 0, NULL, NULL, NULL, NULL, NULL); if (error) goto QUIT; /* Add variables - one for every pair of nodes */ /* Note: If edge from i to j is chosen, then x[i*n+j] = x[j*n+i] = 1. */ /* The cost is split between the two variables. */ for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { sprintf(name, "x_%d_%d", i, j); error = GRBaddvar(model, 0, NULL, NULL, distance(x, y, i, j)/2, 0.0, 1.0, GRB_BINARY, name); if (error) goto QUIT; } } /* Degree-2 constraints */ for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { ind[j] = i*n+j; val[j] = 1.0; } sprintf(name, "deg2_%d", i); error = GRBaddconstr(model, n, ind, val, GRB_EQUAL, 2, name); if (error) goto QUIT; } /* Forbid edge from node back to itself */ for (i = 0; i < n; i++) { error = GRBsetdblattrelement(model, GRB_DBL_ATTR_UB, i*n+i, 0); if (error) goto QUIT; } /* Symmetric TSP */ for (i = 0; i < n; i++) { for (j = 0; j < i; j++) { ind[0] = i*n+j; ind[1] = i+j*n; val[0] = 1; val[1] = -1; error = GRBaddconstr(model, 2, ind, val, GRB_EQUAL, 0, NULL); if (error) goto QUIT; } } /* Set callback function */ mydata.n = n; error = GRBsetcallbackfunc(model, subtourelim, (void *) &mydata); if (error) goto QUIT; /* Must set LazyConstraints parameter when using lazy constraints */ error = GRBsetintparam(GRBgetenv(model), GRB_INT_PAR_LAZYCONSTRAINTS, 1); if (error) goto QUIT; /* Optimize model */ error = GRBoptimize(model); if (error) goto QUIT; /* Extract solution */ error = GRBgetintattr(model, GRB_INT_ATTR_SOLCOUNT, &solcount); if (error) goto QUIT; if (solcount > 0) { int *tour = NULL; double *sol = NULL; sol = (double *) malloc(n*n*sizeof(double)); tour = (int *) malloc(n*sizeof(int)); if (sol == NULL || tour == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } error = GRBgetdblattrarray(model, GRB_DBL_ATTR_X, 0, n*n, sol); if (error) goto QUIT; /* Print tour */ findsubtour(n, sol, &len, tour); printf("Tour: "); for (i = 0; i < len; i++) printf("%d ", tour[i]); printf("\n"); free(tour); free(sol); } QUIT: /* Free data */ free(x); free(y); free(ind); free(val); /* Error reporting */ if (error) { printf("ERROR: %s\n", GRBgeterrormsg(env)); exit(1); } /* Free model */ GRBfreemodel(model); /* Free environment */ GRBfreeenv(env); return 0; }
