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 (ted@lehigh.edu) */
8 /* This file was modified by Ali Pilatin January, 2005 (alp8@lehigh.edu) */
9 /* */
10 /* (c) Copyright 2000-2005 Ted Ralphs. All Rights Reserved. */
11 /* */
12 /* This software is licensed under the Eclipse Public License. Please see */
13 /* accompanying file for terms. */
14 /* */
15 /*===========================================================================*/
16
17 #include "mst.h"
18 #include <string.h>
19 #include <stdio.h>
mst(void)20 void mst(void)
21 {
22 printf("\nIn mst....\n\n");
23 lb_prob *p;
24 int mytid, info, s_bufid, r_bufid, parent, bytes, msgtag;
25 int *tree, *best_tree;
26 int *lamda;
27 int cur_cost, cur_bound, best_bound = 0, alpha = 0;
28 int vertnum, numroutes;
29 int y, cur_node1, cur_node2, m1;
30 int iter_count = 0, i, k, max_iter;
31 int tree_cost, upper_bound;
32 edge_data *cheapest_edges, *depot_costs, *best_edges, *cur_edges;
33 char best = FALSE;
34 double t=0, cpu_time;
35
36 (void) used_time(&t);
37
38 mytid = pvm_mytid();
39
40 p = (lb_prob *) calloc ((int)1, sizeof(lb_prob));
41
42 /*------------------------------------------------------------------------*\
43 | Receive the VRP data |
44 \*------------------------------------------------------------------------*/
45 //the block below is same as receive(P), except for freeing r_bufid
46 PVM_FUNC(r_bufid, pvm_recv(-1, VRP_BROADCAST_DATA));
47 PVM_FUNC(info, pvm_bufinfo(r_bufid, &bytes, &msgtag, &parent));
48 PVM_FUNC(info, pvm_upkint(&(p->dist.wtype), 1, 1));
49 PVM_FUNC(info, pvm_upkint(&(p->vertnum), 1, 1));
50 PVM_FUNC(info, pvm_upkint(&(p->depot), 1, 1));
51 PVM_FUNC(info, pvm_upkint(&p->capacity, 1, 1));
52 p->demand = (int *) calloc (p->vertnum, sizeof(int));
53 PVM_FUNC(info, pvm_upkint(p->demand, p->vertnum, 1));
54 p->edgenum = p->vertnum*(p->vertnum-1)/2;
55 if (p->dist.wtype){ /* not EXPLICIT */
56 p->dist.coordx = (double *) calloc(p->vertnum, sizeof(double));
57 p->dist.coordy = (double *) calloc(p->vertnum, sizeof(double));
58 PVM_FUNC(info, pvm_upkdouble(p->dist.coordx, (int)p->vertnum, 1));
59 PVM_FUNC(info, pvm_upkdouble(p->dist.coordy, (int)p->vertnum, 1));
60 if ((p->dist.wtype == _EUC_3D) || (p->dist.wtype == _MAX_3D) ||
61 (p->dist.wtype == _MAN_3D)){
62 p->dist.coordz = (double *) calloc(p->vertnum, sizeof(double));
63 PVM_FUNC(info, pvm_upkdouble(p->dist.coordz, (int)p->vertnum, 1));
64 }
65 }
66 else{ /* EXPLICIT */
67 p->dist.cost = (int *) malloc ((int)p->edgenum*sizeof(int));
68 PVM_FUNC(info, pvm_upkint(p->dist.cost, (int)p->edgenum, 1));
69 }//above mentioned block ends here
70
71 PVM_FUNC(r_bufid, pvm_recv(-1, VRP_LB_DATA));
72 PVM_FUNC(info, pvm_upkint(&numroutes, 1, 1));
73 PVM_FUNC(info, pvm_upkint(&upper_bound, 1, 1));
74 PVM_FUNC(info, pvm_upkint(&max_iter, 1, 1));
75 PVM_FUNC(info, pvm_upkint(&m1, 1, 1));
76
77 PVM_FUNC(r_bufid, pvm_recv(-1, VRP_LB_DATA2));
78 PVM_FUNC(info, pvm_upkint(&y, 1, 1));
79 PVM_FUNC(info, pvm_upkint(&alpha, 1, 1));
80
81 vertnum = p->vertnum;
82
83 /*------------------------------------------------------------------------*\
84 | Allocate arrays |
85 \*------------------------------------------------------------------------*/
86 tree = (int *) calloc (vertnum, sizeof(int));
87 best_tree = (int *) calloc (vertnum, sizeof(int));
88 lamda = (int *) calloc (vertnum, sizeof(int));
89 cheapest_edges = (edge_data *) calloc (vertnum-1, sizeof(edge_data));
90 best_edges = (edge_data *) calloc (numroutes, sizeof(edge_data));
91 cur_edges = (edge_data *) calloc (numroutes, sizeof(edge_data));
92 depot_costs = (edge_data *) calloc (vertnum-1, sizeof(edge_data));
93
94 /*------------------------------------------------------------------------*\
95 | My lower bound calculation will follow the methodology in _____________ |
96 | See that paper for details. |
97 \*------------------------------------------------------------------------*/
98
99 k=2*numroutes-y;
100
101 for(iter_count = 0; iter_count < max_iter;){
102
103 /*---------------------------------------------------------------------*\
104 | Calculate a k-degree-centre-tree with penalties lamda |
105 \*---------------------------------------------------------------------*/
106
107 tree_cost = make_k_tree(p, tree, lamda, k);
108
109 /*----------------------------------------------------------------------*\
110 | Construct a sorted list of the cheapest edges adjacent to each node in |
111 | the graph. |
112 \*----------------------------------------------------------------------*/
113
114 for (cur_node1 = 1; cur_node1 < vertnum; cur_node1++)
115 cheapest_edges[cur_node1-1].cost = MAXINT;
116
117 for (cur_node1 = 1; cur_node1 < vertnum; cur_node1++)
118 for (cur_node2 = cur_node1 + 1; cur_node2 < vertnum; cur_node2++)
119 if (((cur_cost = MCOST(&p->dist, cur_node1, cur_node2, lamda)) <
120 cheapest_edges[cur_node1-1].cost) && tree[cur_node1] != cur_node2
121 && tree[cur_node2] != cur_node1){
122 cheapest_edges[cur_node1-1].cost = cur_cost;
123 cheapest_edges[cur_node1-1].v0 = cur_node1;
124 cheapest_edges[cur_node1-1].v1 = cur_node2;
125 }
126
127 qsort(cheapest_edges, vertnum-1, sizeof(edge_data), edgecompar);
128
129 /*---------------------------------------------------------------------*\
130 | Construct a sorted list of the cheapest edges adjacent to the depot |
131 \*---------------------------------------------------------------------*/
132
133 for (cur_node1 = 1; cur_node1 < vertnum; cur_node1++){
134 depot_costs[cur_node1-1].cost = MCOST(&p->dist, 0, cur_node1, lamda);
135 depot_costs[cur_node1-1].v1 = cur_node1;
136 }
137
138 qsort(depot_costs, vertnum-1, sizeof(edge_data), edgecompar);
139
140 /*---------------------------------------------------------------------*\
141 | Form the bound by taking edges from cheapest_edges and depot_costs, |
142 | along with the tree calculated earlier. |
143 \*---------------------------------------------------------------------*/
144
145 memcpy (cur_edges, cheapest_edges, (numroutes-y)*sizeof(edge_data));
146 memcpy (cur_edges+numroutes-y, depot_costs, m1*sizeof(edge_data));
147 for (i = 0; i < y-m1; i++)
148 cur_edges[numroutes-y+m1+i] = depot_costs[m1+2*i+1];
149 for (cur_bound = i = 0; i < numroutes; i++)
150 cur_bound += MCOST(&p->dist, cur_edges[i].v0, cur_edges[i].v1, lamda);
151 cur_bound += tree_cost;
152
153 /*---------------------------------------------------------------------*\
154 | Check if this bound improves the previous best bound |
155 \*---------------------------------------------------------------------*/
156
157 if (cur_bound > best_bound){
158 best_bound = cur_bound;
159 memcpy (best_tree, tree, vertnum*sizeof(int));
160 memcpy (best_edges, cur_edges, numroutes*sizeof(edge_data));
161 }
162
163 /*---------------------------------------------------------------------*\
164 | Update the penalties and go back to the beginning |
165 \*---------------------------------------------------------------------*/
166
167 iter_count++;
168 if ((iter_count == 1) && (!alpha))
169 alpha = best_bound/(10*vertnum);
170 if (iter_count < max_iter)
171 best = new_lamda(p, upper_bound, cur_bound, lamda, numroutes,
172 tree, cur_edges, alpha);
173
174 if ((best) || (iter_count >= max_iter) || (cur_bound < 0)) break;
175 }
176
177 /*------------------------------------------------------------------------*\
178 | Transmit the tree and best_edges back to the parent |
179 \*------------------------------------------------------------------------*/
180
181 PVM_FUNC(s_bufid, pvm_initsend(PvmDataRaw));
182 PVM_FUNC(info, pvm_pkint(best_tree, vertnum, 1));
183 PVM_FUNC(info, pvm_pkbyte((char *)best_edges, numroutes*sizeof(edge_data),
184 1));
185 PVM_FUNC(info, pvm_pkint(&best_bound, 1, 1));
186 cpu_time = used_time (&t);
187 PVM_FUNC(info, pvm_pkdouble(&cpu_time, 1, 1));
188 PVM_FUNC(info, pvm_send(parent, LOWER_BOUND));
189 PVM_FUNC(info, pvm_freebuf(s_bufid));
190
191 if ( tree ) free ((char *) tree);
192 if ( best_tree ) free ((char *) best_tree);
193 if ( lamda ) free ((char *) lamda);
194 if ( cheapest_edges ) free ((char *) cheapest_edges);
195 if ( best_edges ) free ((char *) best_edges);
196 if ( cur_edges ) free ((char *) cur_edges);
197 if ( depot_costs ) free ((char *) depot_costs);
198
199 free_lb_prob(p);
200
201 }
202