Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/vrp_master.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 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */
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 <stdio.h>
18 #include <stdlib.h>
19 #include <math.h>
20
21 /* SYMPHONY include files */
22 /*__BEGIN_EXPERIMENTAL_SECTION__*/
23 #include "sym_master.h"
24 /*___END_EXPERIMENTAL_SECTION___*/
25 #include "sym_macros.h"
26 #include "sym_constants.h"
27 #include "sym_proccomm.h"
28 #include "sym_qsort.h"
29 #include "sym_dg_params.h"
30 #include "sym_master_u.h"
31
32 /* VRP include files */
33 #include "vrp_const.h"
34 #include "vrp_types.h"
35 #include "vrp_io.h"
36 #include "compute_cost.h"
37 #include "network.h"
38 #ifdef COMPILE_HEURS
39 #include "start_heurs.h"
40 #endif
41 #include "vrp_master_functions.h"
42 #include "vrp_dg_functions.h"
43 #include "vrp_macros.h"
44 #include "small_graph.h"
45 #ifdef COMPILE_IN_TM
46 #ifdef COMPILE_IN_CP
47 #include "vrp_cp.h"
48 #endif
49 #ifdef COMPILE_IN_LP
50 #include "vrp_lp.h"
51 #ifdef COMPILE_IN_CG
52 #include "vrp_cg.h"
53 /*__BEGIN_EXPERIMENTAL_SECTION__*/
54 #ifdef COMPILE_OUR_DECOMP
55 #include "my_decomp.h"
56 #endif
57 /*___END_EXPERIMENTAL_SECTION___*/
58 #endif
59 #endif
60 #endif
61
62 /*===========================================================================*/
63
64 /*===========================================================================*\
65 * This file contains the user-written functions for the master process.
66 \*===========================================================================*/
67
68 void user_usage(void){
69 printf("vrp [ -HEPT ] [ -S file ] [ -F file ] [ -B rule ]\n\t"
70 "[ -V sel ] [ -K closest ] [ -N routes ] [ -C capacity ]\n"
71 "\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n"
72 "\t%s\n\t%s\n\t%s\n"
73 /*__BEGIN_EXPERIMENTAL_SECTION__*/
74 "\t%s\n"
75 /*___END_EXPERIMENTAL_SECTION___*/
76 "\n",
77 "-H: help",
78 "-E: use sparse edge set",
79 "-T: solve as a Traveling Salesman Problem",
80 "-S file: load sparse graph from 'file'",
81 "-F file: problem data is in 'file'",
82 "-B i: which candidates to check in strong branching",
83 "-A i: how to construct the base set of variables",
84 "-V i: verbosity level",
85 "-K k: use 'k' closest edges to build sparse graph",
86 "-N n: use 'n' routes",
87 /*__BEGIN_EXPERIMENTAL_SECTION__*/
88 "-P: solve as a Bin Packing Problem",
89 /*___END_EXPERIMENTAL_SECTION___*/
90 "-C c: use capacity 'c'");
91 }
92
93 /*===========================================================================*\
94 * Initialize user-defined data structures. In this case, I store all
95 * problem-specific data such as the location of the customers, edge costs,
96 * etc. in this data-structure.
97 \*===========================================================================*/
98
99 int user_initialize(void **user)
100 {
101 vrp_problem *vrp = (vrp_problem *) calloc(1, sizeof(vrp_problem));
102
103 *user = vrp;
104
105 vrp_set_defaults(vrp);
106
107 return(USER_SUCCESS);
108 }
109
110 /*===========================================================================*/
111
112 /*===========================================================================*\
113 * In this function, I set up the user parameters. The first step is to cast
114 * the void pointer in order to access my data. In the readparams() function,
115 * I read in parameters from the parameter file given on the command line.
116 \*===========================================================================*/
117
118 int user_readparams(void *user, char *filename, int argc, char **argv)
119 {
120 vrp_problem *vrp = (vrp_problem *)user;
121
122 vrp_readparams(vrp, filename, argc, argv);
123
124 #if 0
125 if (vrp->par.use_small_graph == LOAD_SMALL_GRAPH){
126 read_small_graph(vrp);
127 vrp->numroutes = vrp->cur_tour->numroutes;
128 }
129
130 /* Selects the cheapest edges adjacent to each node for the base set */
131
132 if (vrp->par.use_small_graph == SAVE_SMALL_GRAPH){
133 if (!vrp->g) make_small_graph(vrp, 0);
134 save_small_graph(vrp);
135 }else if (!vrp->g){
136 make_small_graph(vrp, 0);
137 }
138 #endif
139 return(USER_SUCCESS);
140 }
141
142 /*===========================================================================*/
143
144 /*===========================================================================*\
145 * After I've read in the parameters, I can now read in the data file, whose
146 * name was given in the parameter file. This file contains instance data.
147 \*===========================================================================*/
148
149 int user_io(void *user)
150 {
151 vrp_problem *vrp = (vrp_problem *)user;
152 int i;
153
154 if (strcmp(vrp->par.infile, "")){
155 vrp_io(vrp, vrp->par.infile);
156 }
157
158 if (vrp->numroutes == 1){
159 vrp->par.tsp_prob = TRUE;
160 vrp->capacity = vrp->vertnum;
161 vrp->numroutes = 1;
162 vrp->demand = (int *) malloc (vrp->vertnum * ISIZE);
163 vrp->demand[0] = vrp->vertnum;
164 for (i = vrp->vertnum - 1; i > 0; i--)
165 vrp->demand[i] = 1;
166 vrp->cg_par.tsp_prob = TRUE;
167 if (!vrp->cg_par.which_tsp_cuts)
168 vrp->cg_par.which_tsp_cuts = ALL_TSP_CUTS;
169 }
170
171 vrp->cur_tour = (best_tours *) calloc(1, sizeof(best_tours));
172 vrp->cur_tour->tour = (_node *) calloc(vrp->vertnum, sizeof(_node));
173 #ifdef COMPILE_HEURS
174 vrp->tours = (best_tours *) calloc(vrp->par.tours_to_keep,
175 sizeof(best_tours));
176 #endif
177
178 if (vrp->par.k_closest < 0){
179 vrp->par.k_closest = (int) (ceil(0.1 * vrp->vertnum));
180 if (vrp->par.k_closest < vrp->par.min_closest )
181 vrp->par.k_closest = vrp->par.min_closest;
182 if (vrp->par.k_closest > vrp->par.max_closest)
183 vrp->par.k_closest = vrp->par.max_closest;
184 if (vrp->par.k_closest > vrp->vertnum-1)
185 vrp->par.k_closest = vrp->vertnum-1;
186 }
187
188 if (vrp->par.use_small_graph == LOAD_SMALL_GRAPH){
189 read_small_graph(vrp);
190 vrp->numroutes = vrp->cur_tour->numroutes;
191 }
192
193 /* Selects the cheapest edges adjacent to each node for the base set */
194
195 if (vrp->par.use_small_graph == SAVE_SMALL_GRAPH){
196 if (!vrp->g) make_small_graph(vrp, 0);
197 save_small_graph(vrp);
198 }else if (!vrp->g){
199 make_small_graph(vrp, 0);
200 }
201
202 return(USER_SUCCESS);
203 }
204
205 /*===========================================================================*/
206
207 /*===========================================================================*\
208 * Here is where the heuristics are performed and an upper bound is calculated.
209 * An upper bound can also be specified in the parameter file. The
210 * other thing I do in this routine is build up a graph of the
211 * cheapest k edges adjacent to the each node plus any edges chosen
212 * during the heuristics to comprise my base set later.
213 \*===========================================================================*/
214
215 int user_start_heurs(void *user, double *ub, double *ub_estimate)
216 {
217 vrp_problem *vrp = (vrp_problem *)user;
218
219 if (*ub > 0){
220 vrp->cur_tour->cost = (int) (*ub);
221 }else if (vrp->cur_tour->cost > 0){
222 *ub = (int)(vrp->cur_tour->cost);
223 }else{
224 vrp->cur_tour->cost = MAXINT;
225 }
226
227 vrp->cur_tour->numroutes = vrp->numroutes;
228
229 /*__BEGIN_EXPERIMENTAL_SECTION__*/
230 if(vrp->par.bpp_prob)
231 *ub = 1;
232 /*___END_EXPERIMENTAL_SECTION___*/
233
234 #ifdef COMPILE_HEURS
235 if (vrp->par.do_heuristics || vrp->lb_par.lower_bound)
236 start_heurs(vrp, &vrp->heur_par, &vrp->lb_par, ub, FALSE);
237 else
238 vrp->tournum = -1;
239 #endif
240
241 if (!vrp->numroutes){
242 printf("\nError: Number of trucks not specified or computed "
243 "for VRP\n\n");
244 exit(1);
245 }
246
247 if (vrp->par.verbosity < 0){
248 return(USER_SUCCESS);
249 }
250
251 if (vrp->numroutes > 1){
252 printf("NUMBER OF TRUCKS: \t%i\n", vrp->numroutes);
253 printf("TIGHTNESS: \t\t%.2f\n",
254 (double)vrp->demand[0]/((double)vrp->capacity*(double)vrp->numroutes));
255 }
256
257
258 /*__BEGIN_EXPERIMENTAL_SECTION__*/
259 if (*ub > 0 && !vrp->par.bpp_prob)
260 printf("INITIAL UPPER BOUND: \t%i\n\n", (int)(*ub));
261 else if (!vrp->par.bpp_prob)
262 printf("INITIAL UPPER BOUND: \tNone\n\n");
263 else
264 printf("\n\n");
265 /*___END_EXPERIMENTAL_SECTION___*/
266 /*UNCOMMENT FOR PRODUCTION CODE*/
267 #if 0
268 if (*ub > 0)
269 printf("INITIAL UPPER BOUND: \t%i\n\n", (int)(*ub));
270 else
271 printf("INITIAL UPPER BOUND: \tNone\n\n");
272 #endif
273
274 return(USER_SUCCESS);
275 }
276
277 /*===========================================================================*/
278
279 /*===========================================================================*\
280 * If graph drawing will be use, the user must initialize the drawing
281 * window here.
282 \*===========================================================================*/
283
284 int user_init_draw_graph(void *user, int dg_id)
285 {
286 #ifndef WIN32 /* FIXME : None of this works in Windows */
287 vrp_problem *vrp = (vrp_problem *)user;
288 int s_bufid;
289
290 if (!(vrp->posx && vrp->posy)) return(USER_NO_PP);
291 if ( (vrp->dg_id = dg_id) ){
292 int i, zero = 0, eight = 0x08;
293 char node_place[MAX_NAME_LENGTH] = {"node_placement"};
294 char weight[5];
295 int *posx = vrp->posx, *posy = vrp->posy;
296 int minx=MAXINT, miny=MAXINT, maxx=-MAXINT, maxy=-MAXINT, xx, yy;
297 int width = 1000, height = 700;
298 #if 0
299 int width=p->par.dg_par.canvas_width, height=p->par.dg_par.canvas_height;
300 #endif
301 double mult;
302
303 for (i = vrp->vertnum - 1; i >= 0; i--){
304 if (posx[i] < minx) minx = posx[i];
305 if (posx[i] > maxx) maxx = posx[i];
306 if (posy[i] < miny) miny = posy[i];
307 if (posy[i] > maxy) maxy = posy[i];
308 }
309 xx = maxx - minx;
310 yy = maxy - miny;
311 mult = (int) MIN((width - 20.0)/xx, (height-20.0)/yy);
312 width = (int) (xx * mult + 30);
313 height = (int) (yy * mult + 30);
314 for (i = vrp->vertnum-1; i >= 0; i--){
315 posx[i] = (int) ((posx[i] - minx) * mult + 10);
316 posy[i] = (int) ((maxy - posy[i]) * mult + 10);
317 }
318
319 init_window(dg_id, node_place, width, height);
320 /* Now pack the placement of the nodes of the graph */
321 s_bufid = init_send(DataInPlace);
322 send_str(node_place);
323 send_int_array(&vrp->vertnum, 1);
324 for (i = 0; i < vrp->vertnum; i++){
325 send_int_array(&i, 1);
326 send_int_array(posx + i, 1);
327 send_int_array(posy + i, 1);
328 send_int_array(&eight, 1);
329 sprintf(weight, "%i", vrp->demand[i]);
330 send_str(weight);
331 }
332 /* No edges are passed to the default graph */
333 send_int_array(&zero, 1);
334 send_msg(dg_id, CTOI_SET_GRAPH);
335 freebuf(s_bufid);
336
337 display_graph(dg_id, node_place);
338 }
339 #endif
340
341 return(USER_SUCCESS);
342 }
343
344 /*===========================================================================*/
345
346 /*===========================================================================*\
347 * In this routine, I build the initial edge set for the root. There are
348 * several things going on here. First, there is a user-defined parameter
349 * defining whether or not to just go ahead and add all variables to the
350 * problem up front (vrp->par.add_all_edges). Currently, this seems to be the
351 * best option since the problems are small anyway. Further, I am doing some
352 * preprocessing here by eliminating edges for which the sum of the demands of
353 * their endpoints is greater than the capacity since these edges cannot
354 * be in any feasible solution.
355 *
356 * Notice that there are several options programmed for which set
357 * of edges should be in the base set. The
358 * base constraints are just the degree constraints from the IP
359 * formulation. These do not have to be specified explicitly, just the
360 * number of them given.
361 \*===========================================================================*/
362
363 int user_initialize_root_node(void *user, int *basevarnum, int **basevars,
364 int *basecutnum, int *extravarnum,
365 int **extravars, char *obj_sense,
366 double *obj_offset, char ***colnames,
367 int *colgen_strat)
368 {
369 vrp_problem *vrp = (vrp_problem *)user;
370 int base_varnum = 0;
371 int i, j, k, l;
372 int zero_varnum, *zero_vars;
373 int vertnum = vrp->vertnum;
374 int *edges;
375
376 /* Form the set of base variables */
377 switch(vrp->par.base_variable_selection){
378 case SOME_ARE_BASE:
379 if (vrp->par.add_all_edges == FALSE)
380 /*If we are not adding all the edges, then really EVERYTHING_IS_BASE*/
381 vrp->par.base_variable_selection = EVERYTHING_IS_BASE;
382 else /*Otherwise, all we need to do is set this and then fall through --
383 the remaining edges get added in user_create_root()*/
384 vrp->par.add_all_edges = FALSE;
385
386
387 case EVERYTHING_IS_BASE:
388 *basevars = create_edge_list(vrp, &base_varnum, CHEAP_EDGES);
389
390 *basevars = (int *) realloc((char *)(*basevars), base_varnum * ISIZE);
391 *basevarnum = base_varnum;
392
393 break;
394
395 case EVERYTHING_IS_EXTRA:
396 *basevarnum = 0;
397 break;
398 }
399
400 *basecutnum = vertnum;
401
402 if (!vrp->par.colgen_strat[0]){
403 #if 0
404 /* Currently, column generation is broken */
405 if (vrp->par.add_all_edges ||
406 vrp->par.base_variable_selection == SOME_ARE_BASE){
407 colgen_strat[0]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD |
408 BEFORE_BRANCH__DO_NOT_GENERATE_COLS);
409 }else{
410 colgen_strat[0] = (FATHOM__DO_NOT_GENERATE_COLS__SEND |
411 BEFORE_BRANCH__DO_NOT_GENERATE_COLS);
412 }
413 #endif
414 colgen_strat[0]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD |
415 BEFORE_BRANCH__DO_NOT_GENERATE_COLS);
416 }else{
417 colgen_strat[0] = vrp->par.colgen_strat[0];
418 }
419 if (!vrp->par.colgen_strat[1]){
420 if (vrp->par.add_all_edges ||
421 vrp->par.base_variable_selection == SOME_ARE_BASE){
422 colgen_strat[1]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD |
423 BEFORE_BRANCH__DO_NOT_GENERATE_COLS);
424 }else{
425 colgen_strat[1] = (FATHOM__GENERATE_COLS__RESOLVE |
426 BEFORE_BRANCH__DO_NOT_GENERATE_COLS);
427 }
428 }else{
429 colgen_strat[1] = vrp->par.colgen_strat[1];
430 }
431
432 /*create the edge list (we assume a complete graph) The edge is set to
433 (0,0) in the edge list if it was eliminated in preprocessing*/
434 edges = vrp->edges = (int *) calloc (vertnum*(vertnum-1), sizeof(int));
435 zero_varnum = vrp->zero_varnum;
436 zero_vars = vrp->zero_vars;
437 for (i = 1, k = 0, l = 0; i < vertnum; i++){
438 for (j = 0; j < i; j++){
439 if (l < zero_varnum && k == zero_vars[l]){
440 /*This is one of the zero edges*/
441 edges[2*k] = edges[2*k+1] = 0;
442 l++;
443 k++;
444 continue;
445 }
446 edges[2*k] = j;
447 edges[2*k+1] = i;
448 k++;
449 }
450 }
451
452 /*__BEGIN_EXPERIMENTAL_SECTION__*/
453 if (vrp->par.bpp_prob){
454 for (i = 0; i < *basevarnum; i++){
455 vrp->dist.cost[(*basevars)[i]] = 10;
456 }
457 }
458 /*___END_EXPERIMENTAL_SECTION___*/
459
460 /* Form the set of extra variables */
461 switch(vrp->par.base_variable_selection){
462 case EVERYTHING_IS_EXTRA:
463
464 *extravars = create_edge_list(vrp, extravarnum, CHEAP_EDGES);
465
466 break;
467
468 case SOME_ARE_BASE:
469
470 vrp->par.add_all_edges = TRUE; /*We turned this off in user_set_base()
471 -- now we need to turn it back on*/
472
473 *extravars = create_edge_list(vrp, extravarnum, REMAINING_EDGES);
474
475 break;
476
477 case EVERYTHING_IS_BASE:
478
479 break;
480 }
481
482 return(USER_SUCCESS);
483 }
484
485 /*===========================================================================*/
486
487 /*===========================================================================*\
488 * In my case, a feasible solution is specified most compactly by
489 * essentially a permutation of the customers along with routes numbers,
490 * specifying the order of the customers on their routes. This is just
491 * sent as a character array which then gets cast to an array of
492 * structures, one for each customers specifying the route number and
493 * the next customer on the route.
494 \*===========================================================================*/
495
496 int user_receive_feasible_solution(void *user, int msgtag, double cost,
497 int numvars, int *indices, double *values)
498 {
499 vrp_problem *vrp = (vrp_problem *)user;
500
501 receive_char_array((char *)vrp->cur_tour->tour, vrp->vertnum*sizeof(_node));
502
503 return(USER_SUCCESS);
504 }
505
506 /*===========================================================================*/
507
508 /*===========================================================================*\
509 * Here, we send the necessary data to the LP process. Notice that
510 * there are two cases to deal with. If the LP or the TM are running
511 * as separate processes, then we have to send the data by
512 * message-passing. Otherwise, we can allocate the user-defined LP data
513 * structure here and simply copy the necessary information. This is the
514 * only place the user has to sorry about this distinction between
515 * configurations.
516 \*===========================================================================*/
517
518 int user_send_lp_data(void *user, void **user_lp)
519 {
520 vrp_problem *vrp = (vrp_problem *)user;
521
522 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP)
523 /* This is the case when we are copying data directly because
524 the LP is not running separately. This code should be virtually
525 identical to that of user_receive_lp_data() in the LP process.*/
526
527 vrp_lp_problem *vrp_lp = (vrp_lp_problem *) calloc(1,
528 sizeof(vrp_lp_problem));
529 *user_lp = (void *)vrp_lp;
530
531 vrp_lp->par = vrp->lp_par;
532 vrp_lp->window = vrp->dg_id;
533 vrp_lp->numroutes = vrp->numroutes;
534 vrp_lp->vertnum = vrp->vertnum;
535 vrp_lp->edges = vrp->edges;
536 vrp_lp->demand = vrp->demand;
537 vrp_lp->capacity = vrp->capacity;
538 vrp_lp->costs = vrp->dist.cost;
539
540 vrp_lp->cur_sol = (_node *) calloc (vrp_lp->vertnum, sizeof(_node));
541 /*__BEGIN_EXPERIMENTAL_SECTION__*/
542
543 if (vrp_lp->window){
544 copy_node_set(vrp_lp->window, TRUE, (char *)"Original solution");
545 #if 0
546 copy_node_set(vrp_lp->window, TRUE, (char *)"Compressed solution");
547 #endif
548 }
549
550 /*___END_EXPERIMENTAL_SECTION___*/
551
552 #else
553 /* Here, we send that data using message passing and the rest is
554 done in user_receive_lp_data() in the LP process */
555
556 send_char_array((char *)(&vrp->lp_par), sizeof(vrp_lp_params));
557 send_int_array(&vrp->dg_id, 1);
558 send_int_array(&vrp->numroutes, 1);
559 send_int_array(&vrp->vertnum, 1);
560 send_int_array(vrp->demand, vrp->vertnum);
561 send_int_array(&vrp->capacity, 1);
562 send_int_array(vrp->dist.cost, vrp->edgenum);
563 send_int_array(&vrp->zero_varnum, 1);
564 if (vrp->zero_varnum){
565 send_int_array(vrp->zero_vars, vrp->zero_varnum);
566 }
567 #endif
568
569 return(USER_SUCCESS);
570 }
571
572 /*===========================================================================*/
573
574 /*===========================================================================*\
575 * Here, we send the necessary data to the CG process. Notice that
576 * there are two cases to deal with. If the CG, LP, or the TM are running
577 * as separate processes, then we have to send the data by
578 * message-passing. Otherwise, we can allocate the user-defined LP data
579 * structure here and simply copy the necessary information. This is the
580 * only place the user has to sorry about this distinction between
581 * configurations.
582 \*===========================================================================*/
583
584 int user_send_cg_data(void *user, void **user_cg)
585 {
586 vrp_problem *vrp = (vrp_problem *)user;
587
588 #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CG)
589 /* This is is the case when we are copying data directly because
590 the CG is not running separately. This code should be virtually
591 identical to that of user_receive_cg_data() in the CG process.*/
592
593 vrp_cg_problem *vrp_cg = (vrp_cg_problem *) malloc (sizeof(vrp_cg_problem));
594 int edgenum, vertnum, i, j, k;
595
596 *user_cg = (void *)vrp_cg;
597
598 vrp_cg->par = vrp->cg_par;
599 vrp_cg->numroutes = vrp->numroutes;
600 vertnum = vrp_cg->vertnum = vrp->vertnum;
601 vrp_cg->demand = (int *) malloc(vrp->vertnum*sizeof(int));
602 memcpy(vrp_cg->demand, vrp->demand, vrp->vertnum*sizeof(int));
603 vrp_cg->capacity = vrp->capacity;
604 vrp_cg->dg_id = vrp->dg_id;
605
606 edgenum = vrp->vertnum*(vrp->vertnum-1)/2;
607
608 /*__BEGIN_EXPERIMENTAL_SECTION__*/
609 #ifdef COMPILE_OUR_DECOMP
610 if (vrp->cg_par.do_our_decomp){
611 vrp_cg->cost = vrp->dist.cost;
612 usr_open_decomp_lp( get_cg_ptr(NULL), edgenum );
613 }
614 vrp_cg->last_decomp_index = -1;
615 #endif
616 /*___END_EXPERIMENTAL_SECTION___*/
617 vrp_cg->in_set = (char *) calloc(vrp->vertnum, sizeof(char));
618 vrp_cg->ref = (int *) malloc(vrp->vertnum*sizeof(int));
619 vrp_cg->new_demand = (int *) malloc(vrp->vertnum*sizeof(int));
620 vrp_cg->cut_val = (double *) calloc(vrp->vertnum, sizeof(double));
621 vrp_cg->cut_list = (char *) malloc(((vrp->vertnum >> DELETE_POWER)+1)*
622 (vrp->cg_par.max_num_cuts_in_shrink + 1)*
623 sizeof(char));
624
625 vrp_cg->edges = (int *) calloc (2*edgenum, sizeof(int));
626
627 /*create the edge list (we assume a complete graph)*/
628 for (i = 1, k = 0; i < vertnum; i++){
629 for (j = 0; j < i; j++){
630 vrp_cg->edges[2*k] = j;
631 vrp_cg->edges[2*k+1] = i;
632 k++;
633 }
634 }
635
636 #ifdef CHECK_CUT_VALIDITY
637 if ((vrp_cg->feas_sol_size = vrp->feas_sol_size)){
638 vrp_cg->feas_sol = vrp->feas_sol;
639 }
640 #endif
641 #else
642 /* Here, we send that data using message passing and the rest is
643 done in user_receive_cg_data() in the CG process */
644
645 send_char_array((char *)&vrp->cg_par, sizeof(vrp_cg_params));
646 send_int_array(&vrp->dg_id, 1);
647 send_int_array(&vrp->numroutes, 1);
648 send_int_array(&vrp->vertnum, 1);
649 send_int_array(vrp->demand, vrp->vertnum);
650 send_int_array(&vrp->capacity, 1);
651 /*__BEGIN_EXPERIMENTAL_SECTION__*/
652 if (vrp->cg_par.do_our_decomp)/* need to send costs to CG too */
653 send_int_array(vrp->dist.cost, vrp->edgenum);
654 /*___END_EXPERIMENTAL_SECTION___*/
655 #ifdef CHECK_CUT_VALIDITY
656 send_int_array(&vrp->feas_sol_size, 1);
657 if (vrp->feas_sol_size){
658 send_int_array(vrp->feas_sol, vrp->feas_sol_size);
659 }
660 #endif
661 #endif
662
663 return(USER_SUCCESS);
664 }
665
666 /*===========================================================================*/
667
668 /*===========================================================================*\
669 * Here, we send the necessary data to the CP process. Notice that
670 * there are two cases to deal with. If the CP, LP, or the TM are running
671 * as separate processes, then we have to send the data by
672 * message-passing. Otherwise, we can allocate the user-defined LP data
673 * structure here and simply copy the necessary information. This is the
674 * only place the user has to sorry about this distinction between
675 * configurations.
676 \*===========================================================================*/
677
678 int user_send_cp_data(void *user, void **user_cp)
679 {
680 vrp_problem *vrp = (vrp_problem *)user;
681
682 #if defined(COMPILE_IN_TM) && defined (COMPILE_IN_CP)
683 /* This is is the case when we are copying data directly because
684 the LP is not running separately. This code should be virtually
685 identical to that of user_receive_cp_data() in the CP process.*/
686
687 vrp_cp_problem *vrp_cp = (vrp_cp_problem *) malloc (sizeof(vrp_cp_problem));
688 int i, j, k;
689
690 vrp_cp->vertnum = vrp->vertnum;
691
692 *user_cp = (void *)vrp_cp;
693
694 vrp_cp->edgenum = vrp_cp->vertnum*(vrp_cp->vertnum-1)/2 + vrp_cp->vertnum-1;
695 vrp_cp->edges = (int *) calloc ((int)2*vrp_cp->edgenum, sizeof(int));
696
697 /* create the edge list (we assume a complete graph) */
698 for (i = 1, k = 0; i < vrp_cp->vertnum; i++){
699 for (j = 0; j < i; j++){
700 vrp_cp->edges[2*k] = j;
701 vrp_cp->edges[2*k+1] = i;
702 k++;
703 }
704 }
705
706 /* now add the duplicate copies of the depot edges to allow for
707 routes with one customer */
708 for (i = 1; i < vrp_cp->vertnum; i++){
709 vrp_cp->edges[2*k] = 0;
710 vrp_cp->edges[2*k+1] = i;
711 k++;
712 }
713 #else
714 /* Here, we send that data using message passing and the rest is
715 done in user_receive_cp_data() in the CP process */
716
717 send_int_array(&vrp->vertnum, 1);
718 #endif
719
720 return(USER_SUCCESS);
721 }
722
723 /*__BEGIN_EXPERIMENTAL_SECTION__*/
724 /*===========================================================================*/
725
726 int user_send_sp_data(void *user)
727 {
728 #ifdef COMPILE_HEURS
729 vrp_problem *vrp = (vrp_problem *) user;
730 int i, j;
731 int size;
732 _node *tour;
733 int *coef;
734 int tournum = vrp->tournum + 1 + vrp->sol_pool_col_num;
735 int cur_node, next_node;
736 int v0, v1;
737 int vertnum = vrp->vertnum;
738 /*FIXME: temporary fix to allow this to compile without PVM*/
739
740 coef = (int *) calloc (vrp->vertnum - 1 + vrp->numroutes, ISIZE);
741 size = (vrp->vertnum-1 + vrp->numroutes) * ISIZE;
742
743 send_int_array(&vrp->vertnum, 1);
744
745 send_int_array(&tournum, 1);
746
747 if (tournum <= 0){
748 return(USER_SUCCESS);
749 }
750
751 for (i = 0; i<=vrp->tournum; i++){
752 tour = vrp->tours[i].tour;
753 coef[0] = INDEX(0, tour[0].next);
754 for (cur_node = tour[0].next, next_node = tour[cur_node].next, j = 1;
755 cur_node;
756 cur_node = next_node, next_node = tour[next_node].next, j++){
757 if(tour[cur_node].route == tour[next_node].route){
758 coef[j] = INDEX(cur_node, next_node);
759 }else if (next_node){
760 coef[j++] = INDEX(0, cur_node);
761 if (coef[j-1] == coef[j-2])
762 coef[j-1] = vertnum*(vertnum-1)/2 + cur_node - 1;
763 coef[j] = INDEX(0, next_node);
764 }else{
765 coef[j] = INDEX(0, cur_node);
766 }
767 }
768
769 qsort_i(coef, size/sizeof(int));
770
771 send_int_array(&size, 1);
772 send_char_array((char *)coef, size);
773 }
774
775 for (i = 0; i<vrp->sol_pool_col_num; i++){
776 for (j = 0; j < 2*size/sizeof(int); j+=2){
777 v0 = vrp->sol_pool_cols[2*i*size/ISIZE + j];
778 v1 = vrp->sol_pool_cols[2*i*size/ISIZE + j + 1];
779 coef[j/2] = INDEX(v0, v1);
780 }
781 qsort_i(coef, size/ISIZE);
782
783 send_int_array(&size, 1);
784 send_char_array((char *)coef, size);
785 }
786 #endif
787
788 return(USER_SUCCESS);
789 }
790
791 /*___END_EXPERIMENTAL_SECTION___*/
792 /*===========================================================================*/
793
794 /*===========================================================================*\
795 * Generally, this function is not needed but you might find some use
796 * for it. Someone did :).
797 \*===========================================================================*/
798
799 int user_process_own_messages(void *user, int msgtag)
800 {
801 return(USER_DEFAULT);
802 }
803
804 /*===========================================================================*/
805
806 /*===========================================================================*\
807 * This is the user's chance to display the solution in whatever
808 * manner desired. In my case, I can display a text version, which is
809 * just a list of the customers on each route, or use the interactive
810 * Graph Drawing application to graphically display the solution.
811 \*===========================================================================*/
812
813 int user_display_solution(void *user, double lpetol, int varnum, int *indices,
814 double *values, double objval)
815 {
816 vrp_problem *vrp = (vrp_problem *)user;
817 _node *tour = vrp->cur_tour->tour;
818 int window = vrp->dg_id;
819
820 int prev_node = 0, node, count = 0;
821
822 if (!tour || vrp->cur_tour->cost > (int) objval){ /* Construct the tour */
823 int cur_vert = 0, prev_vert = 0, cur_route;
824 elist *cur_route_start = NULL;
825 edge *edge_data;
826 double cost = 0;
827 network *n = createnet(indices, values, varnum, lpetol, vrp->edges,
828 vrp->demand, vrp->vertnum);
829 vertex *verts = n->verts;
830
831 if (!tour)
832 tour = vrp->cur_tour->tour = (_node *) calloc (vrp->vertnum,
833 sizeof(_node));
834
835 for (cur_route_start = verts[0].first, cur_route = 1, cost = 0,
836 edge_data = cur_route_start->data; cur_route <= vrp->numroutes;
837 cur_route++){
838 edge_data = cur_route_start->data;
839 edge_data->scanned = TRUE;
840 cur_vert = edge_data->v1;
841 tour[prev_vert].next = cur_vert;
842 tour[cur_vert].route = cur_route;
843 prev_vert = 0;
844 cost += vrp->dist.cost[INDEX(prev_vert, cur_vert)];
845 while (cur_vert){
846 if (verts[cur_vert].first->other_end != prev_vert){
847 prev_vert = cur_vert;
848 edge_data = verts[cur_vert].first->data;
849 cur_vert = verts[cur_vert].first->other_end;
850 }
851 else{
852 prev_vert = cur_vert;
853 edge_data = verts[cur_vert].last->data; /*This statement could
854 possibly be taken out
855 to speed things up a
856 bit */
857 cur_vert = verts[cur_vert].last->other_end;
858 }
859 tour[prev_vert].next = cur_vert;
860 tour[cur_vert].route = cur_route;
861 cost += vrp->dist.cost[INDEX(prev_vert, cur_vert)];
862 }
863 edge_data->scanned = TRUE;
864
865 while (cur_route_start->data->scanned){
866 if (!(cur_route_start = cur_route_start->next_edge)) break;
867 }
868 }
869 free_net(n);
870 }
871
872 node = tour[0].next;
873
874 if (tour[0].route == 1)
875 printf("\n0 ");
876 while (node != 0){
877 if (tour[prev_node].route != tour[node].route){
878 printf("\nRoute #%i: ", tour[node].route);
879 count = 0;
880 }
881 printf("%i ", node);
882 count++;
883 if (count > 15){
884 printf("\n");
885 count = 0;
886 }
887 prev_node = node;
888 node = tour[node].next;
889 }
890 printf("\n\n");
891
892 if (window){
893 char name[MAX_NAME_LENGTH] = {"feas_solution"};
894 disp_vrp_tour(window, TRUE, name, tour, vrp->vertnum, vrp->numroutes,
895 CTOI_WAIT_FOR_CLICK_AND_REPORT);
896 }
897
898 #ifndef WIN32
899 if (window){
900 char name[MAX_NAME_LENGTH] = {"feas_solution"};
901 disp_vrp_tour(window, TRUE, name, tour, vrp->vertnum, vrp->numroutes,
902 CTOI_WAIT_FOR_CLICK_AND_REPORT);
903 }
904 #endif
905
906 return(USER_SUCCESS);
907 }
908
909 /*===========================================================================*/
910
911 /*===========================================================================*\
912 * This is a debugging feature which might
913 * allow you to find out why a known feasible solution is being cut off.
914 \*===========================================================================*/
915
916 int user_send_feas_sol(void *user, int *feas_sol_size, int **feas_sol)
917 {
918 #ifdef TRACE_PATH
919 vrp_problem *vrp = (vrp_problem *)user;
920
921 *feas_sol_size = vrp->feas_sol_size;
922 *feas_sol = vrp->feas_sol;
923 #endif
924 return(USER_SUCCESS);
925 }
926
927 /*===========================================================================*/
928
929 /*===========================================================================*\
930 * This function frees everything.
931 \*===========================================================================*/
932
933 int user_free_master(void **user)
934 {
935 vrp_problem *vrp = (vrp_problem *)(*user);
936
937 if (vrp->cur_tour){
938 FREE(vrp->cur_tour->tour);
939 FREE(vrp->cur_tour->route_info);
940 FREE(vrp->cur_tour);
941 }
942 FREE(vrp->posy);
943 FREE(vrp->posx);
944 FREE(vrp->dist.coordx);
945 FREE(vrp->dist.coordy);
946 FREE(vrp->dist.coordz);
947 #if !(defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP))
948 FREE(vrp->dist.cost);
949 FREE(vrp->edges);
950 FREE(vrp->demand);
951 #endif
952 #ifdef COMPILE_HEURS
953 if (vrp->tours){
954 FREE(vrp->tours[0].tour);
955 if (vrp->tourorder)
956 for (i=0; i<=vrp->tournum; i++)
957 FREE(vrp->tours[vrp->tourorder[i]].route_info);
958 FREE(vrp->tours);
959 }
960 FREE(vrp->tourorder);
961 if (vrp->lb){
962 FREE(vrp->lb->tree);
963 FREE(vrp->lb->best_edges);
964 FREE(vrp->lb);
965 }
966 FREE(vrp->par.rand_seed);
967 #endif
968 if (vrp->g){
969 FREE(vrp->g->edges);
970 FREE(vrp->g);
971 }
972 #ifdef CHECK_CUT_VALIDITY
973 FREE(vrp->feas_sol);
974 #endif
975 FREE(vrp->zero_vars);
976 FREE(vrp);
977
978 return(USER_SUCCESS);
979 }
980
981 /*===========================================================================*/
982
983 /*===========================================================================*\
984 * This function is used to lift the user created cuts during warm starting *
985 \*===========================================================================*/
986
987 int user_ws_update_cuts (void *user, int *size, char **coef, double * rhs,
988 char *sense, char type, int new_col_num,
989 int change_type)
990 {
991 return(USER_DEFAULT);
992 }
993
994 /*===========================================================================*/
995
996
997
998
999