Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/Heuristics/cluster_heur.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 <stdio.h>
19 #include <stdlib.h>
20 #include <string.h>
21
22 #include "cluster_heur.h"
23 #include "vrp_master_functions.h"
24 #include "vrp_const.h"
25 #include "sym_proccomm.h"
26 #include "BB_macros.h"
27
28
29 /*===========================================================================*/
30
31 void generate_starter(int vertnum, int *starter, int num)
32 {
33 int i, rans = 0, pos = 0;
34 int ran;
35
36 for (i = 0; i < num; i++){
37 do{
38 ran = (RANDOM() % vertnum) + 1;//draw a random vertex
39 for (pos = 0; pos < rans; pos++)
40 if (starter[pos] == ran) break;
41 }while (pos < rans);//continue drawing till a new vertex is drawn
42
43 starter[rans++] = ran;/*---------------------------------*\
44 | assign this vertex to the current |
45 | position, go back and draw a |
46 | vertex for the next position |
47 \*---------------------------------*/
48 }
49 }
50
51 /*===========================================================================*/
52
53 /*----------------------------------------------------------------------*\
54 | This function spawns the various cluster heuristics which are the first|
55 | step in the process of finding reasonable upper bounds |
56 \*----------------------------------------------------------------------*/
57
58 void cluster_heur(vrp_problem *vrp, heur_params *heur_par,
59 heurs *ch, int trials, int jobs, int *tids, int *sent)
60 {
61 vrp_params *par = &vrp->par;
62
63 int *sweep_tid, *savings_tid, *savings2_tid, *near_cluster_tid, *temp_tid;
64 int *tsp_ni_tid, *tsp_fi_tid, *tsp_fini_tid, *savings3_tid;
65 int sweep_job=0, savings_jobs=0;
66 int savings2_jobs = 0, savings3_jobs = 0, near_cluster_job=0;
67 int tsp_ni_jobs = 0, tsp_fi_jobs = 0, tsp_fini_jobs = 0;
68 int i, temp, dummy;
69 int s_bufid;
70 int vertnum = vrp->vertnum;
71 float lamda, mu;
72 float temp_mu, temp_lamda;
73 float lamda_int, mu_int;
74 int grid_size, count = 0, j, l;
75 int start;
76 int farside = (int) (vertnum * heur_par->fini_ratio);
77 int *starter;
78 int sw_index = 0, tni_index=0, tfi_index=0;
79 int tfini_index=0, s_index=0, s2_index=0, s3_index=0;
80
81
82 if (vrp->par.verbosity > 1)
83 printf("\nNow beginning cluster heuristics ....\n\n");
84
85 /*-----------------------------------------------------------------------*\
86 | Enlisting this process |
87 \*-----------------------------------------------------------------------*/
88
89 if (jobs == 0){
90 fprintf(stderr, "\nNo jobs started... \n\n");
91 return;
92 }
93 else if (vrp->par.verbosity > 2)
94 printf("\n%i jobs started ....\n\n", jobs);
95
96 ch->tids = tids;
97 ch->jobs = trials;
98
99
100 /*-----------------------------------------------------------------------*\
101 | Broadcast number of trials to sweep and tsp routines |
102 \*-----------------------------------------------------------------------*/
103 sw_index = 0;
104 if ((heur_par->sweep_trials)&&(vrp->dist.wtype)){
105 s_bufid = init_send(DataInPlace);
106 send_int_array(&dummy, 1);
107 send_msg(tids[sw_index%jobs], S_SWEEP);
108 s_bufid = init_send(DataInPlace);
109 send_int_array(&heur_par->sweep_trials, 1);
110 send_msg(tids[sw_index%jobs], SWEEP_TRIALS);
111 sent[sw_index]++;
112 sw_index++;
113 printf("\nmessage sent\n\n");
114 }
115
116 for(tni_index=sw_index; tni_index<sw_index+heur_par->tsp.ni_trials; tni_index++){
117 s_bufid = init_send(DataInPlace);
118 send_int_array(&dummy, 1);
119 send_msg(tids[tni_index%jobs], S_TSP_NI);
120 sent[tni_index%jobs]++;
121 s_bufid = init_send(DataInPlace);
122 send_int_array(&heur_par->tsp.num_starts, 1);
123 send_msg(tids[tni_index%jobs], TSP_NI_TRIALS);
124 }
125 for(tfi_index=tni_index; tfi_index<tni_index+heur_par->tsp.fi_trials;
126 tfi_index++){
127 s_bufid = init_send(DataInPlace);
128 send_int_array(&dummy, 1);
129 send_msg(tids[tfi_index%jobs], S_TSP_FI);
130 sent[tfi_index%jobs]++;
131 s_bufid = init_send(DataInPlace);
132 send_int_array(&heur_par->tsp.num_starts, 1);
133 send_msg(tids[tfi_index%jobs], TSP_FI_TRIALS);
134 }
135 for(tfini_index=tfi_index; tfini_index<tfi_index+heur_par->tsp.fini_trials;
136 tfini_index++){
137 s_bufid = init_send(DataInPlace);
138 send_int_array(&dummy, 1);
139 send_msg(tids[tfini_index%jobs], S_TSP_FINI);
140 sent[tfini_index%jobs]++;
141 s_bufid = init_send(DataInPlace);
142 send_int_array(&heur_par->tsp.num_starts, 1);
143 send_msg(tids[tfini_index%jobs], TSP_FINI_TRIALS);
144 s_bufid = init_send(DataInPlace);
145 send_int_array(&farside, 1);
146 send_msg(tids[tfini_index%jobs], TSP_FINI_RATIO);
147 }
148
149 //no need to start saving and saving2 here yet, since no data is sent.
150
151 if (heur_par->savings3_par.grid_size &&
152 heur_par->savings3_par.savings_trials &&
153 (vrp->numroutes ||
154 (!vrp->numroutes && vrp->dist.coordx && vrp->dist.coordy)))
155 for(s3_index=tfini_index; s3_index<tfini_index+
156 heur_par->savings3_par.grid_size*
157 heur_par->savings3_par.grid_size; s3_index++){
158 s_bufid = init_send(DataInPlace);
159 send_int_array(&dummy, 1);
160 send_msg(tids[s3_index%jobs], S_SAVINGS3);
161 sent[s3_index%jobs]++;
162 s_bufid = init_send(DataInPlace);
163 send_int_array(&vrp->numroutes, 1);
164 send_msg(tids[s3_index%jobs], S3_NUMROUTES);
165 //sending savings3 parameters below.
166 grid_size = heur_par->savings3_par.grid_size;
167 lamda = heur_par->savings3_par.lamda;
168 mu = heur_par->savings3_par.mu;
169 if (grid_size == 1){
170 lamda_int = 0;
171 mu_int = 0;
172 }
173 else{
174 lamda_int = ((float)lamda)/((float)(grid_size - 1));
175 mu_int = ((float)mu)/((float)(grid_size -1));
176 }
177 for (i=0; i < grid_size; i++){
178 temp_lamda = i * lamda_int;
179 if (i == grid_size-1) temp_lamda = (float) lamda;
180 for (j=0; j < grid_size; j++){
181 temp_mu = j * mu_int;
182 if (j == grid_size-1) temp_mu = (float) mu;
183 s_bufid = init_send(DataInPlace);
184 send_float_array(&temp_mu, 1);
185 send_float_array(&temp_lamda, 1);
186 send_int_array(&start, 1);
187 send_msg(tids[s3_index%jobs], SAVINGS3_DATA);
188 //count++;
189 if (count > savings3_jobs) break;
190 }
191 if (count > savings3_jobs) break;
192 }
193 }
194
195 if (heur_par->near_cluster_trials &&
196 (vrp->numroutes ||
197 ((!vrp->numroutes) && (vrp->dist.wtype)))){
198 s_bufid = init_send(DataInPlace);
199 send_int_array(&dummy, 1);
200 send_msg(tids[s3_index%jobs], S_NEAR_CLUSTER);
201 sent[s3_index%jobs]++;
202 s_bufid = init_send(DataInPlace);
203 send_int_array(&vrp->numroutes, 1);
204 send_msg(tids[s3_index%jobs], NC_NUMROUTES);
205 }
206 // Above, msg for cluster heuristic sent to the next available process
207
208 /*------------------------------------------------------------------------*\
209 | Generate the random starting points and broadcast |
210 \*------------------------------------------------------------------------*/
211 SRANDOM(vrp->par.rand_seed[0]);
212 heur_par->tsp.ni_trials = MIN(heur_par->tsp.ni_trials, vertnum);
213 heur_par->tsp.fi_trials = MIN(heur_par->tsp.ni_trials, vertnum);
214 heur_par->tsp.fini_trials = MIN(heur_par->tsp.ni_trials, vertnum);
215 starter = ch->starter =
216 (int *) calloc (heur_par->tsp.ni_trials + heur_par->tsp.fi_trials +
217 heur_par->tsp.fini_trials, sizeof(int));
218 generate_starter(vertnum-1, starter, heur_par->tsp.ni_trials);
219 generate_starter(vertnum-1, starter + heur_par->tsp.ni_trials,
220 heur_par->tsp.fi_trials);
221 generate_starter(vertnum-1, starter + heur_par->tsp.ni_trials +
222 heur_par->tsp.fi_trials, heur_par->tsp.fini_trials);
223 if (heur_par->tsp.ni_trials) //here, vertnum variable//
224 starter[0] = vertnum; //is sent to each tsp //
225 if (heur_par->tsp.fi_trials) //heuristic as the first//
226 starter[tni_index] = vertnum; //message. //
227 if (heur_par->tsp.fini_trials) /////////////////////////
228 starter[tfi_index] = vertnum;
229
230 for (i=0; i< heur_par->tsp.ni_trials+heur_par->tsp.fi_trials
231 +heur_par->tsp.fini_trials; i++){
232 s_bufid = init_send(DataInPlace);
233 send_int_array(starter+i, 1);
234 send_msg(tids[(i+sw_index)%jobs], TSP_START_POINT);
235 }
236
237 /*-----------------------------------------------------------------------*\
238 | Broadcast parameters to savings |
239 \*-----------------------------------------------------------------------*/
240
241 /*--------------------------------------------------------------------*\
242 | Here is where the parameter settings are given to the various |
243 | savings proceses. The parameters mu and lamda from the parameter |
244 | file indicate maximum values for these particular parameters. Then |
245 | depending on the grid-size that is specified, I partition the |
246 | square (0, mu) X (0, lamda) into a grid and send various |
247 | combinations of parameters to the various processes. Also, I give |
248 | the processes different starting point rules. If I send FAR_INS to |
249 | a process, then the frathest customer from the depot is always |
250 | used to intialize new routes. Otherwise, I send a random seed that |
251 | can be used to randonly select the next customer to be added to a |
252 | route. The first "block" of trials receives the FAR_INS signal. |
253 | The remaining blocks, launched if savings_trials >1, receive |
254 | random seeds |
255 \*--------------------------------------------------------------------*/
256
257 if (heur_par->savings_par.grid_size && heur_par->savings_par.savings_trials){
258 temp_tid = savings_tid;
259 grid_size = heur_par->savings_par.grid_size;
260 lamda = heur_par->savings_par.lamda;
261 mu = heur_par->savings_par.mu;
262 if (grid_size == 1){
263 lamda_int = 0;
264 mu_int = 0;
265 }
266 else{
267 lamda_int = ((float)lamda)/((float)(grid_size - 1));//lambda interval
268 mu_int = ((float)mu)/((float)(grid_size -1));//mu interval
269 }
270 for (l=0; l<heur_par->savings_par.savings_trials; l++){
271 switch(l){
272 case 0: start = FAR_INS;
273 break; /*send FAR_INS rule to the first "block"*/
274 default: start = vrp->par.rand_seed[(l-1)%6];
275 } /*send random seeds to the remaining blocks*/
276 for (i=0; i < grid_size; i++){
277 temp_lamda = i * lamda_int;
278 if (i == grid_size-1) temp_lamda = (float) lamda;
279 for (j=0; j < grid_size; j++){
280 temp_mu = j * mu_int;
281 if (j == grid_size-1) temp_mu = (float) mu;
282 s_bufid = init_send(DataInPlace);
283 send_int_array(&dummy, 1);
284 send_msg(tids[(s3_index+1+count)%jobs], S_SAVINGS);
285 sent[(s3_index+1+count)%jobs]++;
286 s_bufid = init_send(DataInPlace);
287 send_float_array(&temp_mu, 1);
288 send_float_array(&temp_lamda, 1);
289 send_int_array(&start, 1);
290 send_msg(tids[(s3_index+1+count)%jobs], SAVINGS_DATA);
291 count++;
292 if (count > heur_par->savings_par.savings_trials) break;
293 }
294 if (count > heur_par->savings_par.savings_trials) break;
295 }
296 }
297 }
298
299 /*This is the same as above except for savings2 instead *\
300 \*of savings. */
301 if (heur_par->savings_par.grid_size && heur_par->savings_par.savings2_trials){
302 temp_tid = savings2_tid;
303 grid_size = heur_par->savings_par.grid_size;
304 lamda = heur_par->savings_par.lamda;
305 mu = heur_par->savings_par.mu;
306 if (grid_size == 1){
307 lamda_int = 0;
308 mu_int = 0;
309 }
310 else{
311 lamda_int = ((float)lamda)/((float)(grid_size - 1));
312 mu_int = ((float)mu)/((float)(grid_size -1));
313 }
314 for(l = 0; l < heur_par->savings_par.savings2_trials; l++){
315 switch(l){
316 case 0: start = FAR_INS;
317 break;
318 default: start = vrp->par.rand_seed[(l-1)%6];
319 }
320 for (i = 0; i < grid_size; i++){
321 temp_lamda = i * lamda_int;
322 if (i == grid_size-1) temp_lamda = (float) lamda;
323 for (j = 0; j < grid_size; j++){
324 temp_mu = j * mu_int;
325 if (j == grid_size-1) temp_mu = (float) mu;
326 s_bufid = init_send(DataInPlace);
327 send_int_array(&dummy, 1);
328 send_msg(tids[(s3_index+1+count)%jobs], S_SAVINGS2);
329 sent[(s3_index+1+count)%jobs]++;
330 s_bufid = init_send(DataInPlace);
331 send_float_array(&temp_mu, 1);
332 send_float_array(&temp_lamda, 1);
333 send_int_array(&start, 1);
334 send_msg(tids[(s3_index+1+count)%jobs], SAVINGS2_DATA);
335 count++;
336 if (count > savings2_jobs) break;
337 }
338 if (count > savings2_jobs) break;
339 }
340 }
341 }
342 }
343
344