| 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 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> |
| 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 |
} |