| 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 <math.h> |
| 18 |
#include <stddef.h> |
| 19 |
|
| 20 |
#include "sym_constants.h" |
| 21 |
#include "mst_ins_rout.h" |
| 22 |
#include "vrp_const.h" |
| 23 |
#include "compute_cost.h" |
| 24 |
#include <string.h> |
| 25 |
/*--------------------------------------------------------------------------*\ |
| 26 |
| This first routine creates a minimum k-degree-centre-tree based on the | |
| 27 |
| penalized costs. It first dreates a regular spanning tree and then either | |
| 28 |
| forces edges adjacent to the depot either in or out in order to make the | |
| 29 |
| degree of the depot correct. Edges are forced in and out by subtracting or | |
| 30 |
| adding a constant to all the depot edge costs and forming a new minimum | |
| 31 |
| spanning tree. | |
| 32 |
\*--------------------------------------------------------------------------*/ |
| 33 |
|
| 34 |
int make_k_tree(lb_prob *p, int *tree, int *lamda, int k) |
| 35 |
{ |
| 36 |
int nearnode, size; |
| 37 |
int host, vertnum = p->vertnum, break_node = 0, new_depot_node = 0, i; |
| 38 |
int depot_degree = 0, cur_node, prev_node, next_node, max_node = 0; |
| 39 |
int mu = 0, next_mu, cost = 0, last = 0; |
| 40 |
int *intree = NULL, max_cost; |
| 41 |
neighbor *nbtree = NULL; |
| 42 |
|
| 43 |
while (TRUE){ |
| 44 |
intree = (int *) calloc (vertnum, sizeof(int)); |
| 45 |
nbtree = (neighbor *) calloc (vertnum, sizeof(neighbor )); |
| 46 |
cost = 0; |
| 47 |
last = 0; |
| 48 |
intree[0] = IN_TREE; |
| 49 |
ni_insert_edges(p, 0, nbtree, intree, &last, lamda, mu); |
| 50 |
|
| 51 |
/*-----------------------------------------------------------------------*\ |
| 52 |
| Calculate the minimum spanning tree by adding in the nearest node to the| |
| 53 |
| current tree as long as it does not form a cycle. | |
| 54 |
\*-----------------------------------------------------------------------*/ |
| 55 |
|
| 56 |
for (size = 1; size < vertnum ; size++){ |
| 57 |
nearnode = closest(nbtree, intree, &last, &host); |
| 58 |
intree[nearnode] = IN_TREE; |
| 59 |
tree[nearnode] = host; |
| 60 |
cost += MCOST(&p->dist, host, nearnode, lamda); |
| 61 |
ni_insert_edges(p, nearnode, nbtree, intree, &last, lamda, mu); |
| 62 |
} |
| 63 |
|
| 64 |
/*----------------------------------------------------------------------*\ |
| 65 |
| Calculate the degree of the depot in the current tree | |
| 66 |
\*----------------------------------------------------------------------*/ |
| 67 |
|
| 68 |
for (depot_degree = 0, cur_node = 1; cur_node < vertnum; cur_node++){ |
| 69 |
if (!tree[cur_node]) |
| 70 |
depot_degree++; |
| 71 |
} |
| 72 |
|
| 73 |
/*-----------------------------------------------------------------------*\ |
| 74 |
| If the degree of the depot is as desired, then we are done. If it is too| |
| 75 |
| small, then we can easily determine the next edge to add adjacent to the| |
| 76 |
| depot in order to increase the degree of the depot. We add the edge that| |
| 77 |
| increase the cost of the tree the least by determining which other edge | |
| 78 |
| in the tree would be forced out. In this case, we don't need to | |
| 79 |
| recompute the tree from scratch. We simply make the appropriate switch. | |
| 80 |
| If the degree is too large, we cannot | |
| 81 |
| compute the leaving edge so easily. Then we simply raise the cost of all| |
| 82 |
| edges asjacent to the depot by an amount sufficient to force enough | |
| 83 |
| edges out of the solution. In this case, we do have to recompute the | |
| 84 |
| tree | |
| 85 |
\*-----------------------------------------------------------------------*/ |
| 86 |
|
| 87 |
if (depot_degree == k) break; |
| 88 |
|
| 89 |
if (depot_degree < k){ |
| 90 |
while (depot_degree < k){ |
| 91 |
next_mu = MAXINT; |
| 92 |
for (i = 1; i<vertnum; i++) |
| 93 |
if (tree[i]){ |
| 94 |
max_cost = -MAXINT; |
| 95 |
for (cur_node = i; tree[cur_node]; cur_node = tree[cur_node]) |
| 96 |
if ((cost = MCOST(&p->dist, tree[cur_node], cur_node, lamda)) > |
| 97 |
max_cost){ |
| 98 |
max_cost = cost; |
| 99 |
max_node = cur_node; |
| 100 |
} |
| 101 |
if ((cost = MCOST(&p->dist, 0, i, lamda) - max_cost) < next_mu){ |
| 102 |
next_mu = cost; |
| 103 |
new_depot_node = i; |
| 104 |
break_node = max_node; |
| 105 |
} |
| 106 |
} |
| 107 |
for (prev_node = new_depot_node, cur_node = tree[new_depot_node], |
| 108 |
next_node = tree[cur_node]; prev_node != break_node; |
| 109 |
tree[cur_node] = prev_node, prev_node = cur_node, |
| 110 |
cur_node = next_node, next_node = tree[next_node]); |
| 111 |
|
| 112 |
tree[new_depot_node] = 0; |
| 113 |
|
| 114 |
for (depot_degree = 0, cur_node = 1; cur_node < vertnum; cur_node++) |
| 115 |
if (!tree[cur_node]) |
| 116 |
depot_degree++; |
| 117 |
|
| 118 |
} |
| 119 |
for (cost = 0, cur_node = 1; cur_node < vertnum; cur_node++) |
| 120 |
cost += MCOST(&p->dist, cur_node, tree[cur_node], lamda); |
| 121 |
|
| 122 |
break; |
| 123 |
} |
| 124 |
else{ /*depot_degree > k*/ |
| 125 |
|
| 126 |
mu -= ICOST(&p->dist, 0,1); |
| 127 |
|
| 128 |
if (intree) free((char *) intree); |
| 129 |
if (nbtree) free((char *) nbtree); |
| 130 |
} |
| 131 |
} |
| 132 |
|
| 133 |
free ((char *)intree); |
| 134 |
free ((char *)nbtree); |
| 135 |
return(cost); |
| 136 |
} |
| 137 |
|
| 138 |
/*===========================================================================*/ |
| 139 |
|
| 140 |
int closest(neighbor *nbtree, int *intree, int *last, int *host) |
| 141 |
{ |
| 142 |
int closest_node; |
| 143 |
int pos, ch; |
| 144 |
int cost; |
| 145 |
neighbor temp; |
| 146 |
|
| 147 |
/*-----------------------------------------------------------------------*\ |
| 148 |
| This routine deletes the item from the top of the binary tree where the | |
| 149 |
| distances are stored and adjusts the tree accordingly | |
| 150 |
\*-----------------------------------------------------------------------*/ |
| 151 |
|
| 152 |
closest_node = nbtree[1].nbor; |
| 153 |
*host = nbtree[1].host; |
| 154 |
(void) memcpy ((char *)&temp, (char *)(nbtree+*last), sizeof(neighbor)); |
| 155 |
cost = nbtree[*last].cost; |
| 156 |
--*last; |
| 157 |
pos = 1; |
| 158 |
while ((ch=2*pos) < *last){ |
| 159 |
if ((nbtree[ch].cost > nbtree[ch+1].cost)|| |
| 160 |
((nbtree[ch].cost == nbtree[ch+1].cost) && !nbtree[ch+1].host)) |
| 161 |
ch++; |
| 162 |
if (cost <= nbtree[ch].cost) |
| 163 |
break; |
| 164 |
intree[nbtree[ch].nbor] = pos; |
| 165 |
(void) memcpy ((char *)(nbtree+pos), |
| 166 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 167 |
pos = ch; |
| 168 |
} |
| 169 |
if (ch == *last){ |
| 170 |
if (cost > nbtree[ch].cost){ |
| 171 |
intree[nbtree[ch].nbor] = pos; |
| 172 |
(void) memcpy ((char *)(nbtree+pos), |
| 173 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 174 |
pos=ch; |
| 175 |
} |
| 176 |
} |
| 177 |
intree[temp.nbor] = pos; |
| 178 |
(void) memcpy ((char *)(nbtree+pos), (char *)&temp, sizeof(neighbor)); |
| 179 |
return(closest_node); |
| 180 |
} |
| 181 |
|
| 182 |
/*===========================================================================*/ |
| 183 |
|
| 184 |
void ni_insert_edges(lb_prob *p, int new_node, neighbor *nbtree, int *intree, |
| 185 |
int *last, int *lamda, int mu) |
| 186 |
|
| 187 |
/*--------------------------------------------------------------------------*\ |
| 188 |
| Scan through the edges incident to 'new_node' - the new node in the set. | |
| 189 |
| If the other end 'i' is in the set, do nothing. | |
| 190 |
| If the other end is not in nbtree then insert it. | |
| 191 |
| Otherwise update its distance if necessary: | |
| 192 |
| If the previous closest point of the set to 'i' is closer then | |
| 193 |
| 'new_node' then we don't have to do anything, otherwise update. | |
| 194 |
| (update: the min element is on the top of the tree | |
| 195 |
| Therefore the insertion and the update parts can be done | |
| 196 |
| with the same code, not like in fi_insert_edges.) | |
| 197 |
\*--------------------------------------------------------------------------*/ |
| 198 |
{ |
| 199 |
int cost = 0, prevcost; |
| 200 |
int pos = 0, ch; |
| 201 |
int i; |
| 202 |
int vertnum = p->vertnum; |
| 203 |
|
| 204 |
for (i=0; i<vertnum; i++){ |
| 205 |
if (intree[i] != IN_TREE){ |
| 206 |
cost = TCOST(&p->dist, new_node, i, lamda, mu); |
| 207 |
if (intree[i] == NOT_NEIGHBOR){ |
| 208 |
pos = ++(*last); |
| 209 |
prevcost = cost+1; |
| 210 |
}else{ |
| 211 |
prevcost = nbtree[pos = intree[i]].cost; |
| 212 |
} |
| 213 |
if (prevcost > cost){ |
| 214 |
while ((ch=pos/2) != 0){ |
| 215 |
if ((nbtree[ch].cost < cost)|| |
| 216 |
((nbtree[ch].cost == cost) && !nbtree[ch].host)) |
| 217 |
break; |
| 218 |
intree[nbtree[ch].nbor] = pos; |
| 219 |
(void) memcpy ((char *)(nbtree+pos), |
| 220 |
(char *)(nbtree+ch), sizeof(neighbor)); |
| 221 |
pos = ch; |
| 222 |
} |
| 223 |
nbtree[pos].nbor = i; |
| 224 |
nbtree[pos].host = new_node; |
| 225 |
nbtree[pos].cost = cost; |
| 226 |
intree[i] = pos; |
| 227 |
} |
| 228 |
} |
| 229 |
} |
| 230 |
} |
| 231 |
|
| 232 |
/*--------------------------------------------------------------------------*\ |
| 233 |
| This routine computes the new penaltie for use in computing the lower bound| |
| 234 |
| The penalties are based on the amount of violation of the degree | |
| 235 |
| constraints in the current lower bound. | |
| 236 |
\*--------------------------------------------------------------------------*/ |
| 237 |
|
| 238 |
int new_lamda(lb_prob *p, int upper_bound, int cur_bound, int *lamda, |
| 239 |
int numroutes, int *tree, edge_data *cur_edges, |
| 240 |
int alpha) |
| 241 |
{ |
| 242 |
int gap = upper_bound-cur_bound, multiplier; |
| 243 |
int denom = 0; |
| 244 |
int cur_node1, cur_node2, vertnum = p->vertnum, i; |
| 245 |
int *degrees; |
| 246 |
|
| 247 |
degrees = (int *) calloc (vertnum, sizeof(int)); |
| 248 |
|
| 249 |
for (cur_node1 = 0; cur_node1 < vertnum; cur_node1++){ |
| 250 |
for (cur_node2 = 0; cur_node2 < vertnum; cur_node2++) |
| 251 |
if ((cur_node1 != cur_node2) && (tree[cur_node2] == cur_node1)) |
| 252 |
degrees[cur_node1]++; |
| 253 |
} |
| 254 |
|
| 255 |
for (i = 0; i < numroutes; i++){ |
| 256 |
degrees[cur_edges[i].v0]++; |
| 257 |
degrees[cur_edges[i].v1]++; |
| 258 |
} |
| 259 |
|
| 260 |
for (cur_node1 = 0; cur_node1 < vertnum; cur_node1++) |
| 261 |
denom += cur_node1 ? (degrees[cur_node1]-1)*(degrees[cur_node1]-1) : \ |
| 262 |
(degrees[cur_node1]-2*numroutes)*(degrees[cur_node1]-2*numroutes); |
| 263 |
|
| 264 |
denom = (int) sqrt((double)denom); |
| 265 |
|
| 266 |
if (!denom) return(1); |
| 267 |
|
| 268 |
multiplier = (int) (gap/(denom*alpha)); |
| 269 |
|
| 270 |
for (cur_node1 = 0; cur_node1 < vertnum; cur_node1++) |
| 271 |
lamda[cur_node1] += (degrees[cur_node1] - |
| 272 |
(cur_node1 ? 1: 2*numroutes)); |
| 273 |
|
| 274 |
if (degrees) free((char *) degrees); |
| 275 |
|
| 276 |
return(0); |
| 277 |
} |