Debian Codegraph @

SYMPHONY/Applications/CNRP/src/Master/cnrp_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 /* Capacitated Network Routing Problems. */
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 #include "sym_qsort.h"
30
31 /* CNRP include files */
32 #include "cnrp_const.h"
33 #include "cnrp_master_functions.h"
34 #include "cnrp_macros.h"
35
36 /*===========================================================================*/
37
38 int is_same_edge(const void *ed0, const void *ed1)
39 {
40 return((INDEX(((edge_data *)ed0)->v0, ((edge_data *)ed0)->v1)) -
41 (INDEX(((edge_data *)ed1)->v0, ((edge_data *)ed1)->v1)));
42 }
43
44 /*===========================================================================*/
45
46 /*__BEGIN_EXPERIMENTAL_SECTION__*/
47 #if 0
48 /* This comparison function can be used to sort lexicographically */
49 /*===========================================================================*/
50
51 int is_same_edge(const void *ed0, const void *ed1)
52 {
53 return(((edge_data *)ed0)->v0 - ((edge_data *)ed1)->v0 ?
54 ((edge_data *)ed0)->v0 - ((edge_data *)ed1)->v0 :
55 ((edge_data *)ed0)->v1 - ((edge_data *)ed1)->v1);
56 }
57
58 /*===========================================================================*/
59 #endif
60 /*__END_EXPERIMENTAL_SECTION__*/
61 void delete_dup_edges(small_graph *g)
62 {
63 edge_data *ed0, *ed1;
64 int pos;
65
66 qsort((char *)g->edges, g->edgenum, sizeof(edge_data),
67 is_same_edge);
68 for (pos=0, ed0=ed1=g->edges ; pos < g->edgenum; pos++, ed1++){
69 if ( memcmp((char *)ed0, (char *)ed1, 2*sizeof(int)) ){
70 ed0++;
71 (void)memcpy((char *)ed0, (char *)ed1, sizeof(edge_data));
72 }
73 }
74 pos = ed0 - g->edges + 1;
75 g->allocated_edgenum -= g->edgenum - pos;
76 g->edges = (edge_data *) realloc
77 ((char *)(g->edges), g->allocated_edgenum * sizeof(edge_data));
78 g->edgenum = pos;
79 }
80
81 /*===========================================================================*\
82 * This is the function that creates the list of variables (edges in the graph)
83 \*===========================================================================*/
84
85 void cnrp_create_variables(cnrp_problem *cnrp)
86 {
87 int base_varnum = 0, i, j, k, l;
88 int zero_varnum, *zero_vars;
89 int *edges;
90 int vertnum = cnrp->vertnum;
91
92 #ifdef DIRECTED_X_VARS
93 /*whether or not we will have the out-degree constraints*/
94 char od_const = (cnrp->par.prob_type == TSP || cnrp->par.prob_type == VRP ||
95 cnrp->par.prob_type == BPP);
96 char d_x_vars = TRUE;
97 #else
98 char od_const = FALSE;
99 char d_x_vars = FALSE;
100 #endif
101 int total_edgenum = vertnum*(vertnum - 1)/2;
102 #ifdef ADD_FLOW_VARS
103 int v0, v1;
104 double flow_capacity;
105 #ifdef DIRECTED_X_VARS
106 flow_capacity = cnrp->capacity;
107 #else
108 if (cnrp->par.prob_type == CSTP || cnrp->par.prob_type == CTP)
109 flow_capacity = cnrp->capacity;
110 else
111 flow_capacity = cnrp->capacity/2;
112 #endif
113 #endif
114
115 #ifdef ADD_CAP_CUTS
116 cnrp->basecutnum = (2 + od_const)*vertnum - 1 + 2*total_edgenum;
117 #elif defined(ADD_FLOW_VARS)
118 cnrp->basecutnum = (2 + od_const)*vertnum - 1;
119 #else
120 cnrp->basecutnum = (1 + od_const)*vertnum;
121 #endif
122 #ifdef ADD_X_CUTS
123 cnrp->basecutnum += total_edgenum;
124 #endif
125 #if defined(FIND_NONDOMINATED_SOLUTIONS) && 0
126 cnrp->basecutnum += 2; /* Need two extra constraints */
127 #endif
128
129 switch(cnrp->par.base_variable_selection){
130 case SOME_ARE_BASE:
131 if (cnrp->par.add_all_edges == FALSE){
132 /*If we are not adding all the edges, then really EVERYTHING_IS_BASE*/
133 cnrp->par.base_variable_selection = EVERYTHING_IS_BASE;
134 }else{ /*Otherwise, all we need to do is set this and then fall
135 through -- the remaining edges get added later */
136 cnrp->par.add_all_edges = FALSE;
137 }
138
139 case EVERYTHING_IS_BASE:
140 cnrp->basevars = create_edge_list(cnrp, &base_varnum, CHEAP_EDGES);
141 #ifdef FIND_NONDOMINATED_SOLUTIONS
142 cnrp->basevars = (int *) realloc((char *)cnrp->basevars,
143 (base_varnum + 1) * ISIZE);
144 cnrp->basevarnum = base_varnum + 1; /* Need one extra variable */
145 #ifdef ADD_FLOW_VARS
146 cnrp->basevars[base_varnum] = d_x_vars ? 4*total_edgenum:3*total_edgenum;
147 #else
148 cnrp->basevars[base_varnum] = d_x_vars ? total_edgenum:2*total_edgenum;
149 #endif
150 #else
151 cnrp->basevars = (int *) realloc((char *)cnrp->basevars,
152 base_varnum * ISIZE);
153 cnrp->basevarnum = base_varnum;
154 #endif
155 break;
156
157 case EVERYTHING_IS_EXTRA:
158 cnrp->basevarnum = 0;
159 break;
160 }
161
162 #if 0
163 if (cnrp->par.prob_tpye == BPP){
164 for (i = 0; i < cnrp->basevarnum; i++){
165 cnrp->dist.cost[cnrp->basevars[i]] = 10;
166 }
167 }
168 #endif
169
170 /* The one additional edge allocated is for the extra variable when finding
171 nondominated solutions for multi-criteria problems */
172 edges = cnrp->edges = (int *) calloc (vertnum*(vertnum-1) + 2, sizeof(int));
173
174 /* Create the edge list (we assume a complete graph) The edge is set to
175 (0,0) in the edge list if it was eliminated in preprocessing*/
176 /* For now, we cannot preprocess anything out because SYMPHONY assumes all
177 variables are present */
178 zero_varnum = cnrp->zero_varnum;
179 zero_vars = cnrp->zero_vars;
180 for (i = 1, k = 0, l = 0; i < vertnum; i++){
181 for (j = 0; j < i; j++){
182 #if 0
183 if (l < zero_varnum && k == zero_vars[l]){
184 /*This is one of the zero edges*/
185 edges[2*k] = edges[2*k+1] = 0;
186 l++;
187 k++;
188 continue;
189 }
190 #endif
191 edges[2*k] = j;
192 edges[2*k+1] = i;
193 k++;
194 }
195 }
196 edges[vertnum*(vertnum-1)] = edges[vertnum*(vertnum-1) + 1] = 0;
197
198 switch(cnrp->par.base_variable_selection){
199 case EVERYTHING_IS_EXTRA:
200
201 cnrp->extravars = create_edge_list(cnrp, &cnrp->extravarnum,
202 CHEAP_EDGES);
203 #if defined(FIND_NONDOMINATED_SOLUTIONS) && 0
204 cnrp->extravars = cnrp->extravars + 1;
205 #endif
206
207 break;
208
209 case SOME_ARE_BASE:
210
211 cnrp->par.add_all_edges = TRUE; /*We turned this off in user_set_base()
212 -- now we need to turn it back on*/
213
214 cnrp->extravars = create_edge_list(cnrp, &cnrp->extravarnum,
215 REMAINING_EDGES);
216
217 break;
218
219 case EVERYTHING_IS_BASE:
220
221 break;
222 }
223 }
224
225 /*===========================================================================*/
226
227 int *create_edge_list(cnrp_problem *cnrp, int *varnum, char which_edges)
228 {
229 int i, j, k;
230 int zero_varnum, edgenum, new_ind;
231 int *zero_vars, *uind = NULL;
232 int total_edgenum = cnrp->vertnum*(cnrp->vertnum-1)/2;
233 #ifdef DIRECTED_X_VARS
234 char d_x_vars = TRUE;
235 #else
236 char d_x_vars = FALSE;
237 #endif
238
239 /*DIFF: This routine has to be modified to include the flow variables*/
240
241 switch(which_edges){
242 case CHEAP_EDGES:
243
244 cnrp->zero_vars = zero_vars = (int *) calloc(total_edgenum, sizeof(int));
245
246 /*first determine which variables can be fixed to zero permanently*/
247 for (zero_varnum=0, i=2; i<cnrp->vertnum; i++){
248 for (j=1; j<i; j++){
249 if (cnrp->demand[i] + cnrp->demand[j] > cnrp->capacity){
250 zero_vars[zero_varnum++] = INDEX(i,j);
251 }
252 }
253 }
254
255 edgenum = cnrp->par.add_all_edges ?
256 cnrp->vertnum*(cnrp->vertnum-1)/2 : cnrp->g->edgenum;
257
258 /*First, we construct the index lists*/
259 #ifdef ADD_FLOW_VARS
260 uind = (int *) malloc((3+d_x_vars) * edgenum * ISIZE);
261 #else
262 uind = (int *) malloc((1+d_x_vars) * edgenum * ISIZE);
263 #endif
264
265 *varnum = 0;
266 switch(cnrp->par.add_all_edges){
267 case FALSE:
268 for (i = 0, j = 0; i<edgenum && j<zero_varnum; i++){
269 new_ind = INDEX(cnrp->g->edges[i].v0, cnrp->g->edges[i].v1);
270 if (new_ind < zero_vars[j]){
271 uind[(*varnum)++] = new_ind; /*edge var*/
272 #ifdef DIRECTED_X_VARS
273 uind[(*varnum)++] = total_edgenum + new_ind; /*edge var*/
274 #endif
275 #ifdef ADD_FLOW_VARS
276 /*flow var*/
277 uind[(*varnum)++] = (1+d_x_vars)*total_edgenum + new_ind;
278 /*flow var*/
279 uind[(*varnum)++] = (2+d_x_vars)*total_edgenum + new_ind;
280 #endif
281 }else{
282 while (j < zero_varnum && new_ind > zero_vars[j])
283 j++;
284 if (j == zero_varnum){
285 uind[(*varnum)++] = new_ind; /*edge var*/
286 #ifdef DIRECTED_X_VARS
287 uind[(*varnum)++] = total_edgenum + new_ind; /*edge var*/
288 #endif
289 #ifdef ADD_FLOW_VARS
290 /*flow var*/
291 uind[(*varnum)++] = (1+d_x_vars)*total_edgenum + new_ind;
292 /*flow var*/
293 uind[(*varnum)++] = (2+d_x_vars)*total_edgenum + new_ind;
294 #endif
295 }else if (new_ind < zero_vars[j]){
296 uind[(*varnum)++] = new_ind; /*edge var*/
297 #ifdef DIRECTED_X_VARS
298 uind[(*varnum)++] = total_edgenum + new_ind; /*edge var*/
299 #endif
300 #ifdef ADD_FLOW_VARS
301 /*flow var*/
302 uind[(*varnum)++] = (1+d_x_vars)*total_edgenum + new_ind;
303 /*flow var*/
304 uind[(*varnum)++] = (2+d_x_vars)*total_edgenum + new_ind;
305 #endif
306 }else
307 j++;
308 }
309 }
310 /*Now we have exhausted all the zero edges*/
311 for (; i<edgenum; i++){
312 uind[(*varnum)++] =
313 INDEX(cnrp->g->edges[i].v0, cnrp->g->edges[i].v1);
314 #ifdef DIRECTED_X_VARS
315 uind[(*varnum)++] =
316 total_edgenum +
317 INDEX(cnrp->g->edges[i].v0, cnrp->g->edges[i].v1);
318 #endif
319 #ifdef ADD_FLOW_VARS
320 uind[(*varnum)++] =
321 (1+d_x_vars)*total_edgenum+INDEX(cnrp->g->edges[i].v0,
322 cnrp->g->edges[i].v1);
323 uind[(*varnum)++] =
324 (2+d_x_vars)*total_edgenum+INDEX(cnrp->g->edges[i].v0,
325 cnrp->g->edges[i].v1);
326 #endif
327 }
328 break;
329 case TRUE:
330 for (i = 0, j = 0; j<zero_varnum; i++){
331 if (zero_vars[j] == i){
332 j++;
333 continue;
334 }
335 uind[(*varnum)++] = i; /*edge variable*/
336 #ifdef DIRECTED_X_VARS
337 uind[(*varnum)++] = total_edgenum + i; /*edge variable*/
338 #endif
339 #ifdef ADD_FLOW_VARS
340 /*flow var*/
341 uind[(*varnum)++] = (1+d_x_vars)*total_edgenum + i;
342 /*flow var*/
343 uind[(*varnum)++] = (2+d_x_vars)*total_edgenum + i;
344 #endif
345 }/*Now, we have exhausted all the zero edges*/
346 for (; i < edgenum; i++){
347 uind[(*varnum)++] = i; /*edge variable*/
348 #ifdef DIRECTED_X_VARS
349 uind[(*varnum)++] = total_edgenum + i; /*edge variable*/
350 #endif
351 #ifdef ADD_FLOW_VARS
352 /*flow var*/
353 uind[(*varnum)++] = (1+d_x_vars)*total_edgenum + i;
354 /*flow var*/
355 uind[(*varnum)++] = (2+d_x_vars)*total_edgenum + i;
356 #endif
357 }
358 break;
359 }
360
361 if (cnrp->par.verbosity > 0)
362 printf("Fixed %i edges in root creation\n\n", zero_varnum);
363
364 cnrp->zero_varnum = zero_varnum;
365
366 break;
367
368 case REMAINING_EDGES:
369
370 /*In this case, we are adding all variables at the root, but the small
371 graph edges are base and the rest are extra*/
372
373 zero_varnum = cnrp->zero_varnum;
374 zero_vars = cnrp->zero_vars;
375 edgenum = cnrp->g->edgenum;
376
377 #ifdef ADD_FLOW_VARS
378 uind = (int *) malloc((3 + d_x_vars) *
379 (total_edgenum-edgenum+cnrp->vertnum -1)* ISIZE);
380 #else
381 uind = (int *) malloc((1 + d_x_vars) *
382 (total_edgenum-edgenum+cnrp->vertnum-1) * ISIZE);
383 #endif
384 *varnum = 0;
385 for (i = 0, j = 0, k = 0; i < edgenum; i++, k++){
386 /*In this loop, we check each edge to se if it is in the small
387 graph and whether it is a zero edge*/
388 new_ind = INDEX(cnrp->g->edges[i].v0, cnrp->g->edges[i].v1);
389 for (; k < new_ind; k++){
390 if ((j < zero_varnum && k < zero_vars[j]) || j >= zero_varnum){
391 uind[(*varnum)++] = k; /*edge variable*/
392 #ifdef DIRECTED_X_VARS
393 uind[(*varnum)++] = total_edgenum + k; /*edge variable*/
394 #endif
395 #ifdef ADD_FLOW_VARS
396 /*flow var*/
397 uind[(*varnum)++] = (1+d_x_vars)*total_edgenum + k;
398 /*flow var*/
399 uind[(*varnum)++] = (2+d_x_vars)*total_edgenum + k;
400 #endif
401 }else{ /*curent edge is a zero edge so don't add it*/
402 j++;
403 }
404 }
405 /*k == new_ind here so we don't want to add that edge */
406 }
407 /*Now, we have exhausted the small graph so just add all non-zero
408 edges*/
409 for (; k < total_edgenum && j < zero_varnum; k++)
410 if (k < zero_vars[j]){
411 uind[(*varnum)++] = k; /*edge variable*/
412 #ifdef DIRECTED_X_VARS
413 uind[(*varnum)++] = total_edgenum + k; /*edge variable*/
414 #endif
415 #ifdef ADD_FLOW_VARS
416 /*flow var*/
417 uind[(*varnum)++] = (1+d_x_vars)*total_edgenum + k;
418 /*flow var*/
419 uind[(*varnum)++] = (2+d_x_vars)*total_edgenum + k;
420 #endif
421 }else{
422 j++;
423 }
424 /* Now, there are no more non-zero edges either so add the rest*/
425 for (; k < total_edgenum; k++){
426 uind[(*varnum)++] = k; /*edge variable*/
427 #ifdef DIRECTED_X_VARS
428 uind[(*varnum)++] = total_edgenum + k; /*edge variable*/
429 #endif
430 #ifdef ADD_FLOW_VARS
431 /*flow var*/
432 uind[(*varnum)++] = (1+d_x_vars)*total_edgenum + k;
433 /*flow var*/
434 uind[(*varnum)++] = (2+d_x_vars)*total_edgenum + k;
435 #endif
436 }
437 break;
438 }
439 qsort_i(uind, *varnum);
440
441 return(uind);
442 }