Debian Codegraph @

SYMPHONY/Applications/VRP/src/CutGen/shrink.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 /* */
9 /* This file was jointly authored by Ted Ralphs and Leonid Kopman. */
10 /* */
11 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */
12 /* */
13 /* This software is licensed under the Eclipse Public License. Please see */
14 /* accompanying file for terms. */
15 /* */
16 /*===========================================================================*/
17
18 /* system include files */
19 #include <stdlib.h>
20 #include <math.h>
21 #include <string.h> /* memset() is defined here in LINUX */
22
23 /* SYMPHONY include files */
24 #include "sym_constants.h"
25 #include "sym_macros.h"
26 #include "sym_messages.h"
27 #include "sym_proccomm.h"
28 #include "sym_cg.h"
29
30 /* VRP include files */
31 #include "vrp_cg.h"
32 #include "vrp_macros.h"
33 #include "network.h"
34
35 /*__BEGIN_EXPERIMENTAL_SECTION__*/
36 #if 0
37 #include "util.h"
38 extern CCrandstate rand_state;
39 #endif
40 /*___END_EXPERIMENTAL_SECTION___*/
41
42 /*===========================================================================*/
43
44 /*===========================================================================*\
45 * This file implements the greedy shrinking algorithm of Augerat, et al.
46 * The implementation was done by Leonid Kopman.
47 \*===========================================================================*/
48
49 void reduce_graph(network *n, double etol, int *demand)
50 {
51 elist *e1, *e2, *e3;
52 edge *cur_edge;
53 int v1, v2, deg, count, i, k;
54 edge *edges = n->edges;
55 int num_edges = n->edgenum;
56 int edges_deleted = 0;
57 vertex *verts = n->verts;
58 vertex *v2_pt, *third_node;
59
60 while(TRUE){
61 num_edges = n->edgenum;
62 edges_deleted = 0;
63 for (i = 0; i < num_edges; i++){
64 cur_edge = edges + i;
65 if (cur_edge->weight >= 1 - etol && cur_edge->v0 &&
66 cur_edge->v1 && !(cur_edge->deleted)){
67 cur_edge->deleted = TRUE;
68 n->edgenum--;
69 edges_deleted++;
70 v1 = (verts[cur_edge->v0].degree ==
71 MIN(verts[cur_edge->v0].degree, verts[cur_edge->v1].degree))?
72 cur_edge->v0 : cur_edge->v1;
73 v2 = (v1 == cur_edge->v0) ? cur_edge->v1 : cur_edge->v0;
74 verts[v1].deleted = TRUE;
75 demand[v2] += demand[v1];
76 demand[v1] = 0;
77 v2_pt = verts + v2;
78 v2_pt->degree--;
79 if (v2_pt->first->other_end == v1){
80 v2_pt->first = v2_pt->first->next_edge;
81 }else{
82 for (e3 = v2_pt->first; e3 && e3->next_edge; e3 = e3->next_edge)
83 if (e3->next_edge->other_end == v1){
84 e3->next_edge = e3->next_edge->next_edge;
85 if (e3->next_edge == NULL) v2_pt->last = e3;
86 break;
87 }
88 }
89
90 if (!(v2_pt->orig_node_list_size))
91 v2_pt->orig_node_list = (int *) malloc(n->vertnum*ISIZE);
92 (v2_pt->orig_node_list)[(v2_pt->orig_node_list_size)++] = v1;
93
94 for (k = 0; k < verts[v1].orig_node_list_size; k++){
95 (v2_pt->orig_node_list)[(v2_pt->orig_node_list_size)++] =
96 (verts[v1].orig_node_list)[k];
97 }
98 deg = verts[v1].degree;
99
100 for (e1 = verts[v1].first, count=0; e1 && (count < deg); count++ ){
101 third_node = e1->other;
102 if (third_node->orignodenum == v2){
103 e1 = e1->next_edge;
104 continue;
105 }
106 for (e2 = v2_pt->first; e2; e2 = e2->next_edge){
107 if (e2->other_end == e1->other_end ){
108 e2->data->weight += e1->data->weight;
109 e1->data->deleted = TRUE;
110 edges_deleted++;
111 (third_node->degree)--;
112 if (third_node->first->other_end == v1){
113 third_node->first=third_node->first->next_edge;
114 }else{
115 for (e3 = third_node->first; e3 && e3->next_edge;
116 e3 = e3->next_edge)
117 if (e3->next_edge->other_end == v1){
118 e3->next_edge = e3->next_edge->next_edge;
119 if (e3->next_edge == NULL) third_node->last = e3;
120 break;
121 }
122 }
123 break;
124 }
125 }
126 if (e2){
127 e1 = e1->next_edge;
128 continue;
129 }
130 /* ok, so e1->other_node is not incident to v2 */
131 for (e3 = third_node->first; e3 ; e3 = e3->next_edge){
132 if (e3->other_end == v1){
133 e3->other = v2_pt;
134 e3->other_end = v2;
135 e3->data->v0 = MIN(v2, third_node->orignodenum);
136 e3->data->v1 = MAX(v2, third_node->orignodenum);
137 break;
138 }
139 }
140 v2_pt->last->next_edge = e1;
141 v2_pt->last = e1;
142 v2_pt->degree++;
143 e1=e1->next_edge;
144 v2_pt->last->next_edge = NULL;
145 }
146 }
147 }
148 if (!edges_deleted) break;
149 }
150 }
151
152 /*===========================================================================*/
153
154 int greedy_shrinking1(network *n, double truck_cap, double etol,
155 int max_shrink_cuts, cut_data *new_cut,
156 int *compnodes, int *compmembers, int compnum,
157 char *in_set, double *cut_val, int *ref, char *cut_list,
158 int *demand, cut_data ***cuts, int *num_cuts,
159 int *alloc_cuts)
160 {
161 double set_cut_val, set_demand;
162 vertex *verts = n->verts;
163 elist *e;
164 int shrink_cuts = 0, i, j, k;
165 char *pt, *cutpt;
166 int *ipt;
167 double *dpt;
168 int vertnum = n->vertnum;
169
170 int max_vert = 0, set_size, begin = 1, cur_comp, end = 1, other_end;
171 char *coef;
172 double maxval, weight;
173 vertex *cur_nodept;
174
175 new_cut->size = (vertnum >> DELETE_POWER) + 1;
176 new_cut->coef = coef = (char *) (calloc(new_cut->size, sizeof(char)));
177 memset(cut_list, 0, new_cut->size * (max_shrink_cuts + 1));
178
179 *in_set = 0;
180
181 for (i = 1; i < vertnum; i++){
182 if (verts[compmembers[i]].deleted) compmembers[i] = 0;
183 ref[compmembers[i]] = i;
184 }
185 *ref = 0;
186 /* ref is a reference array for compmembers: gives a place
187 in which a vertex is listed in compmembers */
188
189 for (cur_comp = 1; cur_comp <= compnum;
190 begin += compnodes[cur_comp], cur_comp++) /* for every component */
191 for (i = begin, end = begin + compnodes[cur_comp]; i < end; i++){
192 if (compmembers[i] == 0) continue;
193 /* for every node as a starting one */
194 /*initialize the data structures */
195 memset(in_set + begin, 0, compnodes[cur_comp] * sizeof(char));
196 memset(cut_val + begin, 0, compnodes[cur_comp] * sizeof(double));
197 in_set[i] = 1;
198 set_size = 1 + verts[compmembers[i]].orig_node_list_size;
199 set_cut_val = 0;
200 for (e = verts[compmembers[i]].first; e; e = e->next_edge){
201 if (e->other_end)
202 cut_val[ref[e->other_end]] = e->data->weight;
203 set_cut_val += e->data->weight;
204 }
205 set_demand = demand[compmembers[i]];
206
207 while(TRUE){
208 if (set_cut_val < 2*(ceil(set_demand/truck_cap)) - etol &&
209 set_size > 2){
210 memset(coef, 0, new_cut->size*sizeof(char));
211 for (j = begin, ipt = compmembers + begin; j < end; j++, ipt++){
212 if (in_set[j]){
213 cur_nodept = verts + (*ipt);
214 if (cur_nodept->orig_node_list_size)
215 for (k = 0; k < cur_nodept->orig_node_list_size; k++)
216 (coef[(cur_nodept->orig_node_list)[k] >>
217 DELETE_POWER]) |=
218 (1 << ((cur_nodept->orig_node_list)[k] &
219 DELETE_AND));
220 (coef[(*ipt) >> DELETE_POWER]) |=
221 (1 << ((*ipt) & DELETE_AND));
222 }
223 }
224 new_cut->type = (set_size < vertnum/2 ?
225 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
226 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
227 RHS((int)set_size,(int)set_demand,
228 (int)truck_cap):
229 2*BINS((int)set_demand, (int)truck_cap));
230 for (k = 0, cutpt = cut_list; k < shrink_cuts; k++,
231 cutpt += new_cut->size)
232 if (!memcmp(coef, cutpt, new_cut->size*sizeof(char)))
233 break;/* same cuts */
234 if (k >= shrink_cuts){
235 shrink_cuts +=
236 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
237 memcpy(cutpt, coef, new_cut->size);
238 }
239 if (shrink_cuts > max_shrink_cuts){
240 FREE(new_cut->coef);
241 return(shrink_cuts);
242 }
243 }
244 for (maxval = -1, pt = in_set + begin, dpt = cut_val + begin,
245 j = begin; j < end; pt++, dpt++, j++){
246 if (!(*pt) && *dpt > maxval){
247 maxval = cut_val[j];
248 max_vert = j;
249 }
250 }
251 if (maxval > 0){ /* add the vertex to the set */
252 in_set[max_vert]=1;
253 set_size += 1+ verts[compmembers[max_vert]].orig_node_list_size;
254 set_demand += demand[compmembers[max_vert]];
255 cut_val[max_vert] = 0;
256 for (e=verts[compmembers[max_vert]].first; e; e = e->next_edge){
257 other_end = ref[e->other_end];
258 weight = e->data->weight;
259 set_cut_val += (in_set[other_end]) ? (-weight):weight;
260 cut_val[other_end] += (in_set[other_end]) ? 0 : weight;
261
262 }
263 }
264 else{ /* can't add anything to the set */
265 break;
266 }
267 }
268 }
269 FREE(new_cut->coef);
270 return(shrink_cuts);
271 }
272
273 /*===========================================================================*/
274
275 int greedy_shrinking6(network *n, double truck_cap, double etol,
276 cut_data *new_cut, int *compnodes,
277 int *compmembers, int compnum,char *in_set,
278 double *cut_val, int *ref, char *cut_list,
279 int max_shrink_cuts, int *demand, int trial_num,
280 double prob, cut_data ***cuts, int *num_cuts,
281 int *alloc_cuts)
282 {
283 double set_cut_val, set_demand;
284 vertex *verts = n->verts;
285 elist *e;
286 int i, j, k, shrink_cuts = 0;
287 char *pt, *cutpt;
288 double *dpt;
289 int vertnum = n->vertnum;
290
291 int max_vert = 0, set_size, begin = 1, cur_comp, end = 1, num_trials;
292 char *coef;
293 double maxval;
294 double denominator=pow(2.0,31.0)-1.0;
295 double r, q;
296
297 int other_end;
298 double weight;
299 int *ipt;
300 vertex *cur_nodept;
301
302 new_cut->size = (vertnum >> DELETE_POWER) + 1;
303 new_cut->coef =coef= (char *) (calloc(new_cut->size,sizeof(char)));
304 memset(cut_list, 0, new_cut->size * (max_shrink_cuts +1));
305
306
307 *in_set=0;
308
309 for(i = 1; i < vertnum; i++){
310 if (verts[compmembers[i]].deleted) compmembers[i] = 0;
311 ref[compmembers[i]] = i;
312 }
313 *ref = 0;
314
315 /* ref is a reference array for compmembers: gives a place
316 in which a vertex is listed in compmembers */
317
318 for (cur_comp = 1; cur_comp <= compnum; begin += compnodes[cur_comp],
319 cur_comp++){
320 /* for every component */
321 if (compnodes[cur_comp] <= 7) continue;
322
323 for (num_trials = 0; num_trials < trial_num * compnodes[cur_comp];
324 num_trials++){
325 end = begin + compnodes[cur_comp];
326 /*initialize the data structures */
327 memset(in_set + begin, 0, compnodes[cur_comp] * sizeof(char));
328 memset(cut_val+ begin, 0, compnodes[cur_comp] * sizeof(double));
329
330 set_cut_val = 0;
331 set_size = 0;
332 set_demand = 0;
333 for (i = begin; i < end; i++ ){
334 if (compmembers[i] == 0) continue;
335 /*__BEGIN_EXPERIMENTAL_SECTION__*/
336 #if 0
337 r = CCutil_lprand(&rand_state)/CC_PRANDMAX;
338 #endif
339 /*___END_EXPERIMENTAL_SECTION___*/
340 r = (RANDOM()/denominator);
341 q = (prob/compnodes[cur_comp]);
342 if (r < q){
343 in_set[i] = 1;
344 set_size += 1 + verts[compmembers[i]].orig_node_list_size;
345 set_demand += demand[compmembers[i]];
346 for (e = verts[compmembers[i]].first; e; e = e-> next_edge){
347 other_end = ref[e->other_end];
348 weight = e->data->weight;
349 set_cut_val += (in_set[other_end]) ? (-weight) : weight;
350 cut_val[other_end] += (in_set[other_end]) ? 0 : weight;
351 }
352 }
353 }
354 while(set_size){
355 if (set_cut_val < 2*(ceil(set_demand/truck_cap)) - etol &&
356 set_size > 2){
357 memset(coef, 0, new_cut->size*sizeof(char));
358 for (j = begin, ipt = compmembers + begin; j < end; j++, ipt++)
359 if (in_set[j]){
360 cur_nodept = verts + (*ipt);
361 if (cur_nodept->orig_node_list_size)
362 for (k = 0; k < cur_nodept->orig_node_list_size; k++)
363 (coef[(cur_nodept->orig_node_list)[k] >>
364 DELETE_POWER]) |=
365 (1 << ((cur_nodept->orig_node_list)[k] &
366 DELETE_AND));
367 (coef[(*ipt) >> DELETE_POWER]) |= (1 << ((*ipt) &
368 DELETE_AND));
369 }
370 new_cut->type = (set_size < vertnum/2 ?
371 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
372 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
373 RHS((int)set_size,(int)set_demand,(int)truck_cap):
374 2*BINS((int)set_demand, (int)truck_cap));
375 for (k = 0, cutpt = cut_list; k < shrink_cuts; k++,
376 cutpt += new_cut->size)
377 if (!memcmp(coef, cutpt, new_cut->size*sizeof(char))) break;
378 if ( k >= shrink_cuts){
379 shrink_cuts +=
380 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
381 memcpy(cutpt, coef, new_cut->size);
382 }
383
384 if ( shrink_cuts > max_shrink_cuts){
385 FREE(new_cut->coef);
386 return(shrink_cuts);
387 }
388 }
389 for (maxval = -1, pt = in_set+begin, dpt = cut_val+begin,
390 j = begin; j < end; pt++, dpt++, j++){
391 if (!(*pt) && *dpt > maxval){
392 maxval = cut_val[j];
393 max_vert = j;
394 }
395 }
396 if (maxval > 0){ /* add the vertex to the set */
397 in_set[max_vert]=1;
398 set_size+=1+ verts[compmembers[max_vert]].orig_node_list_size;
399 set_demand+=demand[compmembers[max_vert]];
400 cut_val[max_vert]=0;
401 for (e = verts[compmembers[max_vert]].first; e;
402 e = e->next_edge){
403 other_end = ref[e->other_end];
404 weight = e->data->weight;
405 set_cut_val += (in_set[other_end]) ? (-weight) : weight;
406 cut_val[other_end]+=(in_set[other_end]) ? 0 : weight;
407 }
408 }
409 else{ /* can't add anything to the set */
410 break;
411 }
412 }
413 }
414 }
415
416 FREE(new_cut->coef);
417 return(shrink_cuts);
418 }
419
420 /*===========================================================================*/
421
422 int greedy_shrinking1_one(network *n, double truck_cap, double etol,
423 int max_shrink_cuts, cut_data *new_cut,char *in_set,
424 double *cut_val, char *cut_list, int num_routes,
425 int *demand, cut_data ***cuts, int *num_cuts,
426 int *alloc_cuts)
427 {
428
429 double set_cut_val, set_demand;
430 vertex *verts = n->verts;
431 elist *e;
432 int i, j, k, shrink_cuts = 0;
433 char *pt, *cutpt;
434 double *dpt;
435 int vertnum = n->vertnum;
436 int max_vert = 0;
437 int set_size;
438 /* int flag=0; */
439
440 double complement_demand, total_demand = verts[0].demand;
441 double complement_cut_val;
442 int complement_size;
443 char *coef;
444 double maxval;
445 int other_end;
446 double weight;
447 vertex *cur_nodept;
448
449 new_cut->size = (vertnum >> DELETE_POWER) + 1;
450 new_cut->coef = coef = (char *) (calloc(new_cut->size,sizeof(char)));
451 memset(cut_list, 0, new_cut->size * (max_shrink_cuts + 1));
452
453 for (i = 1; i < vertnum; i++ ){
454 if (verts[i].deleted) continue;/* for every node as a starting one */
455 /*initialize the data structures */
456 memset(in_set, 0, vertnum*sizeof(char));
457 memset(cut_val, 0,vertnum* sizeof(double));
458 in_set[i] = 1;
459 set_size = 1 + verts[i].orig_node_list_size;
460 set_cut_val = 0;
461 for (e= verts[i].first; e; e = e-> next_edge){
462 weight = e->data->weight;
463 cut_val[e->other_end] = weight;
464 set_cut_val += weight;
465 }
466 set_demand = demand[i];
467
468 while(TRUE){
469 if (set_cut_val < 2*(ceil(set_demand/truck_cap)) - etol &&
470 set_size > 2){
471 memset(coef, 0, new_cut->size*sizeof(char));
472 /* printf("%d :", i); */
473 /* printf("%d ", j); */
474 for (j = 1; j < vertnum; j++)
475 if (in_set[j]){
476 cur_nodept = verts + j;
477 if (cur_nodept->orig_node_list_size)
478 for (k = 0; k < cur_nodept->orig_node_list_size; k++)
479 (coef[(cur_nodept->orig_node_list)[k] >>
480 DELETE_POWER]) |=
481 (1 << ((cur_nodept->orig_node_list)[k] &
482 DELETE_AND));
483 (coef[j>> DELETE_POWER]) |= (1 << ( j & DELETE_AND));
484 }
485 /* printf("%f ", set_demand);
486 printf("%f \n",set_cut_val);*/
487 new_cut->type = (set_size < vertnum/2 ?
488 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
489 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
490 RHS((int)set_size,(int)set_demand,(int)truck_cap):
491 2*BINS((int)set_demand,(int)truck_cap));
492 for (k = 0, cutpt = cut_list; k < shrink_cuts; k++,
493 cutpt += new_cut->size)
494 if (!memcmp(coef, cutpt, new_cut->size*sizeof(char)))
495 break; /* same cuts */
496 if ( k >= shrink_cuts){
497 shrink_cuts +=
498 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
499 memcpy(cutpt, coef, new_cut->size);
500 }
501
502 if ( shrink_cuts > max_shrink_cuts){
503 FREE(new_cut->coef);
504 return(shrink_cuts);
505 }
506 }
507 /* check the complement */
508
509 complement_demand = total_demand - set_demand;
510 complement_cut_val =set_cut_val- 2*(*cut_val) + 2*num_routes;
511 complement_size = vertnum - 1 - set_size;
512 if (complement_cut_val< 2*(ceil(complement_demand/truck_cap))-etol &&
513 complement_size > 2){
514 memset(coef, 0, new_cut->size*sizeof(char));
515 for (j = 1; j < vertnum; j++)
516 if (!(in_set[j]) && !(verts[j].deleted)){
517 cur_nodept = verts + j;
518 if (cur_nodept->orig_node_list_size)
519 for (k = 0; k < cur_nodept->orig_node_list_size; k++)
520 (coef[(cur_nodept->orig_node_list)[k] >>
521 DELETE_POWER]) |=
522 (1 << ((cur_nodept->orig_node_list)[k] &
523 DELETE_AND));
524 (coef[j>> DELETE_POWER]) |= (1 << ( j & DELETE_AND));
525 }
526 new_cut->type = (complement_size < vertnum/2 ?
527 SUBTOUR_ELIM_SIDE : SUBTOUR_ELIM_ACROSS);
528 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
529 RHS((int)complement_size,(int)complement_demand,
530 (int)truck_cap):
531 2*BINS((int)complement_demand,(int)truck_cap));
532 for (k=0, cutpt = cut_list; k < shrink_cuts; k++,
533 cutpt += new_cut->size)
534 if (!memcmp(coef, cutpt, new_cut->size*sizeof(char))) break;
535 if ( k >= shrink_cuts){
536 shrink_cuts +=
537 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
538 memcpy(cutpt, coef, new_cut->size);
539 }
540
541 if (shrink_cuts > max_shrink_cuts){
542 FREE(new_cut->coef);
543 return(shrink_cuts);
544 }
545 }
546
547 for (maxval = -1, pt = in_set, dpt = cut_val,pt++, dpt++,
548 j = 1; j < vertnum; pt++, dpt++, j++){
549 if (!(*pt) && *dpt > maxval){
550 maxval = cut_val[j];
551 max_vert = j;
552 }
553 }
554 if (maxval > 0){ /* add the vertex to the set */
555 in_set[max_vert] = 1;
556 set_size += 1 + verts[max_vert].orig_node_list_size ;
557 set_demand += demand[max_vert];
558 cut_val[max_vert] = 0;
559 for (e = verts[max_vert].first; e; e = e-> next_edge){
560 other_end = e->other_end;
561 weight = e->data->weight;
562 set_cut_val += (in_set[other_end]) ? (-weight): weight;
563 cut_val[other_end] += weight;
564
565 }
566 }
567 else{ /* can't add anything to the set */
568 break;
569 }
570 }
571 }
572 FREE(new_cut->coef);
573 return(shrink_cuts);
574 }
575
576 /*===========================================================================*/
577
578 int greedy_shrinking6_one(network *n, double truck_cap,
579 double etol, cut_data *new_cut,
580 char *in_set, double *cut_val, int num_routes,
581 char *cut_list, int max_shrink_cuts, int *demand,
582 int trial_num, double prob, cut_data ***cuts,
583 int *num_cuts, int *alloc_cuts)
584 {
585
586 double set_cut_val, set_demand;
587 vertex *verts=n->verts;
588 elist *e;
589 int i, j, k, shrink_cuts = 0;
590 char *pt, *cutpt;
591 double *dpt;
592 int vertnum = n->vertnum;
593
594 int max_vert = 0, set_size, begin = 1, end = 1, num_trials;
595 char *coef;
596 double maxval, r, q;
597 double denominator = pow(2.0, 31.0) - 1.0;
598
599 int other_end;
600 double weight;
601
602 double complement_demand, total_demand = verts[0].demand;
603 double complement_cut_val;
604 int complement_size;
605 vertex *cur_nodept;
606 /* int flag=0;*/
607
608 new_cut->size = (vertnum >> DELETE_POWER) + 1;
609 new_cut->coef = coef = (char *) (calloc(new_cut->size,sizeof(char)));
610 memset(cut_list, 0, new_cut->size * (max_shrink_cuts +1));
611
612 *in_set = 0;
613
614 for (num_trials = 0; num_trials < trial_num*vertnum ; num_trials++){
615
616 /*initialize the data structures */
617 memset(in_set, 0, vertnum*sizeof(char));
618 memset(cut_val, 0,vertnum* sizeof(double));
619
620 set_cut_val = 0;
621 set_size = 0;
622 set_demand = 0;
623 for (i = 1 ; i < vertnum; i++ ){
624 if (verts[i].deleted) continue;
625 r = (RANDOM()/denominator);
626 q = (prob/vertnum);
627 if (r < q){
628 in_set[i] = 1;
629 set_size += 1 + verts[i].orig_node_list_size;
630 set_demand += demand[i];
631 for (e = verts[i].first; e; e = e-> next_edge){
632 other_end = e->other_end;
633 weight = e->data->weight;
634 set_cut_val += (in_set[other_end]) ? (-weight) : weight;
635 cut_val[other_end] += (in_set[other_end]) ? 0 : weight;
636 }
637 }
638 }
639 while(set_size){
640 if (set_cut_val < 2*(ceil(set_demand/truck_cap)) - etol &&
641 set_size > 2){
642 memset(coef, 0, new_cut->size*sizeof(char));
643 for (j = 1; j < vertnum; j++ )
644 if (in_set[j]){
645 cur_nodept = verts + j;
646 if (cur_nodept->orig_node_list_size)
647 for (k = 0; k < cur_nodept->orig_node_list_size; k++)
648 (coef[(cur_nodept->orig_node_list)[k] >>
649 DELETE_POWER]) |=
650 (1 << ((cur_nodept->orig_node_list)[k] &
651 DELETE_AND));
652 (coef[j>> DELETE_POWER]) |= (1 << ( j & DELETE_AND));
653 }
654 new_cut->type = (set_size < vertnum/2 ?
655 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
656 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
657 RHS((int)set_size, (int)set_demand, (int)truck_cap):
658 2*BINS((int)set_demand, (int)truck_cap));
659 for (k = 0, cutpt = cut_list; k < shrink_cuts; k++,
660 cutpt += new_cut->size)
661 if (!memcmp(coef, cutpt, new_cut->size*sizeof(char))) break;
662 if ( k >= shrink_cuts){
663 shrink_cuts +=
664 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
665 memcpy(cutpt, coef, new_cut->size);
666 }
667 if (shrink_cuts > max_shrink_cuts){
668 FREE(new_cut->coef);
669 return(shrink_cuts);
670 }
671 }
672
673 /* check the complement */
674
675 complement_demand = total_demand - set_demand;
676 complement_cut_val = set_cut_val - 2*(*cut_val) + 2*num_routes;
677 complement_size = vertnum - 1 - set_size;
678 if (complement_cut_val< 2*(ceil(complement_demand/truck_cap))-etol &&
679 complement_size > 2){
680 memset(coef, 0, new_cut->size*sizeof(char));
681 for (j = 1; j < vertnum; j++)
682 if (!(in_set[j])&& !(verts[j].deleted)){
683 cur_nodept = verts + j;
684 if (cur_nodept->orig_node_list_size)
685 for (k = 0; k < cur_nodept->orig_node_list_size; k++)
686 (coef[(cur_nodept->orig_node_list)[k] >>
687 DELETE_POWER]) |=
688 (1 << ((cur_nodept->orig_node_list)[k] &
689 DELETE_AND));
690 (coef[j>> DELETE_POWER]) |= (1 << ( j & DELETE_AND));
691 }
692 new_cut->type = (complement_size < vertnum/2 ?
693 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
694 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
695 RHS((int)complement_size,(int)complement_demand,
696 (int)truck_cap):
697 2*BINS((int)complement_demand,(int)truck_cap));
698 for (k = 0, cutpt = cut_list; k < shrink_cuts; k++,
699 cutpt += new_cut->size)
700 if (!memcmp(coef, cutpt, new_cut->size*sizeof(char))) break;
701 if ( k >= shrink_cuts){
702 shrink_cuts +=
703 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
704 memcpy(cutpt, coef, new_cut->size);
705 }
706
707 if (shrink_cuts > max_shrink_cuts){
708 FREE(new_cut->coef);
709 return(shrink_cuts);
710 }
711 }
712
713 for (maxval = -1, pt = in_set + begin, dpt = cut_val + begin,
714 j = begin; j < end; pt++, dpt++, j++){
715 if (!(*pt) && *dpt > maxval){
716 maxval = cut_val[j];
717 max_vert = j;
718 }
719 }
720 if (maxval > 0){ /* add the vertex to the set */
721 in_set[max_vert] = 1;
722 set_size += 1 + verts[max_vert].orig_node_list_size ;
723 set_demand += demand[max_vert];
724 cut_val[max_vert] = 0;
725 for (e = verts[max_vert].first; e; e = e-> next_edge){
726 other_end = e->other_end;
727 weight = e->data->weight;
728 set_cut_val += (in_set[other_end]) ? (-weight) : weight;
729 cut_val[other_end] += weight;
730 }
731 }
732 else{ /* can't add anything to the set */
733 break;
734 }
735 }
736 }
737
738 FREE(new_cut->coef);
739 return(shrink_cuts);
740 }
741
742 /*===========================================================================*/
743
744 int greedy_shrinking2_one(network *n, double truck_cap,
745 double etol, cut_data *new_cut,
746 char *in_set, double *cut_val, int num_routes,
747 int *demand, cut_data ***cuts, int *num_cuts,
748 int *alloc_cuts)
749 {
750
751 double set_cut_val, set_demand;
752 vertex *verts = n->verts;
753 elist *e, *cur_edge1, *cur_edge2;
754 int j, k, shrink_cuts = 0;
755 char *pt;
756 double *dpt;
757 int vertnum = n->vertnum;
758
759 int max_vert = 0, set_size, begin = 1, end = 1;
760 char *coef;
761 double maxval;
762
763 int other_end;
764 double weight;
765
766 double complement_demand, total_demand = verts[0].demand;
767 double complement_cut_val;
768 int complement_size;
769 vertex *cur_nodept;
770
771 new_cut->size = (vertnum >> DELETE_POWER) + 1;
772 new_cut->coef =coef= (char *) (calloc(new_cut->size,sizeof(char)));
773
774 *in_set=0;
775
776 for (cur_edge1 = verts[0].first; cur_edge1;
777 cur_edge1 = cur_edge1->next_edge){
778 for (cur_edge2 = cur_edge1->next_edge; cur_edge2;
779 cur_edge2 = cur_edge2->next_edge){
780
781 /*initialize the data structures */
782 memset(in_set, 0, vertnum*sizeof(char));
783 memset(cut_val, 0,vertnum* sizeof(double));
784
785 set_cut_val = 2;
786 set_size = 2 + cur_edge1->other->orig_node_list_size +
787 cur_edge2->other->orig_node_list_size;
788 set_demand = demand[cur_edge1->other_end] +
789 demand[cur_edge2->other_end];
790 in_set[cur_edge1->other_end] = 1;
791
792 for (e = verts[cur_edge1->other_end].first; e; e = e-> next_edge){
793 cut_val[e->other_end] += e->data->weight;
794 }
795
796 in_set[cur_edge2->other_end] = 1;
797 for (e = verts[cur_edge2->other_end].first; e; e = e-> next_edge){
798 other_end = e->other_end;
799 weight = e->data->weight;
800 set_cut_val += (in_set[other_end]) ? (-weight) : weight;
801 cut_val[other_end] += (in_set[other_end]) ? 0 : weight;
802 }
803 while(set_size){
804 if (set_cut_val < 2*(ceil(set_demand/truck_cap)) - etol &&
805 set_size > 2){
806 memset(coef, 0, new_cut->size*sizeof(char));
807 for (j = 1; j < vertnum; j++ )
808 if (in_set[j]){
809 cur_nodept = verts + j;
810 if (cur_nodept->orig_node_list_size)
811 for (k = 0; k < cur_nodept->orig_node_list_size; k++)
812 (coef[(cur_nodept->orig_node_list)[k] >>
813 DELETE_POWER]) |=
814 (1 << ((cur_nodept->orig_node_list)[k] &
815 DELETE_AND));
816 (coef[j >> DELETE_POWER]) |= (1 << (j & DELETE_AND));
817 }
818 new_cut->type = (set_size < vertnum/2 ?
819 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
820 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
821 RHS((int)set_size, (int)set_demand, (int)truck_cap):
822 2*BINS((int)set_demand, (int)truck_cap));
823 shrink_cuts +=
824 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
825 }
826
827 /* check the complement */
828
829 complement_demand = total_demand - set_demand;
830 complement_cut_val = set_cut_val - 2*(*cut_val) + 2*num_routes;
831 complement_size = vertnum - 1 - set_size;
832 if (complement_cut_val< 2*(ceil(complement_demand/truck_cap))-etol &&
833 complement_size > 2){
834 memset(coef, 0, new_cut->size*sizeof(char));
835 for (j = 1; j < vertnum; j++)
836 if (!in_set[j]){
837 cur_nodept=verts + j;
838 if (cur_nodept->orig_node_list_size)
839 for (k = 0; k < cur_nodept->orig_node_list_size; k++)
840 (coef[(cur_nodept->orig_node_list)[k] >>
841 DELETE_POWER]) |=
842 (1 << ((cur_nodept->orig_node_list)[k] &
843 DELETE_AND));
844 (coef[j>> DELETE_POWER]) |= (1 << ( j & DELETE_AND));
845 }
846 new_cut->type = (complement_size < vertnum/2 ?
847 SUBTOUR_ELIM_SIDE:SUBTOUR_ELIM_ACROSS);
848 new_cut->rhs = (new_cut->type == SUBTOUR_ELIM_SIDE ?
849 RHS((int)complement_size,(int)complement_demand,
850 (int)truck_cap):
851 2*BINS((int)complement_demand,(int)truck_cap));
852 shrink_cuts +=
853 cg_send_cut(new_cut, num_cuts, alloc_cuts, cuts);
854 }
855
856 for (maxval = -1, pt = in_set+begin, dpt = cut_val+begin,
857 j = begin; j < end; pt++, dpt++, j++){
858 if (!(*pt) && *dpt > maxval){
859 maxval = cut_val[j];
860 max_vert = j;
861 }
862 }
863 if (maxval > 0){ /* add the vertex to the set */
864 in_set[max_vert] = 1;
865 set_size += 1 + verts[max_vert].orig_node_list_size ;
866 set_demand += demand[max_vert];
867 cut_val[max_vert] = 0;
868 for (e = verts[max_vert].first; e; e = e-> next_edge){
869 other_end = e->other_end;
870 weight = e->data->weight;
871 set_cut_val += (in_set[other_end]) ? (-weight) : weight;
872 cut_val[other_end] += weight;
873 }
874 }
875 else{ /* can't add anything to the set */
876 break;
877 }
878 }
879 }
880 }
881 FREE(new_cut->coef);
882 return(shrink_cuts);
883 }