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