Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/vrp_master_functions.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 #ifndef WIN32
18 #include <unistd.h>
19 #endif
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <stddef.h>
23 #include <string.h>
24 #include <sys/types.h>
25
26 /* SYMPHONY include files */
27 #include "sym_constants.h"
28 #include "sym_proccomm.h"
29
30 /* VRP include files */
31 #include "vrp_const.h"
32 #include "vrp_master_functions.h"
33 #include "vrp_macros.h"
34
35 /*===========================================================================*/
36
37 int is_same_edge(const void *ed0, const void *ed1)
38 {
39 return((INDEX(((edge_data *)ed0)->v0, ((edge_data *)ed0)->v1)) -
40 (INDEX(((edge_data *)ed1)->v0, ((edge_data *)ed1)->v1)));
41 }
42
43 /*===========================================================================*/
44
45 /*__BEGIN_EXPERIMENTAL_SECTION__*/
46 #if 0
47 /* This comparison function can be used to sort lexicographically */
48 /*===========================================================================*/
49
50 int is_same_edge(const void *ed0, const void *ed1)
51 {
52 return(((edge_data *)ed0)->v0 - ((edge_data *)ed1)->v0 ?
53 ((edge_data *)ed0)->v0 - ((edge_data *)ed1)->v0 :
54 ((edge_data *)ed0)->v1 - ((edge_data *)ed1)->v1);
55 }
56
57 /*===========================================================================*/
58 #endif
59 /*___END_EXPERIMENTAL_SECTION___*/
60 void delete_dup_edges(small_graph *g)
61 {
62 edge_data *ed0, *ed1;
63 int pos;
64 int alloc_old = g->allocated_edgenum;
65
66 qsort((char *)g->edges, g->edgenum, sizeof(edge_data), is_same_edge);
67 for (pos=0, ed0=ed1=g->edges ; pos < g->edgenum; pos++, ed1++){
68 if ( memcmp((char *)ed0, (char *)ed1, 2*sizeof(int)) ){
69 ed0++;
70 if (ed0 != ed1){
71 (void)memcpy((char *)ed0, (char *)ed1, sizeof(edge_data));
72 }
73 }
74 }
75 pos = ((ptrdiff_t)ed0 - (ptrdiff_t)g->edges)/sizeof(edge_data) + 1;
76 g->allocated_edgenum -= g->edgenum - pos;
77 if (alloc_old){
78 g->edges = (edge_data *) realloc
79 ((char *)(g->edges), g->allocated_edgenum * sizeof(edge_data));
80 }else {
81 g->edges = (edge_data *) calloc(g->allocated_edgenum, sizeof(edge_data));
82 }
83 g->edgenum = pos;
84 }
85
86 /*__BEGIN_EXPERIMENTAL_SECTION__*/
87 /*===========================================================================*/
88
89 /*===========================================================================*\
90 * This function broadcasts various data that the processes need to
91 * compute heuristic solutions.
92 \*===========================================================================*/
93
94 void broadcast(vrp_problem *vrp, int *tids, int jobs)
95 {
96 int s_bufid;
97
98 if (jobs == 0) return;
99
100 s_bufid = init_send(DataInPlace);
101 send_int_array(&vrp->dist.wtype, 1);
102 send_int_array(&vrp->vertnum, 1);
103 send_int_array(&vrp->depot, 1);
104 send_int_array(&vrp->capacity, 1);
105 send_int_array(vrp->demand, (int)vrp->vertnum);
106 if (vrp->dist.wtype != _EXPLICIT){ /* not EXPLICIT */
107 send_dbl_array(vrp->dist.coordx, vrp->vertnum);
108 send_dbl_array(vrp->dist.coordy, vrp->vertnum);
109 if ((vrp->dist.wtype == _EUC_3D) || (vrp->dist.wtype == _MAX_3D) ||
110 (vrp->dist.wtype == _MAN_3D))
111 send_dbl_array(vrp->dist.coordz, vrp->vertnum);
112 }
113 else{ /* EXPLICIT */
114 send_int_array(vrp->dist.cost, (int)vrp->edgenum);
115 }
116 msend_msg(tids, jobs, VRP_BROADCAST_DATA);
117
118 freebuf(s_bufid);
119 }
120
121 /*___END_EXPERIMENTAL_SECTION___*/
122 /*===========================================================================*/
123
124 int *create_edge_list(vrp_problem *vrp, int *varnum, char which_edges)
125 {
126 int i, j, k;
127 int zero_varnum, edgenum, new_ind;
128 int *zero_vars, *uind = NULL;
129 int total_edgenum = vrp->vertnum*(vrp->vertnum-1)/2;
130
131 switch(which_edges){
132 case CHEAP_EDGES:
133
134 vrp->zero_vars = zero_vars = (int *) calloc(total_edgenum, sizeof(int));
135
136 /*first determine which variables can be fixed to zero permanently*/
137 for (zero_varnum=0, i=2; i<vrp->vertnum; i++){
138 for (j=1; j<i; j++){
139 if (vrp->demand[i] + vrp->demand[j] > vrp->capacity){
140 zero_vars[zero_varnum++] = INDEX(i,j);
141 }
142 }
143 }
144 edgenum = vrp->par.add_all_edges ?
145 vrp->vertnum*(vrp->vertnum-1)/2 : vrp->g->edgenum;
146
147 /*First, we construct the index lists*/
148 uind = (int *) malloc(edgenum * ISIZE);
149 *varnum = 0;
150 switch(vrp->par.add_all_edges){
151 case FALSE:
152 for (i = 0, j = 0; i<edgenum && j<zero_varnum; i++){
153 new_ind = INDEX(vrp->g->edges[i].v0, vrp->g->edges[i].v1);
154 if (new_ind < zero_vars[j]){
155 uind[(*varnum)++] = new_ind;
156 }else{
157 while (j < zero_varnum && new_ind > zero_vars[j])
158 j++;
159 if (j == zero_varnum){
160 uind[(*varnum)++] = new_ind;
161 }else if (new_ind < zero_vars[j]){
162 uind[(*varnum)++] = new_ind;
163 }else{
164 j++;
165 }
166 }
167 }
168 /*Now we have exhausted all the zero edges*/
169 for (; i<edgenum; i++)
170 uind[(*varnum)++] =
171 INDEX(vrp->g->edges[i].v0, vrp->g->edges[i].v1);
172 break;
173 case TRUE:
174 for (i = 0, j = 0; j<zero_varnum; i++){
175 if (zero_vars[j] == i){
176 j++;
177 continue;
178 }
179 uind[(*varnum)++] = i;
180 }/*Now, we have exhausted all the zero edges*/
181 for (; i <edgenum; i++){
182 uind[(*varnum)++] = i;
183 }
184 break;
185 }
186
187 #if 0
188 if (vrp->par.verbosity > 0)
189 printf("Fixed %i edges in root creation\n\n", zero_varnum);
190 #endif
191
192 vrp->zero_varnum = zero_varnum;
193
194 break;
195
196 case REMAINING_EDGES:
197
198 /*In this case, we are adding all variables at the root, but the small
199 graph edges are base and the rest are extra*/
200
201 zero_varnum = vrp->zero_varnum;
202 zero_vars = vrp->zero_vars;
203 edgenum = vrp->g->edgenum;
204
205 uind = (int *) malloc((total_edgenum-edgenum+vrp->vertnum-1) * ISIZE);
206
207 *varnum = 0;
208 for (i = 0, j = 0, k = 0; i<edgenum; i++, k++){
209 /*In this loop, we check each edge to see if it is in the small
210 graph and whether it is a zero edge*/
211 new_ind = INDEX(vrp->g->edges[i].v0, vrp->g->edges[i].v1);
212 for (; k < new_ind; k++){
213 if ((j < zero_varnum && k < zero_vars[j]) || j >= zero_varnum){
214 uind[(*varnum)++] = k;
215 }else{
216 while (j < zero_varnum && k > zero_vars[j])
217 j++;
218 if (j == zero_varnum){
219 uind[(*varnum)++] = k;
220 }else if (k < zero_vars[j]){
221 uind[(*varnum)++] = k;
222 }else{
223 j++;
224 }
225 }
226 }
227 /*k == new_ind here so we don't want to add that edge */
228 }
229 /*Now, we have exhausted the small graph so just add all non-zero
230 edges*/
231 while (j < zero_varnum && k > zero_vars[j])
232 j++;
233 for (; k<total_edgenum && j<zero_varnum; k++)
234 if (k < zero_vars[j])
235 uind[(*varnum)++] = k;
236 else
237 j++;
238 /* Now, there are no more non-zero edges either so add the rest*/
239 for (; k<total_edgenum; k++)
240 uind[(*varnum)++] = k;
241
242 break;
243 }
244
245 return(uind);
246 }