Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/Heuristics/start_heurs.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
18 #include <memory.h>
19 #include <stdio.h>
20
21 #include "BB_constants.h"
22 #include "BB_macros.h"
23 #include "start_heurs.h"
24 #include "cluster_heur.h"
25 #include "route_heur.h"
26 #include "exchange_heur.h"
27 #include "small_graph.h"
28 #include "receive_rout.h"
29 #include "collect_solutions.h"
30 #include "lower_bound.h"
31 #include "sym_timemeas.h"
32 #include "vrp_const.h"
33 #include "sym_dg_params.h"
34 #include "vrp_sym_dg.h"
35 #include "sym_proccomm.h"
36 #include "vrp_master_functions.h"
37
38 void start_heurs(vrp_problem *vrp, heur_params *heur_par, lb_params *lb_par,
39 double *ub, char windows)
40 {
41 int pos, last, mytid;
42 int *tids, *sent, dummy;
43 int trials = 0, i, jobs = 0;
44 best_tours *tours = NULL;
45 best_tours *solutions = NULL;
46 int *tourorder = NULL, ub_pos;
47 heurs *heur_out = NULL;
48 double heurtime = 0, lbtime = 0, t = 0;
49
50 mytid = pvm_mytid();
51 (void)used_time(&t);
52
53 tids = (int *) malloc((heur_par->no_of_machines)*sizeof(int));
54
55 /*-----------------------------------------------------------------------*\
56 | start parallel processes & send common data |
57 \*-----------------------------------------------------------------------*/
58
59 jobs = spawn(vrp->par.executables.heuristics, (char **)NULL,
60 vrp->par.debug.heuristics, (char *)NULL,
61 heur_par->no_of_machines, tids);
62 sent = (int *) calloc(jobs, sizeof(int));
63 printf("\nHello, jobs %i %i %i are spawned\n", tids[0],tids[1], tids[2]);
64
65 broadcast(vrp, tids, jobs);
66
67 /*-----------------------------------------------------------------------*\
68 | start the cluster heuristics |
69 \*-----------------------------------------------------------------------*/
70
71 heur_out = (heurs *) calloc (1, sizeof(heurs));
72
73 if (vrp->par.do_heuristics){
74 if (heur_par->sweep_trials && vrp->dist.coordx && vrp->dist.coordy){
75 trials += 1;
76 }
77 if (heur_par->savings3_par.savings_trials && (vrp->numroutes ||
78 (!vrp->numroutes && vrp->dist.coordx && vrp->dist.coordy))){
79 trials += heur_par->savings3_par.grid_size
80 * heur_par->savings3_par.grid_size;
81 }
82 if (heur_par->near_cluster_trials && (vrp->numroutes ||
83 (!vrp->numroutes && vrp->dist.coordx && vrp->dist.coordy))){
84 trials += 1;
85 }
86
87 trials += ((heur_par->savings_par.savings_trials +
88 heur_par->savings_par.savings2_trials)
89 * (heur_par->savings_par.grid_size *
90 heur_par->savings_par.grid_size) +
91 heur_par->tsp.ni_trials + heur_par->tsp.fi_trials +
92 heur_par->tsp.fini_trials);
93 }else{
94 trials = 0;
95 }
96
97 printf("\nname of p_process = %s \n\n", vrp->par.executables.heuristics);
98 if (trials){
99
100 cluster_heur(vrp, heur_par, heur_out, trials, jobs, tids, sent);
101
102 printf("\nNo jobs: %i \n\n", jobs);
103 /*-----------------------------------------------------------------------*\
104 | receive the heuristical tours |
105 \*-----------------------------------------------------------------------*/
106
107 if (trials){
108 tours = vrp->tours;
109 vrp->tours[0].cost = MAXINT;
110 vrp->tours[0].tour = (_node *) calloc
111 (vrp->par.tours_to_keep, vrp->vertnum * sizeof(_node));
112 for (pos=1; pos<vrp->par.tours_to_keep; pos++){
113 tours[pos].tour = tours[pos-1].tour + vrp->vertnum;
114 tours[pos].cost = MAXINT;
115 }
116 tourorder = vrp->tourorder = (int *)
117 calloc(vrp->par.tours_to_keep+1, sizeof(int));
118 vrp->tournum = -1; /*status of
119 heuristics*/
120 heurtime += receive_tours(vrp, heur_out, &last, TRUE, FALSE, FALSE,
121 windows, jobs, sent);
122 /*receives the tours output by *\
123 | the clustering processes and |
124 | orders them , keeping the |
125 | best "vrp->par.tours_to_keep" |
126 \*of them at hand. */
127 }
128
129 /*-----------------------------------------------------------------------*\
130 | Start the route heuristics |
131 \*-----------------------------------------------------------------------*/
132
133 trials = trials ? MIN(vrp->tournum+1, heur_par->route_opt1) : 0;
134 solutions = (best_tours *) malloc(trials*sizeof(best_tours));
135 if (trials){
136 route_heur(vrp, heur_par, heur_out, trials, jobs, tids, sent, solutions);
137 // printf("\nTids after route_heur %i % i%i", tids[0], tids[1], tids[2]);
138 heurtime += collect_solutions(vrp, trials, &last, FALSE, solutions);
139 }
140
141 /*-----------------------------------------------------------------------*\
142 | Start the exchange heuristics |
143 \*-----------------------------------------------------------------------*/
144
145 trials = trials ? MIN(vrp->tournum+1, heur_par->exchange) : 0;
146 if (trials){
147 exchange_heur(vrp, heur_out, trials, jobs, FIRST_SET, tids, sent);
148 heurtime += receive_tours(vrp, heur_out, &last, TRUE, FALSE, FALSE,
149 windows, jobs, sent);
150 }
151
152 /*-----------------------------------------------------------------------*\
153 | Run the route heuristics again |
154 \*-----------------------------------------------------------------------*/
155 trials = trials ? MIN(vrp->tournum+1, heur_par->route_opt2) : 0;
156 if (trials){
157 solutions = (best_tours *) malloc(trials*sizeof(best_tours));
158 route_heur(vrp, heur_par, heur_out, trials, jobs, tids, sent, solutions);
159 heurtime += collect_solutions(vrp, trials, &last, FALSE, solutions);
160 }
161
162 /*-----------------------------------------------------------------------*\
163 | Start the second set of exchange heuristics |
164 \*-----------------------------------------------------------------------*/
165
166 trials = trials ? MIN(vrp->tournum+1, heur_par->exchange2) : 0;
167 if (trials){
168 exchange_heur(vrp, heur_out, trials, jobs, SECOND_SET, tids, sent);
169 heurtime += receive_tours(vrp, heur_out, &last, TRUE, FALSE, FALSE,
170 windows, jobs, sent);
171 }
172 /*-----------------------------------------------------------------------*\
173 | Run route heuristics once more |
174 \*-----------------------------------------------------------------------*/
175
176 trials = trials ? MIN(vrp->tournum+1, heur_par->route_opt3) : 0;
177 solutions = (best_tours *) malloc(trials*sizeof(best_tours));
178 if (trials){
179 route_heur(vrp, heur_par, heur_out, trials, jobs, tids, sent, solutions);
180 make_small_graph(vrp, 2*heur_out->jobs*vrp->vertnum);
181 heurtime += collect_solutions(vrp, trials, &last, TRUE, solutions);
182 }
183
184 /*-----------------------------------------------------------------------*\
185 | Compute the upper and lower bounds |
186 \*-----------------------------------------------------------------------*/
187 vrp->lb->lower_bound = (double) 0;
188 ub_pos = -1;
189
190 if (vrp->tournum>=0 && *ub <= 0){
191 if (!vrp->numroutes){
192 vrp->numroutes = tours[tourorder[0]].numroutes;
193 *ub = (double) tours[tourorder[0]].cost;
194 ub_pos = 0;
195 }
196 else{
197 for (i=0; i<= vrp->tournum; i++)
198 if (tours[tourorder[i]].numroutes == vrp->numroutes){
199 *ub = (double) tours[tourorder[i]].cost;
200 ub_pos = i;
201 break;
202 }
203 }
204 if (ub_pos >= 0){
205 /*vrp->cur_tour = &tours[tourorder[ub_pos]];*/
206 vrp->cur_tour->numroutes = tours[tourorder[ub_pos]].numroutes;
207 vrp->cur_tour->cost = tours[tourorder[ub_pos]].cost;
208 memcpy((char *)vrp->cur_tour->tour,
209 (char *)tours[tourorder[ub_pos]].tour,
210 vrp->vertnum*sizeof(_node));
211 vrp->cur_tour->algorithm = 0;
212 vrp->cur_tour->solve_time = 0;
213 FREE(vrp->cur_tour->route_info);
214 }else{
215 printf("No tours found with %i routes -- no upper bound found\n\n",
216 vrp->numroutes);
217 }
218 }
219
220 vrp->bd_time.ub_overhead = used_time(&t);
221 vrp->bd_time.ub_heurtime = heurtime;
222
223 if (vrp->numroutes && lb_par->lower_bound){
224 lower_bound(vrp, lb_par, heur_out, (int)(*ub), jobs, tids, sent);
225 lbtime += receive_lbs(vrp, heur_out, 1, vrp->numroutes, jobs, sent);
226 }
227
228 vrp->bd_time.lb_overhead += used_time(&t);
229 vrp->bd_time.lb_heurtime = lbtime;
230
231 if (heur_out) free((char *)heur_out);
232
233 if (ub_pos>=0 && vrp->par.verbosity>0){
234 printf("\nThe best upper bound found with %i trucks is %i\n\n",
235 vrp->numroutes, (int)(*ub));
236 if (vrp->par.verbosity >1){
237 if (windows){
238 /*if (!vrp->window)
239 vrp->window = init_win(vrp->par.executables.winprog,
240 vrp->par.debug.winprog,
241 vrp->posx, vrp->posy, vrp->vertnum);
242 vrp->window->windata.draw = TRUE;
243 disp_tour(vrp->window, tours[tourorder[ub_pos]].tour, TRUE);*/
244 }
245 }
246 }
247 else if (*ub && vrp->par.verbosity > 2){
248 printf("\nUsing upper bound of %i given in parameter file\n\n",
249 (int)(*ub));
250 }
251
252 if (vrp->lb->lower_bound && vrp->par.verbosity>0){
253 printf("\nThe best lower bound found with %i trucks is %.1f\n\n",
254 vrp->numroutes, vrp->lb->lower_bound);
255 #if 0
256 if (vrp->par.verbosity >1 && vrp->dg_id){
257 char name[20] = {"Lower Bound"};
258 disp_lb(vrp->dg_id, TRUE, name, vrp->lb->tree, vrp->lb->best_edges,
259 vrp->vertnum, vrp->numroutes, CTOI_WAIT_FOR_CLICK_AND_REPORT);
260 }
261 #endif
262 }
263
264 /*
265 p->comp_times.bc_overhead = used_time(&t);
266 */
267 init_send(DataInPlace);
268 send_int_array(&dummy, 1);
269 msend_msg(tids, jobs, STOP);
270 for(i=0; i<jobs; kill_proc(tids[i++]));
271 }
272 }