Debian Codegraph @

SYMPHONY/Applications/CNRP/src/Master/cnrp_io.c

raw
1 /*===========================================================================*/
2 /* */
3 /* This file is part of a demonstration application for use with the */
4 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */
5 /* Capacitated Network Routing Problems. */
6 /* */
7 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */
8 /* */
9 /* This application was developed by Ted Ralphs ([email protected]) */
10 /* */
11 /* This software is licensed under the Eclipse Public License. Please see */
12 /* accompanying file for terms. */
13 /* */
14 /*===========================================================================*/
15
16 /* system include files */
17 #include <stdlib.h>
18 #include <stdio.h>
19 #include <string.h>
20 #include <math.h>
21
22 /* SYMPHONY include files */
23 #include "sym_macros.h"
24 #include "sym_types.h"
25 #include "sym_master_u.h"
26 #include "sym_lp_params.h"
27
28 /* CNRP include files */
29 #include "cnrp_io.h"
30 #include "compute_cost.h"
31 #include "cnrp_types.h"
32 #include "cnrp_const.h"
33 #include "cnrp_macros.h"
34
35 #define NUMNODES -1
36
37 /*===========================================================================*/
38
39 /*===========================================================================*\
40 * This file contains the user I/O functions for the master process.
41 \*===========================================================================*/
42
43 /*===========================================================================*\
44 * This first function reads in the data instance.
45 \*===========================================================================*/
46
47 void cnrp_io(cnrp_problem *cnrp, char *infile)
48 {
49 static char keywords[KEY_NUM][22] = {
50 "NAME",
51 "NAME:", /*This section lists the names of the */
52 "TYPE", /*possible fields in the data file */
53 "TYPE:",
54 "COMMENT",
55 "COMMENT:",
56 "DIMENSION",
57 "DIMENSION:",
58 "CAPACITY",
59 "CAPACITY:",
60 "EDGE_WEIGHT_TYPE",
61 "EDGE_WEIGHT_TYPE:",
62 "EDGE_WEIGHT_FORMAT",
63 "EDGE_WEIGHT_FORMAT:",
64 "DISPLAY_DATA_TYPE",
65 "DISPLAY_DATA_TYPE:",
66 "EDGE_WEIGHT_SECTION",
67 "EDGE_WEIGHT_SECTION:",
68 "DISPLAY_DATA_SECTION",
69 "DISPLAY_DATA_SECTION:",
70 "NODE_COORD_SECTION",
71 "NODE_COORD_SECTION:",
72 "NODE_COORD_TYPE",
73 "NODE_COORD_TYPE:",
74 "DEPOT_SECTION",
75 "DEPOT_SECTION:",
76 "CAPACITY_VOL",
77 "CAPACITY_VOL:",
78 "DEMAND_SECTION",
79 "DEMAND_SECTION:",
80 "TIME_WINDOW_SECTION",
81 "TIME_WINDOW_SECTION:",
82 "STANDTIME_SECTION",
83 "STANDTIME_SECTION:",
84 "PICKUP_SECTION",
85 "PICKUP_SECTION:",
86 "EOF",
87 "EOF.",
88 "",
89 "",
90 "NO_MORE_TYPE"
91 };
92
93 #define NCTYPE_NUM 3
94
95 static char nctypes[NCTYPE_NUM][14] = {
96 "TWOD_COORDS",
97 "THREED_COORDS", /*This section lists the possible node*/
98 "NO_COORDS" /*coordinate data types */
99 };
100
101 #define WTYPE_NUM 8
102
103 static char wtypes[WTYPE_NUM][9] = {
104 "EXPLICIT",
105 "EUC_2D", /*This is a list of the possible data types for */
106 "EUC_3D", /*edge weights */
107 "MAX_2D",
108 "MAX_3D",
109 "MAN_2D",
110 "MAN_3D",
111 "GEO"
112 };
113
114 #define WFORMAT_NUM 9
115
116 static char wformats[WFORMAT_NUM][20] = {
117 "UPPER_ROW",
118 "LOWER_ROW", /*This is a list of the possible formats that*/
119 "UPPER_DIAG_ROW", /*the edge weight matrix could be given in */
120 "LOWER_DIAG_ROW", /*if it is given explicitly */
121 "UPPER_COL",
122 "LOWER_COL",
123 "UPPER_DIAG_COL",
124 "LOWER_DIAG_COL",
125 "FULL_MATRIX"
126 };
127
128 #define DTYPE_NUM 3
129
130 static char dtypes[DTYPE_NUM][14] = {
131 "COORD_DISPLAY",
132 "TWOD_DISPLAY", /*This is a list of the various display data*/
133 "NO_DISPLAY" /*types */
134 };
135
136 char line[LENGTH], line1[LENGTH], key[30], tmp[80];
137 int wformat=-1, dtype=-1, nctype=-1;
138 double fdummy, demand_scale_factor = 1;
139 int i, j = 0;
140 int l, m, *coef2;
141 FILE *f;
142 int node;
143 double deg, min, coord_x, coord_y, coord_z;
144 double x, y;
145 int capacity_vol = FALSE;
146 int k;
147 register int vertnum = 0;
148 distances *dist = &cnrp->dist;
149 int adj_vertnum = 0;
150
151 if (!strcmp(infile, "")){
152 printf("\nCNRP I/O: No problem data file specified\n\n");
153 exit(1);
154 }
155
156 if ((f = fopen(infile, "r")) == NULL){
157 fprintf(stderr, "CNRP I/O: file '%s' can't be opened\n", infile);
158 exit(1);
159 }
160
161 /*This loop reads in the next line of the data file and compares it
162 to the list of possible keywords to determine what data will follow.
163 It then reads the data into the appropriate field and iterates */
164
165 while(NULL != fgets( line1, LENGTH, f)){
166 strcpy(key,"");
167 sscanf(line1,"%s",key); /*read in next keyword*/
168
169 for (k = 0; k < KEY_NUM; k++) /*which data field comes next?*/
170 if (strcmp(keywords[k], key) == 0) break;
171
172 if (k == KEY_NUM){
173 continue;
174 fprintf(stderr, "Unknown keyword! bye.\n");
175 exit(1); /*error check for acceptable data field*/
176 }
177
178 k >>= 1; /* This is a bit shift operation that divides k by 2 */
179 /* since in the list of keywords, there are two possible*/
180 /* formats for the keyword */
181
182 if (strchr(line1,':')){
183 strcpy(line, strchr(line1, ':')+1);
184 }
185
186 switch (k){
187
188 case 0: /* NAME */
189 if (!sscanf(line, "%s", cnrp->name))
190 fprintf(stderr, "\nCNRP I/O: error reading NAME\n\n");
191 printf("PROBLEM NAME: \t\t%s\n", cnrp->name);
192 break;
193
194 case 1 : /*TYPE*/
195 sscanf(line, "%s", tmp);
196 if (!cnrp->par.prob_type){
197 if (strcmp("CVRP", tmp) == 0){
198 cnrp->par.prob_type = cnrp->cg_par.prob_type =
199 cnrp->lp_par.prob_type = cnrp->cp_par.prob_type = VRP;
200 }else if (strcmp("TSP", tmp) == 0){
201 cnrp->par.prob_type = cnrp->cg_par.prob_type =
202 cnrp->lp_par.prob_type = cnrp->cp_par.prob_type = TSP;
203 }else if (strcmp("BPP", tmp) == 0){
204 cnrp->par.prob_type = cnrp->cg_par.prob_type =
205 cnrp->lp_par.prob_type = cnrp->cp_par.prob_type = BPP;
206 }else if (strcmp("CSTP", tmp) == 0){
207 cnrp->par.prob_type = cnrp->cg_par.prob_type =
208 cnrp->lp_par.prob_type = cnrp->cp_par.prob_type = CSTP;
209 }else if (strcmp("CTP", tmp) == 0){
210 cnrp->par.prob_type = cnrp->cg_par.prob_type =
211 cnrp->lp_par.prob_type = cnrp->cp_par.prob_type = CTP;
212 }else{
213 fprintf(stderr, "This is not a recognized problem type!\n");
214 exit(1);
215 }
216 }
217 switch(cnrp->par.prob_type){
218 case VRP:
219 printf("TYPE: \t\t\tCVRP\n");
220 break;
221
222 case TSP:
223 printf("TYPE: \t\t\tTSP\n");
224 break;
225
226 case BPP:
227 printf("TYPE: \t\t\tBPP\n");
228 break;
229
230 case CSTP:
231 printf("TYPE: \t\t\tCSTP\n");
232 break;
233
234 case CTP:
235 printf("TYPE: \t\t\tCTP\n");
236 break;
237 }
238 break;
239
240 case 2 : /*COMMENT*/
241 #if 0
242 if (!strncpy(tmp, line, 80))
243 fprintf(stderr, "\nCNRP I/O: error reading COMMENT\n\n");
244 printf("DESCRIPTION: \t\t%s\n", tmp);
245 #endif
246 break;
247 case 3 : /* DIMENSION */
248 if (!sscanf(line, "%i", &k)){
249 fprintf(stderr, "CNRP I/O: error reading DIMENSION\n\n");
250 exit(1);
251 }
252 vertnum = cnrp->vertnum = (int) k;
253 cnrp->edgenum = (int) vertnum * (vertnum - 1)/2;
254 printf("DIMENSION: \t\t%i\n", k);
255 break;
256 case 4 : /*CAPACITY*/
257 if (!sscanf(line, "%i", &k)){
258 fprintf(stderr, "CNRP I/O: error reading CAPACITY\n\n");
259 exit(1);
260 }
261 cnrp->capacity = ((double) k)*demand_scale_factor;
262 if (NUMNODES > 0 &&
263 (cnrp->par.prob_type == CSTP || cnrp->par.prob_type == VRP)){
264 cnrp->capacity=ceil(cnrp->capacity*(NUMNODES/(double)vertnum));
265 }
266 break;
267 case 5 : /* EDGE_WEIGHT_TYPE */
268 sscanf(line, "%s", tmp);
269 for (dist->wtype = 0; dist->wtype < WTYPE_NUM; (dist->wtype)++)
270 if (strcmp(wtypes[dist->wtype], tmp) == 0) break;
271 if (dist->wtype == WTYPE_NUM) {
272 fprintf(stderr, "Unknown weight type : %s !!!\n", tmp);
273 exit(1);
274 }
275 break;
276 case 6 : /* EDGE_WEIGHT_FORMAT */
277 sscanf(line, "%s", tmp);
278 for (wformat = 0; wformat < WFORMAT_NUM; wformat++)
279 if (strcmp(wformats[wformat], tmp) == 0) break;
280 if (wformat == WFORMAT_NUM) {
281 fprintf(stderr, "Unknown weight type : %s !!!\n", tmp);
282 exit(1);
283 }
284 break;
285 case 7 : /* DISPLAY_DATA_TYPE */
286 sscanf(line, "%s", tmp);
287 for (dtype = 0; dtype < DTYPE_NUM; dtype++)
288 if (strcmp(dtypes[dtype], tmp) == 0) break;
289 if (dtype == DTYPE_NUM) {
290 fprintf(stderr, "Unknown display type : %s !!!\n", tmp);
291 exit(1);
292 }
293 break;
294 case 8: /* EDGE_WEIGHT_SECTION */
295 /*------------------------break if not EXPLICIT -*/
296 if (dist->wtype != _EXPLICIT) break;
297 dist->cost = (int *) malloc (cnrp->edgenum*sizeof(int));
298 switch (wformat){
299 case 1 : /* LOWER_ROW */
300 case 4 : /* UPPER_COL */
301 case 3 : /* LOWER_DIAG_ROW */
302 case 6 : /* UPPER_DIAG_COL */
303 for (i=0, coef2=dist->cost; i<vertnum; i++){
304 for (j=0; j<i; j++, coef2++){
305 if (!fscanf(f,"%lf", &fdummy)){
306 fprintf(stderr, "Not enough data -- DIMENSION or "
307 "EDGE_WEIGHT_TYPE declared wrong\n");
308 exit(1);
309 }
310 else *coef2 = (int) fdummy;
311 }
312 if ((wformat==3 || wformat==6) &&
313 !fscanf(f,"%lf", &fdummy)){
314 fprintf(stderr, "Not enough data -- DIMENSION or "
315 "EDGE_WEIGHT_TYPE declared wrong\n");
316 exit(1);
317 }
318 }
319 if (fscanf(f,"%lf", &fdummy)){
320 fprintf(stderr, "Too much data -- DIMENSION or "
321 "EDGE_WEIGHT_TYPE declared wrong\n");
322 exit(1);
323 }
324 break;
325 case 0 : /* UPPER_ROW */
326 case 5 : /* LOWER_COL */
327 case 2 : /* UPPER_DIAG_ROW */
328 case 7 : /* LOWER_DIAG_COL */
329 for (i=0, coef2=dist->cost; i<vertnum; i++){
330 if (wformat==2 || wformat==7)
331 if (!fscanf(f,"%lf", &fdummy)){
332 fprintf(stderr, "Not enough data -- DIMENSION or "
333 "EDGE_WEIGHT_TYPE declared wrong");
334 exit(1);
335 }
336 for (j=i+1; j<vertnum; j++){
337 if (!fscanf(f,"%lf", &fdummy)){
338 fprintf(stderr, "Not enough data -- DIMENSION or "
339 "EDGE_WEIGHT_TYPE declared wrong");
340 exit(1);
341 }
342 else coef2[j*(j-1)/2+i] = (int) fdummy;
343 }
344 }
345 if (fscanf(f,"%lf", &fdummy)){
346 fprintf(stderr, "Too much data -- DIMENSION or "
347 "EDGE_WEIGHT_TYPE declared wrong\n");
348 exit(1);
349 }
350 break;
351 case 8 : /* FULL_MATRIX */
352 for (i=0, coef2=dist->cost; i<vertnum; i++){
353 for (j=0; j<=i; j++)
354 if(!fscanf(f,"%lf", &fdummy)){
355 fprintf(stderr, "Not enough data -- DIMENSION or "
356 "EDGE_WEIGHT_TYPE declared wrong");
357 exit(1);
358 }
359 for (j=i+1; j<vertnum; j++){
360 if(!fscanf(f,"%lf", &fdummy)){
361 fprintf(stderr, "Not enough data -- DIMENSION or "
362 "EDGE_WEIGHT_TYPE declared wrong");
363 exit(1);
364 }
365 coef2[j*(j-1)/2+i] = (int) fdummy;
366 }
367 }
368 if (fscanf(f,"%lf", &fdummy)){
369 fprintf(stderr, "Too much data -- DIMENSION or "
370 "EDGE_WEIGHT_TYPE declared wrong\n");
371 exit(1);
372 }
373 break;
374 }
375 break;
376 case 9 : /* DISPLAY_DATA_SECTION */
377 /*--------------------- break if NO_DISPLAY -*/
378 if (dtype != 1){
379 fprintf(stderr, "DISPLAY_DATA_SECTION exists"
380 "but not TWOD_DISPLAY!\n");
381 exit(1);
382 }
383 /* posx, posy -*/
384 cnrp->posx = (int *) malloc (vertnum*sizeof(int));
385 cnrp->posy = (int *) malloc (vertnum*sizeof(int));
386 for (i=0; i<vertnum; i++){
387 if ((k = fscanf(f,"%i%lf%lf", &node, &x, &y)) != 3){
388 fprintf(stderr, "\nCNRP I/O: error reading DISPLAY_DATA\n");
389 break;
390 }
391 cnrp->posx[node-1] = (int)(x + 0.5);
392 cnrp->posy[node-1] = (int)(y + 0.5);
393 }
394 if (fscanf(f,"%lf", &fdummy)){
395 fprintf(stderr, "\nCNRP I/O: too much display data\n");
396 break;
397 }
398 break;
399 case 10 : /* NODE_COORD_SECTION */
400 if (nctype == -1) nctype = 0; /*if not given: TWOD_COORDS*/
401 if (dtype == -1 && ((dist->wtype == _EUC_2D) || /*display type*/
402 (dist->wtype == _MAX_2D) || /*not defd yet*/
403 (dist->wtype == _MAN_2D) ))/*&& can disp.*/
404 dtype = 0; /* COORD_DISPLAY */
405 if (dtype == 0){
406 cnrp->posx = (int *) malloc (vertnum*sizeof(int));
407 cnrp->posy = (int *) malloc (vertnum*sizeof(int));
408 }
409 dist->coordx = (double *) malloc (vertnum*sizeof(double));
410 dist->coordy = (double *) malloc (vertnum*sizeof(double));
411 if (nctype == 1)
412 dist->coordz = (double *) malloc (vertnum*sizeof(double));
413 #if 0
414 for (i = 0; i < vertnum; i++){
415 if (nctype == 0) /* TWOD_COORDS */
416 if (fscanf(f,"%i%lf%lf", &node, &coord_x, &coord_y) != 3){
417 fprintf(stderr, "\nCNRP I/O: error reading NODE_COORD\n\n");
418 exit(1);
419 }
420 if (nctype == 1) /* THREED_COORDS */
421 if (fscanf(f,"%i%lf%lf%lf", &node, &coord_x, &coord_y,
422 &coord_z) != 4){
423 fprintf(stderr, "\nCNRP I/O: error reading NODE_COORD\n\n");
424 exit(1);
425 }
426 dist->coordx[node-1] = coord_x;
427 dist->coordy[node-1] = coord_y;
428 /*since position is an integer and coord is a double, I must
429 round off here if dtype is EXPLICIT*/
430 if (dtype == 0){
431 cnrp->posx[node-1] = (int)coord_x;
432 cnrp->posy[node-1] = (int)coord_y;
433 }
434 if (nctype == 1) dist->coordz[node-1] = coord_z;
435 if (dist->wtype == 7){ /* GEO */
436 /*--- latitude & longitude for i ------------*/
437 deg = floor(dist->coordx[i]);
438 min = dist->coordx[i] - deg;
439 dist->coordx[i] = MY_PI * (deg + 5.0*min/3.0 ) / 180.0;
440 deg = floor(dist->coordy[i]);
441 min = dist->coordy[i] - deg;
442 dist->coordy[i] = MY_PI * (deg + 5.0*min/3.0 ) / 180.0;
443 /*--- latitude & longitude for j ------------*/
444 deg = floor(dist->coordx[j]);
445 min = dist->coordx[j] - deg;
446 dist->coordx[j] = MY_PI * (deg + 5.0*min/3.0 ) / 180.0;
447 deg = floor(dist->coordy[j]);
448 min = dist->coordy[j] - deg;
449 dist->coordy[j] = MY_PI * (deg + 5.0*min/3.0 ) / 180.0;
450 }
451 }
452 #else
453 for (i = adj_vertnum = 0; i < vertnum; i++){
454 if (nctype == 0){ /* TWOD_COORDS */
455 if (fscanf(f,"%i%lf%lf", &node, &coord_x, &coord_y) != 3){
456 fprintf(stderr, "\nCNRP I/O: error reading NODE_COORD\n\n");
457 exit(1);
458 }
459 }
460 if (nctype == 1){ /* THREED_COORDS */
461 if (fscanf(f,"%i%lf%lf%lf", &node, &coord_x, &coord_y,
462 &coord_z) != 4){
463 fprintf(stderr, "\nCNRP I/O: error reading NODE_COORD\n\n");
464 exit(1);
465 }
466 }
467 if (NUMNODES > 0 && i % vertnum/NUMNODES != 0){
468 continue;
469 }
470 dist->coordx[adj_vertnum] = coord_x;
471 dist->coordy[adj_vertnum] = coord_y;
472 /*since position is an integer and coord is a double, I must
473 round off here if dtype is EXPLICIT*/
474 if (dtype == 0){
475 cnrp->posx[adj_vertnum] = (int)coord_x;
476 cnrp->posy[adj_vertnum] = (int)coord_y;
477 }
478 if (nctype == 1) dist->coordz[adj_vertnum-1] = coord_z;
479 if (dist->wtype == 7){ /* GEO */
480 /*--- latitude & longitude for i ------------*/
481 deg = floor(dist->coordx[adj_vertnum]);
482 min = dist->coordx[adj_vertnum] - deg;
483 dist->coordx[adj_vertnum] = MY_PI * (deg + 5.0*min/3.0 ) / 180.0;
484 deg = floor(dist->coordy[adj_vertnum]);
485 min = dist->coordy[adj_vertnum] - deg;
486 dist->coordy[adj_vertnum] = MY_PI * (deg + 5.0*min/3.0 ) / 180.0;
487 /*--- latitude & longitude for j ------------*/
488 deg = floor(dist->coordx[j]);
489 min = dist->coordx[j] - deg;
490 dist->coordx[j] = MY_PI * (deg + 5.0*min/3.0 ) / 180.0;
491 deg = floor(dist->coordy[j]);
492 min = dist->coordy[j] - deg;
493 dist->coordy[j] = MY_PI * (deg + 5.0*min/3.0 ) / 180.0;
494 }
495 adj_vertnum++;
496 }
497 cnrp->vertnum = adj_vertnum;
498 #endif
499 if (fscanf(f,"%i%lf%lf%lf", &node, &coord_x, &coord_y, &coord_z)){
500 fprintf(stderr, "\nCNRP I/O: too much data in NODE_COORD\n\n");
501 exit(1);
502 }
503 break;
504 case 11: /* NODE_COORD_TYPE */
505 sscanf(line, "%s", tmp);
506 for (nctype = 0; nctype < NCTYPE_NUM; nctype++)
507 if (strcmp(nctypes[nctype], tmp) == 0) break;
508 if (nctype == NCTYPE_NUM) {
509 fprintf(stderr, "Unknown node_coord_type : %s !!!\n", tmp);
510 exit(1);
511 }
512 break;
513 case 12: /*DEPOT_SECTION*/
514 fscanf(f, "%i", &k);
515 if (k != 1){
516 fprintf(stderr, "Error in data: depot must be node 1");
517 exit(1);
518 }
519 cnrp->depot = k - 1;
520 while (-1 != k) fscanf(f, "%i", &k);
521 break;
522 case 13: /*CAPACITY_VOL*/
523 sscanf(line, "%i", &k);
524 capacity_vol = TRUE;
525 break;
526 case 14: /*DEMAND_SECTION*/
527 cnrp->demand = (double *) malloc(vertnum*sizeof(double));
528 for (i = 0; i < vertnum; i++){
529 if (capacity_vol){
530 if (fscanf(f, "%i%i%i", &k, &l, &m) != 3){
531 fprintf(stderr,"\nCNRP I/O: error reading DEMAND_SECTION\n");
532 exit(1);
533 }
534 }
535 else if (fscanf(f, "%i%i", &k, &l) != 2){
536 fprintf(stderr, "\nCNRP I/O: error reading DEMAND_SECTION\n\n");
537 exit(1);
538 }
539 cnrp->demand[k-1] = MIN((double) l, 0.5*cnrp->capacity);
540 cnrp->demand[0] += cnrp->demand[k-1];
541 }
542 if (fscanf(f, "%i%i", &k, &l)){
543 fprintf(stderr, "\nCNRP I/O: too much data in DEMAND_SECTION\n\n");
544 exit(1);
545 }
546 demand_scale_factor = (double)(vertnum)/cnrp->demand[0];
547 for (i = 0; i < vertnum; i++){
548 cnrp->demand[i] *= demand_scale_factor;
549 }
550 if (cnrp->capacity > 0) cnrp->capacity *= demand_scale_factor;
551 break;
552 case 15: /*TIME_WINDOW_SECTION*/ /*These sections are not used*/
553 while (fscanf(f, "%d %*d:%*d %*d:%*d", &k));
554 break;
555 case 16: /*STANDTIME_SECTION*/
556 while (fscanf(f, "%d%*d", &k));
557 break;
558 case 17: /*PICKUP_SECTION*/
559 while (fscanf(f, "%d%*d%*d", &k));
560 break;
561 case 18: /* EOF */
562 default: break;
563 }
564 }
565
566 if (f != stdin)
567 fclose(f);
568
569 if (cnrp->par.prob_type != VRP && cnrp->par.prob_type != BPP &&
570 cnrp->par.prob_type != TSP && cnrp->par.prob_type != CSTP &&
571 cnrp->par.prob_type != CTP){
572 printf("Unknown problem type! Exiting...\n");
573 exit(1);
574 }
575
576 cnrp->cur_tour = (best_tours *) calloc(1, sizeof(best_tours));
577 cnrp->cur_tour->tour = (_node *) calloc(vertnum, sizeof(_node));
578 cnrp->cur_sol_tree = (int *) calloc(vertnum, ISIZE);
579
580 /*calculate all the distances explcitly and then use distance type EXPLICIT*/
581
582 if (cnrp->par.prob_type == BPP){
583 dist->cost = (int *) calloc (cnrp->edgenum, sizeof(int));
584 for (i = 1, k = 0; i < cnrp->vertnum; i++){
585 for (j = 0; j < i; j++){
586 dist->cost[k++] = (int)cnrp->demand[i] + (int)cnrp->demand[j];
587 }
588 }
589 }else if (dist->wtype != _EXPLICIT){
590 dist->cost = (int *) calloc (cnrp->edgenum, sizeof(int));
591 for (i = 1, k = 0; i < cnrp->vertnum; i++){
592 for (j = 0; j < i; j++){
593 dist->cost[k++] = ICOST(dist, i, j);
594 }
595 }
596 }
597 dist->wtype = _EXPLICIT;
598
599 if (cnrp->par.k_closest < 0){
600 cnrp->par.k_closest = (int) ceil(0.1 * cnrp->vertnum);
601 if (cnrp->par.k_closest < cnrp->par.min_closest )
602 cnrp->par.k_closest = cnrp->par.min_closest;
603 if (cnrp->par.k_closest > cnrp->par.max_closest)
604 cnrp->par.k_closest = cnrp->par.max_closest;
605 if (cnrp->par.k_closest > cnrp->vertnum-1)
606 cnrp->par.k_closest = cnrp->vertnum-1;
607 }
608 if (cnrp->par.prob_type == TSP || cnrp->par.prob_type == CTP){
609 cnrp->numroutes = 1;
610 if (!cnrp->demand)
611 cnrp->demand = (double *) malloc (vertnum * DSIZE);
612 for (i = vertnum - 1; i > 0; i--)
613 cnrp->demand[i] = 1.0;
614 if (!cnrp->cg_par.which_tsp_cuts)
615 cnrp->cg_par.which_tsp_cuts = ALL_TSP_CUTS;
616 }
617
618 if (cnrp->par.prob_type == TSP)
619 cnrp->capacity = cnrp->demand[0] = (double)(vertnum);
620 else if (cnrp->par.prob_type == CTP)
621 cnrp->capacity = cnrp->demand[0] = (double)(vertnum) -1;
622 }
623
624 /*===========================================================================*/
625
626 /*===========================================================================*\
627 * This second function reads in the parameters from the parameter file.
628 \*===========================================================================*/
629
630 void cnrp_readparams(cnrp_problem *cnrp, char *filename, int argc, char **argv)
631 {
632 int i, j;
633 char line[LENGTH], key[50], value[50], c, tmp;
634 FILE *f = NULL;
635 str_int colgen_str[COLGEN_STR_SIZE] = COLGEN_STR_ARRAY;
636
637 cnrp_params *par = &cnrp->par;
638 cnrp_lp_params *lp_par = &cnrp->lp_par;
639 cnrp_cg_params *cg_par = &cnrp->cg_par;
640
641 cnrp->numroutes = 0;
642 #if defined(CHECK_CUT_VALIDITY) || defined(TRACE_PATH)
643 cnrp->feas_sol_size = 0;
644 cnrp->feas_sol = NULL;
645 #endif
646 par->prob_type = NONE;
647 par->k_closest = -1;
648 par->min_closest = 4;
649 par->max_closest = 10;
650 par->add_all_edges = TRUE;
651 /*For now, I think this is necessary to make it work*/
652 par->base_variable_selection = SOME_ARE_BASE;
653 par->use_small_graph = FALSE;
654 par->colgen_strat[0] = 0;
655 par->colgen_strat[1] = 0;
656 par->verbosity = 0;
657 #ifdef MULTI_CRITERIA
658 par->binary_search_tolerance = .01;
659 par->compare_solution_tolerance = .001;
660 #endif
661
662 lp_par->verbosity = 0;
663 lp_par->branching_rule = 2;
664 lp_par->branch_on_cuts = FALSE;
665 lp_par->strong_branching_cand_num_max = 7;
666 lp_par->strong_branching_cand_num_min = 7;
667 lp_par->strong_branching_red_ratio = 0;
668 lp_par->detect_tailoff = 0;
669 lp_par->child_compar_obj_tol = .01;
670 lp_par->gamma = 1; /*Determines the fixed cost*/
671 lp_par->tau = 0; /*Determines the variable cost*/
672 lp_par->rho = 0.00001;
673 cg_par->verbosity = 0;
674 cg_par->do_greedy = TRUE;
675 cg_par->greedy_num_trials = 5;
676 cg_par->do_extra_in_root = FALSE;
677 cg_par->which_tsp_cuts = NO_TSP_CUTS;
678 cg_par->which_connected_routine = BOTH;
679 cg_par->max_num_cuts_in_shrink = 200;
680 #if defined(DIRECTED_X_VARS) && !defined(ADD_X_CUTS)
681 cg_par->generate_x_cuts = TRUE;
682 #else
683 cg_par->generate_x_cuts = FALSE;
684 #endif
685 #if defined(ADD_FLOW_VARS) && !defined(ADD_CAP_CUTS)
686 cg_par->generate_cap_cuts = TRUE;
687 cg_par->generate_tight_cap_cuts = TRUE;
688 #else
689 cg_par->generate_cap_cuts = FALSE;
690 cg_par->generate_tight_cap_cuts = FALSE;
691 #endif
692 /*For minimum cut*/
693 cg_par->do_mincut = TRUE;
694 cg_par->update_contr_above = 0;
695 cg_par->shrink_one_edges = FALSE;
696 cg_par->do_extra_checking = FALSE;
697 cg_par->tau = 0;
698
699 if (!strcmp(filename, ""))
700 goto EXIT;
701
702 if ((f = fopen(filename, "r")) == NULL){
703 printf("CNRP Readparams: file %s can't be opened\n", filename);
704 exit(1); /*error check for existence of parameter file*/
705 }
706
707 while(NULL != fgets( line, LENGTH, f)){ /*read in parameter settings*/
708 strcpy(key, "");
709 sscanf(line, "%s%s", key, value);
710
711 if (strcmp(key, "input_file") == 0){
712 par->infile[MAX_FILE_NAME_LENGTH] = 0;
713 strncpy(par->infile, value, MAX_FILE_NAME_LENGTH);
714 }
715 else if (strcmp(key, "prob_type") == 0){
716 if (strcmp("VRP", value) == 0){
717 par->prob_type = cg_par->prob_type =
718 cnrp->lp_par.prob_type = VRP;
719 }else if (strcmp("TSP", value) == 0){
720 par->prob_type = cg_par->prob_type =
721 cnrp->lp_par.prob_type = TSP;
722 }else if (strcmp("BPP", value) == 0){
723 par->prob_type = cg_par->prob_type =
724 cnrp->lp_par.prob_type = BPP;
725 }else if (strcmp("CSTP", value) == 0){
726 par->prob_type = cg_par->prob_type =
727 cnrp->lp_par.prob_type = CSTP;
728 }else if (strcmp("CTP", value) == 0){
729 par->prob_type = cg_par->prob_type =
730 cnrp->lp_par.prob_type = CTP;
731 }else{
732 fprintf(stderr, "Unknown problem type!\n");
733 exit(1);
734 }
735 }
736 else if (strcmp(key, "k_closest") == 0){
737 READ_INT_PAR(par->k_closest);
738 }
739 else if (strcmp(key, "k_closest_minimum") == 0){
740 READ_INT_PAR(par->min_closest);
741 }
742 else if (strcmp(key, "k_closest_maximum") == 0){
743 READ_INT_PAR(par->max_closest);
744 }
745 else if (strcmp(key, "add_all_edges") == 0){
746 READ_INT_PAR(par->add_all_edges);
747 }
748 else if (strcmp(key, "base_variable_selection") == 0){
749 READ_INT_PAR(par->base_variable_selection);
750 }
751 else if (strcmp(key, "use_small_graph") == 0){
752 READ_INT_PAR(par->use_small_graph);
753 if (par->use_small_graph){
754 if (fgets( line, LENGTH, f) == NULL){
755 printf("No small graph file!/n/n");
756 exit(1);
757 }
758 strcpy(key, "");
759 sscanf(line, "%s%s", key, value);
760 if (strcmp(key, "small_graph_file_name") != 0){
761 printf("Need small_graph_file_name next!!!/n/n");
762 exit(1);
763 }
764 strcpy(par->small_graph_file, value);
765 }
766 }
767 else if (strcmp(key, "colgen_in_first_phase") == 0 ||
768 strcmp(key, "TM_colgen_in_first_phase") == 0){
769 READ_INT_PAR(par->colgen_strat[0]);
770 }
771 else if (strcmp(key, "colgen_in_second_phase") == 0 ||
772 strcmp(key, "TM_colgen_in_second_phase") == 0){
773 READ_INT_PAR(par->colgen_strat[1]);
774 }
775 else if (strcmp(key, "colgen_in_first_phase_str") == 0 ||
776 strcmp(key, "TM_colgen_in_first_phase_str") == 0){
777 READ_STRINT_PAR(par->colgen_strat[0],
778 colgen_str, COLGEN_STR_SIZE, value);
779 }
780 else if (strcmp(key, "colgen_in_second_phase_str") == 0 ||
781 strcmp(key, "TM_colgen_in_second_phase_str") == 0){
782 READ_STRINT_PAR(par->colgen_strat[1],
783 colgen_str, COLGEN_STR_SIZE, value);
784 }
785 else if (strcmp(key, "numroutes") == 0){
786 READ_INT_PAR(j);
787 cnrp->numroutes = j;
788 }
789 #ifdef MULTI_CRITERIA
790 else if (strcmp(key, "binary_search_tolerance") == 0){
791 READ_DBL_PAR(par->binary_search_tolerance);
792 }
793 else if (strcmp(key, "compare_solution_tolerance") == 0){
794 READ_DBL_PAR(par->compare_solution_tolerance);
795 }
796 #endif
797
798 /************************ lp parameters *******************************/
799 else if (strcmp(key, "branching_rule") == 0){
800 READ_INT_PAR(lp_par->branching_rule);
801 }
802 else if (strcmp(key, "branch_on_cuts") == 0){
803 READ_INT_PAR(lp_par->branch_on_cuts);
804 }
805 else if (strcmp(key, "strong_branching_cand_num") == 0){
806 READ_INT_PAR(lp_par->strong_branching_cand_num_max);
807 lp_par->strong_branching_cand_num_min =
808 lp_par->strong_branching_cand_num_max;
809 lp_par->strong_branching_red_ratio = 0;
810 }
811 else if (strcmp(key, "strong_branching_cand_num_min") == 0){
812 READ_INT_PAR(lp_par->strong_branching_cand_num_min);
813 }
814 else if (strcmp(key, "strong_branching_cand_num_max") == 0){
815 READ_INT_PAR(lp_par->strong_branching_cand_num_max);
816 }
817 else if (strcmp(key, "strong_branching_red_ratio") == 0){
818 READ_INT_PAR(lp_par->strong_branching_red_ratio);
819 }
820 else if (strcmp(key, "child_compar_obj_tol") == 0){
821 READ_FLOAT_PAR(lp_par->child_compar_obj_tol);
822 }
823 else if (strcmp(key, "detect_tailoff") == 0){
824 READ_INT_PAR(lp_par->detect_tailoff);
825 }
826 else if (strcmp(key, "gamma") == 0){
827 READ_DBL_PAR(lp_par->gamma);
828 cg_par->tau = lp_par->tau = 1 - lp_par->gamma;
829 }
830 else if (strcmp(key, "rho") == 0){
831 READ_DBL_PAR(lp_par->rho);
832 }
833
834 /************************* cutgen parameters ***************************/
835
836 else if (strcmp(key, "verbosity") == 0){
837 READ_INT_PAR(par->verbosity);
838 lp_par->verbosity = cg_par->verbosity = par->verbosity;
839 }
840 else if (strcmp(key, "do_greedy") == 0){
841 READ_INT_PAR(cg_par->do_greedy);
842 }
843 else if (strcmp(key, "greedy_num_trials") == 0){
844 READ_INT_PAR(cg_par->greedy_num_trials);
845 }
846 else if (strcmp(key, "do_extra_in_root") == 0){
847 READ_INT_PAR(cg_par->do_extra_in_root);
848 }
849 else if (strcmp(key, "which_tsp_cuts") == 0){
850 READ_INT_PAR(cg_par->which_tsp_cuts);
851 }
852 #if defined(CHECK_CUT_VALIDITY) || defined(TRACE_PATH)
853 else if (strcmp(key, "feasible_solution_edges") == 0){
854 READ_INT_PAR(cnrp->feas_sol_size);
855 if (cnrp->feas_sol_size){
856 int cur_node, prev_node = 0;
857 char value1[10], value2[10];
858
859 cnrp->feas_sol = (int *)calloc(cnrp->feas_sol_size, sizeof(int));
860 for (i = 0; i < cnrp->feas_sol_size; i++){
861 if (!fgets( line, LENGTH, f)){
862 fprintf(stderr,
863 "\nCNRP I/O: error reading in feasible solution\n");
864 exit(1);
865 }
866 strcpy(key, "");
867 sscanf(line, "%s%s%s", key, value1, value2);
868 if (strcmp(key, "edge")){
869 fprintf(stderr,
870 "\nCNRP I/O: error reading in feasible solution\n");
871 exit(1);
872 }
873 if (sscanf(value1, "%i", &prev_node) != 1){
874 fprintf(stderr,
875 "\nCNRP I/O: error reading in feasible solution %s\n",
876 key);
877 exit(1);
878 }
879 if (sscanf(value2, "%i", &cur_node) != 1){
880 fprintf(stderr,
881 "\nCNRP I/O: error reading in feasible solution %s\n",
882 key);
883 exit(1);
884 }
885 cnrp->feas_sol[i] = INDEX(prev_node, cur_node);
886 }
887 }
888 }
889 else if (strcmp(key, "feasible_solution_nodes") == 0){
890 READ_INT_PAR(cnrp->feas_sol_size);
891 if (cnrp->feas_sol_size){
892 int cur_node, prev_node = 0;
893
894 cnrp->feas_sol = (int *)calloc(cnrp->feas_sol_size, sizeof(int));
895 for (i=0; i<cnrp->feas_sol_size; i++){
896 if (!fgets( line, LENGTH, f)){
897 fprintf(stderr,
898 "\nCNRP I/O: error reading in feasible solution\n");
899 exit(1);
900 }
901 sscanf(line, "%s", value);
902 if (sscanf(value, "%i", &cur_node) != 1){
903 fprintf(stderr,
904 "\nCNRP I/O: error reading in feasible solution %s\n",
905 key);
906 exit(1);
907 }else{
908 cnrp->feas_sol[i] = INDEX(prev_node, cur_node);
909 prev_node = cur_node;
910 }
911 }
912 }
913 }
914 #endif
915 else if (strcmp(key, "which_connected_routine") == 0){
916 READ_INT_PAR(cg_par->which_connected_routine);
917 }
918 else if (strcmp(key, "max_num_cuts_in_shrink") == 0){
919 READ_INT_PAR(cg_par->max_num_cuts_in_shrink);
920 }
921 else if (strcmp(key, "generate_x_cuts") == 0){
922 READ_INT_PAR(cg_par->generate_x_cuts);
923 }
924 else if (strcmp(key, "generate_cap_cuts") == 0){
925 READ_INT_PAR(cg_par->generate_cap_cuts);
926 }
927 else if (strcmp(key, "generate_tight_cap_cuts") == 0){
928 READ_INT_PAR(cg_par->generate_tight_cap_cuts);
929 }
930 /*For minimum cut*/
931 else if (strcmp(key, "do_mincut") == 0){
932 READ_INT_PAR(cg_par->do_mincut);
933 }
934 else if (strcmp(key, "update_contr_above") == 0){
935 READ_INT_PAR(cg_par->update_contr_above);
936 }
937 else if (strcmp(key, "shrink_one_edges") == 0){
938 READ_INT_PAR(cg_par->shrink_one_edges);
939 }
940 else if (strcmp(key, "do_extra_checking") == 0){
941 READ_INT_PAR(cg_par->do_extra_checking);
942 }
943 }
944
945 EXIT:
946
947 for (i = 1; i < argc; i++){
948 sscanf(argv[i], "%c %c", &tmp, &c);
949 if (tmp != '-')
950 continue;
951 switch (c) {
952 case 'D':
953 sscanf(argv[++i], "%i", &lp_par->verbosity);
954 break;
955 case 'H':
956 user_usage();
957 exit(0);
958 case 'E':
959 par->add_all_edges = FALSE;
960 break;
961 case 'S':
962 strncpy(par->small_graph_file, argv[++i], MAX_FILE_NAME_LENGTH);
963 par->use_small_graph = LOAD_SMALL_GRAPH;
964 break;
965 case 'F':
966 strncpy(par->infile, argv[++i], MAX_FILE_NAME_LENGTH);
967 break;
968 case 'B':
969 sscanf(argv[++i], "%i", &lp_par->branching_rule);
970 break;
971 case 'V':
972 sscanf(argv[++i], "%i", &par->base_variable_selection);
973 break;
974 case 'K':
975 sscanf(argv[++i], "%i", &par->k_closest);
976 break;
977 case 'N':
978 sscanf(argv[++i], "%i", &cnrp->numroutes);
979 break;
980 case 'M':
981 cg_par->do_mincut = FALSE;
982 break;
983 case 'X':
984 sscanf(argv[++i], "%i", &cg_par->generate_x_cuts);
985 break;
986 case 'Y':
987 sscanf(argv[++i], "%i", &cg_par->generate_cap_cuts);
988 break;
989 case 'Z':
990 sscanf(argv[++i], "%i", &cg_par->generate_tight_cap_cuts);
991 break;
992 case 'G':
993 sscanf(argv[++i], "%lf", &lp_par->gamma);
994 lp_par->tau = cg_par->tau = 1 - lp_par->gamma;
995 break;
996 #ifdef MULTI_CRITERIA
997 case 'I':
998 sscanf(argv[++i], "%lf", &par->binary_search_tolerance);
999 break;
1000 #endif
1001 case 'P':
1002 i++;
1003 if (strcmp("VRP", argv[i]) == 0){
1004 par->prob_type = cg_par->prob_type =
1005 cnrp->lp_par.prob_type = VRP;
1006 }else if (strcmp("TSP", argv[i]) == 0){
1007 par->prob_type = cg_par->prob_type =
1008 cnrp->lp_par.prob_type = TSP;
1009 }else if (strcmp("BPP", argv[i]) == 0){
1010 par->prob_type = cg_par->prob_type =
1011 cnrp->lp_par.prob_type = BPP;
1012 }else if (strcmp("CSTP", argv[i]) == 0){
1013 par->prob_type = cg_par->prob_type =
1014 cnrp->lp_par.prob_type = CSTP;
1015 }else if (strcmp("CTP", argv[i]) == 0){
1016 par->prob_type = cg_par->prob_type =
1017 cnrp->lp_par.prob_type = CTP;
1018 }else{
1019 fprintf(stderr, "Unknown problem type!\n");
1020 exit(1);
1021 }
1022 break;
1023
1024 case 'C':
1025 sscanf(argv[++i], "%f", &cnrp->capacity);
1026 break;
1027 case 'T':
1028 par->test = TRUE;
1029 if(i+1 < argc){
1030 sscanf(argv[i+1], "%c", &tmp);
1031 if(tmp != '-'){
1032 strncpy(par->test_dir, argv[++i],MAX_FILE_NAME_LENGTH);
1033 }
1034 }
1035 break;
1036 };
1037 }
1038
1039 if (f)
1040 fclose(f);
1041 }