Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/Heuristics/receive_rout.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 /* This application was developed by Ted Ralphs ([email protected]) */
8 /* This file was modified by Ali Pilatin January, 2005 ([email protected]) */
9 /* */
10 /* (c) Copyright 2000-2005 Ted Ralphs. All Rights Reserved. */
11 /* */
12 /* This software is licensed under the Common Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 #include <memory.h>
18 #include <time.h>
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <unistd.h>
22 #include "BB_constants.h"
23 #include "sym_messages.h"
24 #include "receive_rout.h"
25 #include "compute_cost.h"
26 #include "vrp_master_functions.h"
27 #include "network.h"
28 #include "sym_proccomm.h"
29 #include "vrp_const.h"
30 #include "vrp_macros.h"
31
32 /*--------------------------------------------------------------------*\
33 | The receive_tours function is used to receive the tours |
34 | output by various heuristic processes running in parallel and keep |
35 | an ordered list of them in a binary tree. It checks about once every |
36 | second to see if any tours have come into the recieve buffer and if |
37 | so, it updates the binary tree and stores the tour if it is one of |
38 | the lowest (vrp->par.tours_to_keep) cost tours |
39 \*--------------------------------------------------------------------*/
40
41 double receive_tours(vrp_problem *vrp, heurs *hh, int *last,
42 char print, char routes, char add_edges,
43 char win, int jobs, int *sent)
44 {
45 int pos;
46 int i, low_run, dead_tasks = 0;
47 int s_bufid = 0, r_bufid = 0, bytes, msgtag, tid;
48 _node *tour;
49 int *tourorder = vrp->tourorder, tournum = -1;
50 best_tours *tours = vrp->tours;/*-------------------------------------*\
51 | new best tours are put in this tours* |
52 \*-------------------------------------*/
53 int cost;
54 int numroutes, v0, v1, vertnum = vrp->vertnum;
55 route_data *route_info = NULL;
56 time_t cur_time, prev_time;
57 int algorithm;
58 double solve_time = 0, total_solve_time = 0;
59 edge_data *next_edge = NULL;
60 small_graph *g = NULL;
61 int newedgenum=0, round =0, round1 = 0;
62 int receive = 1, *returned, some_returned = 0;
63 int mytid = pvm_mytid();
64 if (add_edges){
65 g = vrp->g;
66 next_edge = g->edges+g->edgenum;
67 }
68
69 if (hh->jobs == 0) return((double) 0);
70
71 returned= (int *) calloc(jobs+1, sizeof(int));
72 tour = (_node *) calloc (vertnum, sizeof(_node));
73
74 time(&prev_time);
75
76 while(receive){
77 receive = 0;
78 r_bufid = nreceive_msg(-1, -1);
79 if (r_bufid){ /*check buffer for tour*/
80 bufinfo(r_bufid, &bytes, &msgtag, &tid);//get the tid of buffer
81 for (i=0; hh->tids[i] != tid; i++);//find the corresponding tids[i]
82 returned[i] += 1;
83 receive_char_array((char *)tour, (vertnum)*sizeof(_node));//receive a tour
84 receive_int_array(&cost, 1);
85 receive_int_array(&numroutes, 1); /*receive
86 tour */
87 receive_int_array(&algorithm, 1);
88 receive_dbl_array(&solve_time, 1);
89 if (routes){
90 route_info = (route_data *) calloc(numroutes + 1,
91 sizeof(route_data));
92 receive_char_array((char *)route_info, (numroutes+1) *
93 sizeof(route_data));
94
95 }
96 if (!cost){ /*zero cost is an error flag - don't store this tour*/
97 if (vrp->par.verbosity >2)
98 fprintf(stderr, "Error receiving job %i - infeasible\n", i+1);
99 if (win && vrp->par.verbosity>4){
100 if(!vrp->dg_id){
101 /*vrp->window = init_win(vrp->par.executables.winprog,
102 vrp->par.debug.winprog,
103 vrp->posx, vrp->posy, vrp->vertnum);*/
104 }
105 /*vrp->window->windata.draw = TRUE;
106 disp_tour(vrp->window, tour, TRUE);*/
107 }
108 hh->jobs--;
109 if (!hh->jobs) return((double) 0);
110 else continue;
111 }
112 if (tournum + 1 < vrp->par.tours_to_keep){
113 *last = ++tournum;
114 tours[*last].cost = MAXINT;
115 }
116 else{
117 *last = tourorder[tournum];
118 }
119 if (tours[*last].cost >cost){ /*check to see if tour is one of *\
120 |the (vrp->par.tours_to_keep) |
121 |cheapest and if so, update |
122 \*binary tree */
123 tours[*last].cost = cost;
124 tours[*last].numroutes = numroutes;
125 tours[*last].algorithm = algorithm;
126 tours[*last].solve_time += solve_time;
127 total_solve_time += solve_time;
128 if(routes)
129 tours[*last].route_info = route_info;
130 memcpy((char *)tours[*last].tour, (char *)tour,
131 vertnum*sizeof(_node));
132 for (pos = tournum -1;
133 pos >=0 &&tours[tourorder[pos]].cost >cost; pos--){
134 tourorder[pos+1]=tourorder[pos];
135 }
136 tourorder[pos+1]=*last;
137 }
138
139 if (print && vrp->par.verbosity >2){
140 printf("A job from task %i returned: cost = %i trucks = %i", hh->tids[i],
141 cost, numroutes);
142 printf(" algorithm = %i solution time = %.3f\n", algorithm,
143 solve_time);
144
145
146 if (vrp->par.verbosity>4 && win){
147 if(!vrp->dg_id){
148 /*vrp->window = init_win(vrp->par.executables.winprog,
149 vrp->par.debug.winprog,
150 vrp->posx, vrp->posy, vrp->vertnum);*/
151 }
152 /*vrp->window->windata.draw = TRUE;
153 disp_tour(vrp->window, tour, TRUE);*/
154 /*display the tour in the tour window*/
155 }
156 }
157 if (add_edges){
158 v0 = 0;
159 v1 = tour[0].next;
160 for (pos = 0; pos<vertnum; pos++){
161 v1 = tour[v0=v1].next;
162 if(tour[v0].route == tour[v1].route){
163 if (v0 < v1){
164 next_edge->v0 = v0;
165 next_edge->v1 = v1;
166 }
167 else{
168 next_edge->v0 = v1;
169 next_edge->v1 = v0;
170 }
171 if (!bsearch((char *)next_edge, (char *)g->edges,
172 g->edgenum, sizeof(edge_data), is_same_edge)){
173 (next_edge++)->cost = ICOST(&vrp->dist, v0, v1);
174 newedgenum++;
175 }
176 }
177 }
178 }
179 time(&prev_time); /*reset the time_out timer*/
180 }
181 else{
182 #if 0
183 sleep(.01); /*the purpose of this sleep command is to keep the *\
184 | program from checking the buffer continuously, which |
185 | chews up CPU time. Before continuing, there is a |
186 | check to see if too much time has elapsed since the |
187 | last tour was received and if so all remaining |
188 \*processes are killed and the function terminates */
189 #endif
190 time (&cur_time);
191 if (cur_time > prev_time + vrp->par.time_out.ub){
192 if (vrp->par.verbosity>1)
193 printf("\nReceive tours timed out after %i seconds ...\n",
194 vrp->par.time_out.ub);
195 break;
196 }
197 }
198 for(i=0; i < jobs; i++){
199 if((returned[i] != sent[i]) && (pstat(hh->tids[i]) == PROCESS_OK)){
200 receive = 1;
201 break;//break out of loop
202 }
203 }
204 }
205 if (add_edges && newedgenum){
206 g->edgenum += newedgenum;
207 delete_dup_edges(g);
208 }
209 vrp->tournum = tournum;
210 for (i=0; i<jobs; some_returned+=returned[i],i++);
211 if ((print) && (some_returned)){
212 if (vrp->par.verbosity >2){
213 printf("\nTotal solution time for heuristics in this "
214 "batch is %.3f\n\n", total_solve_time);
215 printf("the best tour values: \n");
216 for (pos=0; pos<=tournum; pos++)
217 printf("%i algorithm = %i\n", tours[tourorder[pos]].cost,
218 tours[tourorder[pos]].algorithm);
219 if (add_edges)
220 printf("\nNumber of edges in the problem is %i\n\n", g->edgenum);
221 }
222 else if (vrp->par.verbosity >1){
223 printf("Best tour found has cost %i with %i trucks using "
224 "algorithm %i\n",
225 tours[tourorder[0]].cost, tours[tourorder[0]].numroutes,
226 tours[tourorder[0]].algorithm);
227 printf("Total solution time for this solution is %.3f\n",
228 tours[tourorder[0]].solve_time);
229 printf("Total solution time for heuristics in this batch is %.3f\n\n",
230 total_solve_time);
231 if (add_edges)
232 printf("Number of edges in the problem is %i\n\n", g->edgenum);
233 }
234 }
235 if (tour) free ((char *) tour);
236 if (hh->starter) free((char *)hh->starter);
237 hh->starter = NULL;
238 if (returned) free((char *)returned);
239 for(i=0; i<jobs; sent[i]=0, i++);
240 return(total_solve_time);
241 }
242
243 /*===========================================================================*/
244
245 double receive_lbs(vrp_problem *vrp, heurs *hh, char win,
246 int numroutes, int jobs, int *sent)
247 {
248 int i, low_run, dead_tasks = 0, nr = numroutes;
249 int r_bufid = 0, bytes, msgtag, tid, s_bufid;
250 int *tree, *temp_tree;
251 edge_data *best_edges, *temp_best_edges;
252 int cost, round =0;
253 time_t cur_time, prev_time;
254 double solve_time = 0, total_solve_time = 0;
255 int receive, *returned, some_returned = 0;
256 if (hh->jobs == 0) return((double) 0);
257 returned= (int *) calloc(jobs+1, sizeof(int));
258 tree = vrp->lb->tree = (int *) calloc(vrp->vertnum, sizeof(int));
259 best_edges = vrp->lb->best_edges = (edge_data *) calloc(numroutes,
260 sizeof(edge));
261 temp_tree = (int *) calloc (vrp->vertnum, sizeof(int));
262 temp_best_edges = vrp->lb->best_edges = (edge_data *) calloc(numroutes,
263 sizeof(edge));
264 vrp->lb->lower_bound = (double) -MAXINT;
265
266 time(&prev_time);
267 while(receive){
268 receive = 0;
269 r_bufid = nreceive_msg(-1, LOWER_BOUND);
270 if (r_bufid){ /*check buffer for tour*/
271 bufinfo(r_bufid, &bytes, &msgtag, &tid);
272 for (i=0; hh->tids[i] != tid; i++);
273 returned[i] += 1;
274 receive_int_array(temp_tree, vrp->vertnum);
275 receive_char_array((char *)temp_best_edges,
276 numroutes * sizeof(edge_data));
277 receive_int_array(&cost, 1);
278 receive_dbl_array(&solve_time, 1);
279 total_solve_time += solve_time;
280 if ((double) cost > vrp->lb->lower_bound){
281 vrp->lb->lower_bound = (double) cost;
282 memcpy (tree, temp_tree, vrp->vertnum*sizeof(int));
283 memcpy (best_edges, temp_best_edges, numroutes*sizeof(edge));
284 }
285
286 if (!win && vrp->par.verbosity>2){
287 switch(i){
288 case 0:
289 printf("A job from 1st task returned: cost = %i trucks = %u "
290 "solution time = %.3f\n", cost, nr, solve_time);
291 break;
292 case 1:
293 printf("A job from 2nd task returned: cost = %i trucks = %u "
294 "solution time = %.3f\n", cost, nr, solve_time);
295 break;
296 case 2:
297 printf(
298 "A job from 3rd task returned: cost = %i trucks = %u "
299 "solution time = %.3f\n", cost, nr, solve_time);
300 break;
301 default:
302 printf("A job from %ith task returned: cost = %i trucks = %u "
303 "solution time = %.3f\n", i+1, cost, nr, solve_time);
304 }
305
306 if (vrp->par.verbosity >4){
307 if(!vrp->dg_id && win){
308 /*vrp->window = init_win(vrp->par.executables.winprog,
309 vrp->par.debug.winprog,
310 vrp->posx, vrp->posy, vrp->vertnum);*/
311 }
312 /*vrp->window->windata.draw = TRUE;
313 disp_lb(vrp->window, temp_tree, temp_best_edges,
314 numroutes, TRUE);*/
315 /*display the lb in the tour window*/
316 }
317 }
318 time(&prev_time); /*reset the time_out timer*/
319 }
320 else{
321 #if 0
322 sleep(.01);/* the purpose of this sleep command is to keep the *\
323 | program from checking the buffer continuously, which |
324 | chews up CPU time. Before continuing, there is a |
325 | check to see if too much time has elapsed since the |
326 | last tour was received and if so all remaining |
327 \*processes are killed and the function terminates */
328 #endif
329
330 time (&cur_time);
331 if (cur_time > prev_time + vrp->par.time_out.ub){
332 if (vrp->par.verbosity>1)
333 printf("\nReceive tours timed out after %i seconds ...\n",
334 vrp->par.time_out.ub);
335 break;
336 }
337 }
338 for(i=0; i<jobs; i++){
339 if(returned[i] != sent[i] && pstat(hh->tids[i]) == PROCESS_OK){
340 receive = 1;
341 break;//break out of loop
342 }
343 }
344 }
345 for (i=0; i<jobs; i++, some_returned+=returned[i]);
346 if ((some_returned) && (vrp->par.verbosity >0))
347 printf("The best lower bound: %.1f with %u trucks\n",
348 vrp->lb->lower_bound, nr);
349
350 if (temp_tree) free ((char *) temp_tree);
351 if (hh->starter) free((char *) hh->starter);
352 hh->starter = NULL;
353 if (returned) free((char *)returned);
354 freebuf(r_bufid);
355 for(i=0; i<jobs; sent[i]=0, i++);
356 return (total_solve_time);
357 }