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