Debian Codegraph @

SYMPHONY/Applications/VRP/src/Master/Heuristics/lower_bound.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 #include <memory.h>
18 #include <stdio.h>
19 #include <stdlib.h>
20
21 #include "BB_macros.h"
22 #include "lower_bound.h"
23 #include "vrp_master_functions.h"
24 #include "vrp_const.h"
25 #include "sym_proccomm.h"
26
27 /*===========================================================================*/
28
29 static int intcompar(const void *int1, const void *int2)
30 {
31 return(*((int *)int2) - *((int *)int1));
32 }
33
34 /*===========================================================================*/
35
36 static int sum(int *array, int lower_lim, int upper_lim)
37 {
38 int i, sum;
39
40 for (sum = 0, i=lower_lim; i<= upper_lim; i++)
41 sum += array[i];
42
43 return(sum);
44 }
45
46 /*===========================================================================*/
47
48 void lower_bound(vrp_problem *vrp, lb_params *lb_par, heurs *lh,
49 int ub, int jobs, int *tids, int *sent)
50 {
51 int s_bufid, dummy;
52 int y, i, alpha, interval;
53 int *sorted_demand, trials;
54 int m1, numroutes = vrp->numroutes, capacity = vrp->capacity;
55
56 if (!lb_par->lower_bound)
57 return;
58
59 if (vrp->par.verbosity > 1)
60 printf("\nNow beginning lower bounding ....\n\n");
61
62 /*Calculate m1 = maximum # of single vehicle routes*/
63
64 sorted_demand = (int *) calloc (vrp->vertnum, sizeof(int));
65
66 memcpy (sorted_demand, vrp->demand, vrp->vertnum*sizeof(int));
67 qsort (sorted_demand+1, vrp->vertnum-1, sizeof(int), intcompar);
68
69 for (m1 = 0;; m1++)
70 if (!(capacity*(numroutes-m1-1) >=
71 sum(sorted_demand, m1+2, vrp->vertnum-1)))
72 break;
73
74 trials = (lb_par->lower_bound)*(numroutes-m1);
75
76 lh->tids = tids;
77
78 lh->jobs = jobs;
79
80 if (!jobs){
81 fprintf(stderr, "\nNo jobs started .... \n\n");
82 return;
83 }
84
85 else if (vrp->par.verbosity >2)
86 printf("\n%i jobs started ...\n\n", jobs);
87
88 /*-----------------------------------------------------------------------*\
89 | Broadcast data to the lower bounding procedure |
90 \*-----------------------------------------------------------------------*/
91 for(i=0; i<trials; i++){
92 s_bufid = init_send(DataInPlace);
93 send_int_array(&dummy, 1);
94 send_msg(tids[i%jobs], MST);
95 sent[i%jobs]++;
96 broadcast(vrp, tids+(i%jobs), 1);
97
98 s_bufid = init_send(DataInPlace);
99 send_int_array(&numroutes, 1);
100 send_int_array(&ub, 1);
101 send_int_array(&lb_par->lb_max_iter, 1);
102 send_int_array(&m1, 1);
103 send_msg(tids[i%jobs], VRP_LB_DATA);
104 }
105 interval = lb_par->lb_penalty_mult/lb_par->lower_bound;
106
107 for (i=trials-1, y = m1, alpha = lb_par->lb_penalty_mult; i>=0; i--, y++){
108 s_bufid = init_send(DataInPlace);
109 send_int_array(&y, 1);
110 send_int_array(&alpha, 1);
111 send_msg(tids[i%jobs], VRP_LB_DATA2);
112 if (y == numroutes){
113 y = m1-1;
114 alpha -= interval;
115 }
116 }
117
118 freebuf(s_bufid);
119 FREE(sorted_demand);
120 }
121
122
123