/* nag_mip_tsp_simann (h03bbc) Example Program.
*
* Copyright 2022 Numerical Algorithms Group.
*
* Mark 28.6, 2022.
*/
#include <nag.h>
#include <stdio.h>
#include <string.h>
int main(void) {
/* Scalars */
Integer exit_status = 0;
Integer subid = 53, lseed = 4, lstate;
Integer i, j, l, nc, n_i, icol, col_s, col_f, nrows, tmode;
double bound, targc, cost;
/* Arrays */
Integer seed[] = {304950, 889934, 209094, 23423990};
double alg_stats[6];
Integer *state = 0, *path = 0;
double *dm = 0;
char **cities = 0;
/* Nag Types */
Nag_BaseRNG genid = Nag_WichmannHill_I;
NagError fail;
INIT_FAIL(fail);
printf("nag_mip_tsp_simann (h03bbc) Example Program Results\n\n");
/* Read number of cities from data file */
scanf(" %*[^\n]"); /* Skip heading */
scanf("%" NAG_IFMT " %*[^\n]", &nc);
/* Get the length of the state array for random number generation */
lstate = -1;
nag_rand_init_repeat(genid, subid, seed, lseed, state, &lstate, &fail);
if (fail.code != NE_NOERROR) {
printf("Error from nag_rand_init_repeat (g05kfc).\n%s\n", fail.message);
exit_status = 1;
goto END;
}
/* Allocate arrays using nc and lstate */
if (!(state = NAG_ALLOC(lstate, Integer)) ||
!(path = NAG_ALLOC(nc, Integer)) || !(dm = NAG_ALLOC(nc * nc, double)) ||
!(cities = NAG_ALLOC(nc, char *))) {
printf("Allocation failure\n");
exit_status = 2;
goto END;
}
/* Read distance matrix 10 columns at a time */
/* Define DM for reading distance matrix from file */
#define DM(I, J) dm[(J - 1) * nc + I - 1]
for (icol = 2; icol <= nc; icol = icol + 10) {
/* Skip a line */
scanf(" %" NAG_IFMT " %*[^\n]", &n_i);
col_f = MIN(icol + 9, nc);
nrows = col_f - 1;
for (i = 1; i <= nrows; i++) {
/* Skip row number */
scanf("%" NAG_IFMT "", &n_i);
col_s = MAX(i + 1, icol);
for (j = col_s; j <= col_f; j++) {
scanf("%lf", &DM(i, j));
}
scanf("%*[^\n] ");
}
}
/* Read city names */
for (i = 0; i < nc; i++) {
if (!(cities[i] = NAG_ALLOC(20, char))) {
printf("Allocation failure\n");
exit_status = 3;
goto END;
}
scanf("%" NAG_IFMT " %19s%*[^\n] ", &n_i, cities[i]);
}
/* Initialize the random number generator to a repeatable sequence */
nag_rand_init_repeat(genid, subid, seed, lseed, state, &lstate, &fail);
if (fail.code != NE_NOERROR) {
printf("Error from nag_rand_init_repeat (g05kfc).\n%s\n", fail.message);
exit_status = 4;
goto END;
}
/* Calculate a lower bound internally and try to find lowest cost path. */
bound = -1.0;
targc = -1.0;
/* Find low cost return path through all cities. */
nag_mip_tsp_simann(nc, dm, bound, targc, path, &cost, &tmode, alg_stats,
state, &fail);
if (fail.code != NE_NOERROR) {
printf("Error from nag_mip_tsp_simann (h03bbc).\n%s\n", fail.message);
exit_status = 5;
goto END;
}
printf("Initial search end cost: %12.2f\n", alg_stats[2]);
printf("Search best cost : %12.2f\n", alg_stats[3]);
printf("Initial temperature : %12.2f\n", alg_stats[4]);
printf("Lower bound : %12.2f\n", alg_stats[5]);
printf("Termination mode : %12" NAG_IFMT "\n\n", tmode);
printf("Final cost : %12.2f\n\n", cost);
printf("Final path:\n");
printf(" %s --> %s\n", cities[path[0] - 1], cities[path[1] - 1]);
l = strlen(cities[path[0] - 1]);
for (i = 2; i <= nc - 1; i++) {
printf(" ");
for (j = 0; j < l; j++)
printf(" ");
printf(" --> %s\n", cities[path[i] - 1]);
}
printf(" ");
for (j = 0; j < l; j++)
printf(" ");
printf(" --> %s\n", cities[path[0] - 1]);
END:
NAG_FREE(dm);
NAG_FREE(state);
NAG_FREE(path);
for (i = 0; i < nc; i++) {
NAG_FREE(cities[i]);
}
NAG_FREE(cities);
return exit_status;
}