| 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 |
/* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */ |
| 8 |
/* */ |
| 9 |
/* This application was developed by Ted Ralphs ([email protected]) */ |
| 10 |
/* */ |
| 11 |
/* This software is licensed under the Eclipse Public License. Please see */ |
| 12 |
/* accompanying file for terms. */ |
| 13 |
/* */ |
| 14 |
/*===========================================================================*/ |
| 15 |
|
| 16 |
/* system include files */ |
| 17 |
#include <stdio.h> |
| 18 |
#include <stdlib.h> |
| 19 |
#include <math.h> |
| 20 |
|
| 21 |
/* SYMPHONY include files */ |
| 22 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 23 |
#include "sym_master.h" |
| 24 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 25 |
#include "sym_macros.h" |
| 26 |
#include "sym_constants.h" |
| 27 |
#include "sym_proccomm.h" |
| 28 |
#include "sym_qsort.h" |
| 29 |
#include "sym_dg_params.h" |
| 30 |
#include "sym_master_u.h" |
| 31 |
|
| 32 |
/* VRP include files */ |
| 33 |
#include "vrp_const.h" |
| 34 |
#include "vrp_types.h" |
| 35 |
#include "vrp_io.h" |
| 36 |
#include "compute_cost.h" |
| 37 |
#include "network.h" |
| 38 |
#ifdef COMPILE_HEURS |
| 39 |
#include "start_heurs.h" |
| 40 |
#endif |
| 41 |
#include "vrp_master_functions.h" |
| 42 |
#include "vrp_dg_functions.h" |
| 43 |
#include "vrp_macros.h" |
| 44 |
#include "small_graph.h" |
| 45 |
#ifdef COMPILE_IN_TM |
| 46 |
#ifdef COMPILE_IN_CP |
| 47 |
#include "vrp_cp.h" |
| 48 |
#endif |
| 49 |
#ifdef COMPILE_IN_LP |
| 50 |
#include "vrp_lp.h" |
| 51 |
#ifdef COMPILE_IN_CG |
| 52 |
#include "vrp_cg.h" |
| 53 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 54 |
#ifdef COMPILE_OUR_DECOMP |
| 55 |
#include "my_decomp.h" |
| 56 |
#endif |
| 57 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 58 |
#endif |
| 59 |
#endif |
| 60 |
#endif |
| 61 |
|
| 62 |
/*===========================================================================*/ |
| 63 |
|
| 64 |
/*===========================================================================*\ |
| 65 |
* This file contains the user-written functions for the master process. |
| 66 |
\*===========================================================================*/ |
| 67 |
|
| 68 |
void user_usage(void){ |
| 69 |
printf("vrp [ -HEPT ] [ -S file ] [ -F file ] [ -B rule ]\n\t" |
| 70 |
"[ -V sel ] [ -K closest ] [ -N routes ] [ -C capacity ]\n" |
| 71 |
"\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n" |
| 72 |
"\t%s\n\t%s\n\t%s\n" |
| 73 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 74 |
"\t%s\n" |
| 75 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 76 |
"\n", |
| 77 |
"-H: help", |
| 78 |
"-E: use sparse edge set", |
| 79 |
"-T: solve as a Traveling Salesman Problem", |
| 80 |
"-S file: load sparse graph from 'file'", |
| 81 |
"-F file: problem data is in 'file'", |
| 82 |
"-B i: which candidates to check in strong branching", |
| 83 |
"-A i: how to construct the base set of variables", |
| 84 |
"-V i: verbosity level", |
| 85 |
"-K k: use 'k' closest edges to build sparse graph", |
| 86 |
"-N n: use 'n' routes", |
| 87 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 88 |
"-P: solve as a Bin Packing Problem", |
| 89 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 90 |
"-C c: use capacity 'c'"); |
| 91 |
} |
| 92 |
|
| 93 |
/*===========================================================================*\ |
| 94 |
* Initialize user-defined data structures. In this case, I store all |
| 95 |
* problem-specific data such as the location of the customers, edge costs, |
| 96 |
* etc. in this data-structure. |
| 97 |
\*===========================================================================*/ |
| 98 |
|
| 99 |
int user_initialize(void **user) |
| 100 |
{ |
| 101 |
vrp_problem *vrp = (vrp_problem *) calloc(1, sizeof(vrp_problem)); |
| 102 |
|
| 103 |
*user = vrp; |
| 104 |
|
| 105 |
vrp_set_defaults(vrp); |
| 106 |
|
| 107 |
return(USER_SUCCESS); |
| 108 |
} |
| 109 |
|
| 110 |
/*===========================================================================*/ |
| 111 |
|
| 112 |
/*===========================================================================*\ |
| 113 |
* In this function, I set up the user parameters. The first step is to cast |
| 114 |
* the void pointer in order to access my data. In the readparams() function, |
| 115 |
* I read in parameters from the parameter file given on the command line. |
| 116 |
\*===========================================================================*/ |
| 117 |
|
| 118 |
int user_readparams(void *user, char *filename, int argc, char **argv) |
| 119 |
{ |
| 120 |
vrp_problem *vrp = (vrp_problem *)user; |
| 121 |
|
| 122 |
vrp_readparams(vrp, filename, argc, argv); |
| 123 |
|
| 124 |
#if 0 |
| 125 |
if (vrp->par.use_small_graph == LOAD_SMALL_GRAPH){ |
| 126 |
read_small_graph(vrp); |
| 127 |
vrp->numroutes = vrp->cur_tour->numroutes; |
| 128 |
} |
| 129 |
|
| 130 |
/* Selects the cheapest edges adjacent to each node for the base set */ |
| 131 |
|
| 132 |
if (vrp->par.use_small_graph == SAVE_SMALL_GRAPH){ |
| 133 |
if (!vrp->g) make_small_graph(vrp, 0); |
| 134 |
save_small_graph(vrp); |
| 135 |
}else if (!vrp->g){ |
| 136 |
make_small_graph(vrp, 0); |
| 137 |
} |
| 138 |
#endif |
| 139 |
return(USER_SUCCESS); |
| 140 |
} |
| 141 |
|
| 142 |
/*===========================================================================*/ |
| 143 |
|
| 144 |
/*===========================================================================*\ |
| 145 |
* After I've read in the parameters, I can now read in the data file, whose |
| 146 |
* name was given in the parameter file. This file contains instance data. |
| 147 |
\*===========================================================================*/ |
| 148 |
|
| 149 |
int user_io(void *user) |
| 150 |
{ |
| 151 |
vrp_problem *vrp = (vrp_problem *)user; |
| 152 |
int i; |
| 153 |
|
| 154 |
if (strcmp(vrp->par.infile, "")){ |
| 155 |
vrp_io(vrp, vrp->par.infile); |
| 156 |
} |
| 157 |
|
| 158 |
if (vrp->numroutes == 1){ |
| 159 |
vrp->par.tsp_prob = TRUE; |
| 160 |
vrp->capacity = vrp->vertnum; |
| 161 |
vrp->numroutes = 1; |
| 162 |
vrp->demand = (int *) malloc (vrp->vertnum * ISIZE); |
| 163 |
vrp->demand[0] = vrp->vertnum; |
| 164 |
for (i = vrp->vertnum - 1; i > 0; i--) |
| 165 |
vrp->demand[i] = 1; |
| 166 |
vrp->cg_par.tsp_prob = TRUE; |
| 167 |
if (!vrp->cg_par.which_tsp_cuts) |
| 168 |
vrp->cg_par.which_tsp_cuts = ALL_TSP_CUTS; |
| 169 |
} |
| 170 |
|
| 171 |
vrp->cur_tour = (best_tours *) calloc(1, sizeof(best_tours)); |
| 172 |
vrp->cur_tour->tour = (_node *) calloc(vrp->vertnum, sizeof(_node)); |
| 173 |
#ifdef COMPILE_HEURS |
| 174 |
vrp->tours = (best_tours *) calloc(vrp->par.tours_to_keep, |
| 175 |
sizeof(best_tours)); |
| 176 |
#endif |
| 177 |
|
| 178 |
if (vrp->par.k_closest < 0){ |
| 179 |
vrp->par.k_closest = (int) (ceil(0.1 * vrp->vertnum)); |
| 180 |
if (vrp->par.k_closest < vrp->par.min_closest ) |
| 181 |
vrp->par.k_closest = vrp->par.min_closest; |
| 182 |
if (vrp->par.k_closest > vrp->par.max_closest) |
| 183 |
vrp->par.k_closest = vrp->par.max_closest; |
| 184 |
if (vrp->par.k_closest > vrp->vertnum-1) |
| 185 |
vrp->par.k_closest = vrp->vertnum-1; |
| 186 |
} |
| 187 |
|
| 188 |
if (vrp->par.use_small_graph == LOAD_SMALL_GRAPH){ |
| 189 |
read_small_graph(vrp); |
| 190 |
vrp->numroutes = vrp->cur_tour->numroutes; |
| 191 |
} |
| 192 |
|
| 193 |
/* Selects the cheapest edges adjacent to each node for the base set */ |
| 194 |
|
| 195 |
if (vrp->par.use_small_graph == SAVE_SMALL_GRAPH){ |
| 196 |
if (!vrp->g) make_small_graph(vrp, 0); |
| 197 |
save_small_graph(vrp); |
| 198 |
}else if (!vrp->g){ |
| 199 |
make_small_graph(vrp, 0); |
| 200 |
} |
| 201 |
|
| 202 |
return(USER_SUCCESS); |
| 203 |
} |
| 204 |
|
| 205 |
/*===========================================================================*/ |
| 206 |
|
| 207 |
/*===========================================================================*\ |
| 208 |
* Here is where the heuristics are performed and an upper bound is calculated. |
| 209 |
* An upper bound can also be specified in the parameter file. The |
| 210 |
* other thing I do in this routine is build up a graph of the |
| 211 |
* cheapest k edges adjacent to the each node plus any edges chosen |
| 212 |
* during the heuristics to comprise my base set later. |
| 213 |
\*===========================================================================*/ |
| 214 |
|
| 215 |
int user_start_heurs(void *user, double *ub, double *ub_estimate) |
| 216 |
{ |
| 217 |
vrp_problem *vrp = (vrp_problem *)user; |
| 218 |
|
| 219 |
if (*ub > 0){ |
| 220 |
vrp->cur_tour->cost = (int) (*ub); |
| 221 |
}else if (vrp->cur_tour->cost > 0){ |
| 222 |
*ub = (int)(vrp->cur_tour->cost); |
| 223 |
}else{ |
| 224 |
vrp->cur_tour->cost = MAXINT; |
| 225 |
} |
| 226 |
|
| 227 |
vrp->cur_tour->numroutes = vrp->numroutes; |
| 228 |
|
| 229 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 230 |
if(vrp->par.bpp_prob) |
| 231 |
*ub = 1; |
| 232 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 233 |
|
| 234 |
#ifdef COMPILE_HEURS |
| 235 |
if (vrp->par.do_heuristics || vrp->lb_par.lower_bound) |
| 236 |
start_heurs(vrp, &vrp->heur_par, &vrp->lb_par, ub, FALSE); |
| 237 |
else |
| 238 |
vrp->tournum = -1; |
| 239 |
#endif |
| 240 |
|
| 241 |
if (!vrp->numroutes){ |
| 242 |
printf("\nError: Number of trucks not specified or computed " |
| 243 |
"for VRP\n\n"); |
| 244 |
exit(1); |
| 245 |
} |
| 246 |
|
| 247 |
if (vrp->par.verbosity < 0){ |
| 248 |
return(USER_SUCCESS); |
| 249 |
} |
| 250 |
|
| 251 |
if (vrp->numroutes > 1){ |
| 252 |
printf("NUMBER OF TRUCKS: \t%i\n", vrp->numroutes); |
| 253 |
printf("TIGHTNESS: \t\t%.2f\n", |
| 254 |
(double)vrp->demand[0]/((double)vrp->capacity*(double)vrp->numroutes)); |
| 255 |
} |
| 256 |
|
| 257 |
|
| 258 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 259 |
if (*ub > 0 && !vrp->par.bpp_prob) |
| 260 |
printf("INITIAL UPPER BOUND: \t%i\n\n", (int)(*ub)); |
| 261 |
else if (!vrp->par.bpp_prob) |
| 262 |
printf("INITIAL UPPER BOUND: \tNone\n\n"); |
| 263 |
else |
| 264 |
printf("\n\n"); |
| 265 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 266 |
/*UNCOMMENT FOR PRODUCTION CODE*/ |
| 267 |
#if 0 |
| 268 |
if (*ub > 0) |
| 269 |
printf("INITIAL UPPER BOUND: \t%i\n\n", (int)(*ub)); |
| 270 |
else |
| 271 |
printf("INITIAL UPPER BOUND: \tNone\n\n"); |
| 272 |
#endif |
| 273 |
|
| 274 |
return(USER_SUCCESS); |
| 275 |
} |
| 276 |
|
| 277 |
/*===========================================================================*/ |
| 278 |
|
| 279 |
/*===========================================================================*\ |
| 280 |
* If graph drawing will be use, the user must initialize the drawing |
| 281 |
* window here. |
| 282 |
\*===========================================================================*/ |
| 283 |
|
| 284 |
int user_init_draw_graph(void *user, int dg_id) |
| 285 |
{ |
| 286 |
#ifndef WIN32 /* FIXME : None of this works in Windows */ |
| 287 |
vrp_problem *vrp = (vrp_problem *)user; |
| 288 |
int s_bufid; |
| 289 |
|
| 290 |
if (!(vrp->posx && vrp->posy)) return(USER_NO_PP); |
| 291 |
if ( (vrp->dg_id = dg_id) ){ |
| 292 |
int i, zero = 0, eight = 0x08; |
| 293 |
char node_place[MAX_NAME_LENGTH] = {"node_placement"}; |
| 294 |
char weight[5]; |
| 295 |
int *posx = vrp->posx, *posy = vrp->posy; |
| 296 |
int minx=MAXINT, miny=MAXINT, maxx=-MAXINT, maxy=-MAXINT, xx, yy; |
| 297 |
int width = 1000, height = 700; |
| 298 |
#if 0 |
| 299 |
int width=p->par.dg_par.canvas_width, height=p->par.dg_par.canvas_height; |
| 300 |
#endif |
| 301 |
double mult; |
| 302 |
|
| 303 |
for (i = vrp->vertnum - 1; i >= 0; i--){ |
| 304 |
if (posx[i] < minx) minx = posx[i]; |
| 305 |
if (posx[i] > maxx) maxx = posx[i]; |
| 306 |
if (posy[i] < miny) miny = posy[i]; |
| 307 |
if (posy[i] > maxy) maxy = posy[i]; |
| 308 |
} |
| 309 |
xx = maxx - minx; |
| 310 |
yy = maxy - miny; |
| 311 |
mult = (int) MIN((width - 20.0)/xx, (height-20.0)/yy); |
| 312 |
width = (int) (xx * mult + 30); |
| 313 |
height = (int) (yy * mult + 30); |
| 314 |
for (i = vrp->vertnum-1; i >= 0; i--){ |
| 315 |
posx[i] = (int) ((posx[i] - minx) * mult + 10); |
| 316 |
posy[i] = (int) ((maxy - posy[i]) * mult + 10); |
| 317 |
} |
| 318 |
|
| 319 |
init_window(dg_id, node_place, width, height); |
| 320 |
/* Now pack the placement of the nodes of the graph */ |
| 321 |
s_bufid = init_send(DataInPlace); |
| 322 |
send_str(node_place); |
| 323 |
send_int_array(&vrp->vertnum, 1); |
| 324 |
for (i = 0; i < vrp->vertnum; i++){ |
| 325 |
send_int_array(&i, 1); |
| 326 |
send_int_array(posx + i, 1); |
| 327 |
send_int_array(posy + i, 1); |
| 328 |
send_int_array(&eight, 1); |
| 329 |
sprintf(weight, "%i", vrp->demand[i]); |
| 330 |
send_str(weight); |
| 331 |
} |
| 332 |
/* No edges are passed to the default graph */ |
| 333 |
send_int_array(&zero, 1); |
| 334 |
send_msg(dg_id, CTOI_SET_GRAPH); |
| 335 |
freebuf(s_bufid); |
| 336 |
|
| 337 |
display_graph(dg_id, node_place); |
| 338 |
} |
| 339 |
#endif |
| 340 |
|
| 341 |
return(USER_SUCCESS); |
| 342 |
} |
| 343 |
|
| 344 |
/*===========================================================================*/ |
| 345 |
|
| 346 |
/*===========================================================================*\ |
| 347 |
* In this routine, I build the initial edge set for the root. There are |
| 348 |
* several things going on here. First, there is a user-defined parameter |
| 349 |
* defining whether or not to just go ahead and add all variables to the |
| 350 |
* problem up front (vrp->par.add_all_edges). Currently, this seems to be the |
| 351 |
* best option since the problems are small anyway. Further, I am doing some |
| 352 |
* preprocessing here by eliminating edges for which the sum of the demands of |
| 353 |
* their endpoints is greater than the capacity since these edges cannot |
| 354 |
* be in any feasible solution. |
| 355 |
* |
| 356 |
* Notice that there are several options programmed for which set |
| 357 |
* of edges should be in the base set. The |
| 358 |
* base constraints are just the degree constraints from the IP |
| 359 |
* formulation. These do not have to be specified explicitly, just the |
| 360 |
* number of them given. |
| 361 |
\*===========================================================================*/ |
| 362 |
|
| 363 |
int user_initialize_root_node(void *user, int *basevarnum, int **basevars, |
| 364 |
int *basecutnum, int *extravarnum, |
| 365 |
int **extravars, char *obj_sense, |
| 366 |
double *obj_offset, char ***colnames, |
| 367 |
int *colgen_strat) |
| 368 |
{ |
| 369 |
vrp_problem *vrp = (vrp_problem *)user; |
| 370 |
int base_varnum = 0; |
| 371 |
int i, j, k, l; |
| 372 |
int zero_varnum, *zero_vars; |
| 373 |
int vertnum = vrp->vertnum; |
| 374 |
int *edges; |
| 375 |
|
| 376 |
/* Form the set of base variables */ |
| 377 |
switch(vrp->par.base_variable_selection){ |
| 378 |
case SOME_ARE_BASE: |
| 379 |
if (vrp->par.add_all_edges == FALSE) |
| 380 |
/*If we are not adding all the edges, then really EVERYTHING_IS_BASE*/ |
| 381 |
vrp->par.base_variable_selection = EVERYTHING_IS_BASE; |
| 382 |
else /*Otherwise, all we need to do is set this and then fall through -- |
| 383 |
the remaining edges get added in user_create_root()*/ |
| 384 |
vrp->par.add_all_edges = FALSE; |
| 385 |
|
| 386 |
|
| 387 |
case EVERYTHING_IS_BASE: |
| 388 |
*basevars = create_edge_list(vrp, &base_varnum, CHEAP_EDGES); |
| 389 |
|
| 390 |
*basevars = (int *) realloc((char *)(*basevars), base_varnum * ISIZE); |
| 391 |
*basevarnum = base_varnum; |
| 392 |
|
| 393 |
break; |
| 394 |
|
| 395 |
case EVERYTHING_IS_EXTRA: |
| 396 |
*basevarnum = 0; |
| 397 |
break; |
| 398 |
} |
| 399 |
|
| 400 |
*basecutnum = vertnum; |
| 401 |
|
| 402 |
if (!vrp->par.colgen_strat[0]){ |
| 403 |
#if 0 |
| 404 |
/* Currently, column generation is broken */ |
| 405 |
if (vrp->par.add_all_edges || |
| 406 |
vrp->par.base_variable_selection == SOME_ARE_BASE){ |
| 407 |
colgen_strat[0]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD | |
| 408 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 409 |
}else{ |
| 410 |
colgen_strat[0] = (FATHOM__DO_NOT_GENERATE_COLS__SEND | |
| 411 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 412 |
} |
| 413 |
#endif |
| 414 |
colgen_strat[0]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD | |
| 415 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 416 |
}else{ |
| 417 |
colgen_strat[0] = vrp->par.colgen_strat[0]; |
| 418 |
} |
| 419 |
if (!vrp->par.colgen_strat[1]){ |
| 420 |
if (vrp->par.add_all_edges || |
| 421 |
vrp->par.base_variable_selection == SOME_ARE_BASE){ |
| 422 |
colgen_strat[1]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD | |
| 423 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 424 |
}else{ |
| 425 |
colgen_strat[1] = (FATHOM__GENERATE_COLS__RESOLVE | |
| 426 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 427 |
} |
| 428 |
}else{ |
| 429 |
colgen_strat[1] = vrp->par.colgen_strat[1]; |
| 430 |
} |
| 431 |
|
| 432 |
/*create the edge list (we assume a complete graph) The edge is set to |
| 433 |
(0,0) in the edge list if it was eliminated in preprocessing*/ |
| 434 |
edges = vrp->edges = (int *) calloc (vertnum*(vertnum-1), sizeof(int)); |
| 435 |
zero_varnum = vrp->zero_varnum; |
| 436 |
zero_vars = vrp->zero_vars; |
| 437 |
for (i = 1, k = 0, l = 0; i < vertnum; i++){ |
| 438 |
for (j = 0; j < i; j++){ |
| 439 |
if (l < zero_varnum && k == zero_vars[l]){ |
| 440 |
/*This is one of the zero edges*/ |
| 441 |
edges[2*k] = edges[2*k+1] = 0; |
| 442 |
l++; |
| 443 |
k++; |
| 444 |
continue; |
| 445 |
} |
| 446 |
edges[2*k] = j; |
| 447 |
edges[2*k+1] = i; |
| 448 |
k++; |
| 449 |
} |
| 450 |
} |
| 451 |
|
| 452 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 453 |
if (vrp->par.bpp_prob){ |
| 454 |
for (i = 0; i < *basevarnum; i++){ |
| 455 |
vrp->dist.cost[(*basevars)[i]] = 10; |
| 456 |
} |
| 457 |
} |
| 458 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 459 |
|
| 460 |
/* Form the set of extra variables */ |
| 461 |
switch(vrp->par.base_variable_selection){ |
| 462 |
case EVERYTHING_IS_EXTRA: |
| 463 |
|
| 464 |
*extravars = create_edge_list(vrp, extravarnum, CHEAP_EDGES); |
| 465 |
|
| 466 |
break; |
| 467 |
|
| 468 |
case SOME_ARE_BASE: |
| 469 |
|
| 470 |
vrp->par.add_all_edges = TRUE; /*We turned this off in user_set_base() |
| 471 |
-- now we need to turn it back on*/ |
| 472 |
|
| 473 |
*extravars = create_edge_list(vrp, extravarnum, REMAINING_EDGES); |
| 474 |
|
| 475 |
break; |
| 476 |
|
| 477 |
case EVERYTHING_IS_BASE: |
| 478 |
|
| 479 |
break; |
| 480 |
} |
| 481 |
|
| 482 |
return(USER_SUCCESS); |
| 483 |
} |
| 484 |
|
| 485 |
/*===========================================================================*/ |
| 486 |
|
| 487 |
/*===========================================================================*\ |
| 488 |
* In my case, a feasible solution is specified most compactly by |
| 489 |
* essentially a permutation of the customers along with routes numbers, |
| 490 |
* specifying the order of the customers on their routes. This is just |
| 491 |
* sent as a character array which then gets cast to an array of |
| 492 |
* structures, one for each customers specifying the route number and |
| 493 |
* the next customer on the route. |
| 494 |
\*===========================================================================*/ |
| 495 |
|
| 496 |
int user_receive_feasible_solution(void *user, int msgtag, double cost, |
| 497 |
int numvars, int *indices, double *values) |
| 498 |
{ |
| 499 |
vrp_problem *vrp = (vrp_problem *)user; |
| 500 |
|
| 501 |
receive_char_array((char *)vrp->cur_tour->tour, vrp->vertnum*sizeof(_node)); |
| 502 |
|
| 503 |
return(USER_SUCCESS); |
| 504 |
} |
| 505 |
|
| 506 |
/*===========================================================================*/ |
| 507 |
|
| 508 |
/*===========================================================================*\ |
| 509 |
* Here, we send the necessary data to the LP process. Notice that |
| 510 |
* there are two cases to deal with. If the LP or the TM are running |
| 511 |
* as separate processes, then we have to send the data by |
| 512 |
* message-passing. Otherwise, we can allocate the user-defined LP data |
| 513 |
* structure here and simply copy the necessary information. This is the |
| 514 |
* only place the user has to sorry about this distinction between |
| 515 |
* configurations. |
| 516 |
\*===========================================================================*/ |
| 517 |
|
| 518 |
int user_send_lp_data(void *user, void **user_lp) |
| 519 |
{ |
| 520 |
vrp_problem *vrp = (vrp_problem *)user; |
| 521 |
|
| 522 |
#if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) |
| 523 |
/* This is the case when we are copying data directly because |
| 524 |
the LP is not running separately. This code should be virtually |
| 525 |
identical to that of user_receive_lp_data() in the LP process.*/ |
| 526 |
|
| 527 |
vrp_lp_problem *vrp_lp = (vrp_lp_problem *) calloc(1, |
| 528 |
sizeof(vrp_lp_problem)); |
| 529 |
*user_lp = (void *)vrp_lp; |
| 530 |
|
| 531 |
vrp_lp->par = vrp->lp_par; |
| 532 |
vrp_lp->window = vrp->dg_id; |
| 533 |
vrp_lp->numroutes = vrp->numroutes; |
| 534 |
vrp_lp->vertnum = vrp->vertnum; |
| 535 |
vrp_lp->edges = vrp->edges; |
| 536 |
vrp_lp->demand = vrp->demand; |
| 537 |
vrp_lp->capacity = vrp->capacity; |
| 538 |
vrp_lp->costs = vrp->dist.cost; |
| 539 |
|
| 540 |
vrp_lp->cur_sol = (_node *) calloc (vrp_lp->vertnum, sizeof(_node)); |
| 541 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 542 |
|
| 543 |
if (vrp_lp->window){ |
| 544 |
copy_node_set(vrp_lp->window, TRUE, (char *)"Original solution"); |
| 545 |
#if 0 |
| 546 |
copy_node_set(vrp_lp->window, TRUE, (char *)"Compressed solution"); |
| 547 |
#endif |
| 548 |
} |
| 549 |
|
| 550 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 551 |
|
| 552 |
#else |
| 553 |
/* Here, we send that data using message passing and the rest is |
| 554 |
done in user_receive_lp_data() in the LP process */ |
| 555 |
|
| 556 |
send_char_array((char *)(&vrp->lp_par), sizeof(vrp_lp_params)); |
| 557 |
send_int_array(&vrp->dg_id, 1); |
| 558 |
send_int_array(&vrp->numroutes, 1); |
| 559 |
send_int_array(&vrp->vertnum, 1); |
| 560 |
send_int_array(vrp->demand, vrp->vertnum); |
| 561 |
send_int_array(&vrp->capacity, 1); |
| 562 |
send_int_array(vrp->dist.cost, vrp->edgenum); |
| 563 |
send_int_array(&vrp->zero_varnum, 1); |
| 564 |
if (vrp->zero_varnum){ |
| 565 |
send_int_array(vrp->zero_vars, vrp->zero_varnum); |
| 566 |
} |
| 567 |
#endif |
| 568 |
|
| 569 |
return(USER_SUCCESS); |
| 570 |
} |
| 571 |
|
| 572 |
/*===========================================================================*/ |
| 573 |
|
| 574 |
/*===========================================================================*\ |
| 575 |
* Here, we send the necessary data to the CG process. Notice that |
| 576 |
* there are two cases to deal with. If the CG, LP, or the TM are running |
| 577 |
* as separate processes, then we have to send the data by |
| 578 |
* message-passing. Otherwise, we can allocate the user-defined LP data |
| 579 |
* structure here and simply copy the necessary information. This is the |
| 580 |
* only place the user has to sorry about this distinction between |
| 581 |
* configurations. |
| 582 |
\*===========================================================================*/ |
| 583 |
|
| 584 |
int user_send_cg_data(void *user, void **user_cg) |
| 585 |
{ |
| 586 |
vrp_problem *vrp = (vrp_problem *)user; |
| 587 |
|
| 588 |
#if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CG) |
| 589 |
/* This is is the case when we are copying data directly because |
| 590 |
the CG is not running separately. This code should be virtually |
| 591 |
identical to that of user_receive_cg_data() in the CG process.*/ |
| 592 |
|
| 593 |
vrp_cg_problem *vrp_cg = (vrp_cg_problem *) malloc (sizeof(vrp_cg_problem)); |
| 594 |
int edgenum, vertnum, i, j, k; |
| 595 |
|
| 596 |
*user_cg = (void *)vrp_cg; |
| 597 |
|
| 598 |
vrp_cg->par = vrp->cg_par; |
| 599 |
vrp_cg->numroutes = vrp->numroutes; |
| 600 |
vertnum = vrp_cg->vertnum = vrp->vertnum; |
| 601 |
vrp_cg->demand = (int *) malloc(vrp->vertnum*sizeof(int)); |
| 602 |
memcpy(vrp_cg->demand, vrp->demand, vrp->vertnum*sizeof(int)); |
| 603 |
vrp_cg->capacity = vrp->capacity; |
| 604 |
vrp_cg->dg_id = vrp->dg_id; |
| 605 |
|
| 606 |
edgenum = vrp->vertnum*(vrp->vertnum-1)/2; |
| 607 |
|
| 608 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 609 |
#ifdef COMPILE_OUR_DECOMP |
| 610 |
if (vrp->cg_par.do_our_decomp){ |
| 611 |
vrp_cg->cost = vrp->dist.cost; |
| 612 |
usr_open_decomp_lp( get_cg_ptr(NULL), edgenum ); |
| 613 |
} |
| 614 |
vrp_cg->last_decomp_index = -1; |
| 615 |
#endif |
| 616 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 617 |
vrp_cg->in_set = (char *) calloc(vrp->vertnum, sizeof(char)); |
| 618 |
vrp_cg->ref = (int *) malloc(vrp->vertnum*sizeof(int)); |
| 619 |
vrp_cg->new_demand = (int *) malloc(vrp->vertnum*sizeof(int)); |
| 620 |
vrp_cg->cut_val = (double *) calloc(vrp->vertnum, sizeof(double)); |
| 621 |
vrp_cg->cut_list = (char *) malloc(((vrp->vertnum >> DELETE_POWER)+1)* |
| 622 |
(vrp->cg_par.max_num_cuts_in_shrink + 1)* |
| 623 |
sizeof(char)); |
| 624 |
|
| 625 |
vrp_cg->edges = (int *) calloc (2*edgenum, sizeof(int)); |
| 626 |
|
| 627 |
/*create the edge list (we assume a complete graph)*/ |
| 628 |
for (i = 1, k = 0; i < vertnum; i++){ |
| 629 |
for (j = 0; j < i; j++){ |
| 630 |
vrp_cg->edges[2*k] = j; |
| 631 |
vrp_cg->edges[2*k+1] = i; |
| 632 |
k++; |
| 633 |
} |
| 634 |
} |
| 635 |
|
| 636 |
#ifdef CHECK_CUT_VALIDITY |
| 637 |
if ((vrp_cg->feas_sol_size = vrp->feas_sol_size)){ |
| 638 |
vrp_cg->feas_sol = vrp->feas_sol; |
| 639 |
} |
| 640 |
#endif |
| 641 |
#else |
| 642 |
/* Here, we send that data using message passing and the rest is |
| 643 |
done in user_receive_cg_data() in the CG process */ |
| 644 |
|
| 645 |
send_char_array((char *)&vrp->cg_par, sizeof(vrp_cg_params)); |
| 646 |
send_int_array(&vrp->dg_id, 1); |
| 647 |
send_int_array(&vrp->numroutes, 1); |
| 648 |
send_int_array(&vrp->vertnum, 1); |
| 649 |
send_int_array(vrp->demand, vrp->vertnum); |
| 650 |
send_int_array(&vrp->capacity, 1); |
| 651 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 652 |
if (vrp->cg_par.do_our_decomp)/* need to send costs to CG too */ |
| 653 |
send_int_array(vrp->dist.cost, vrp->edgenum); |
| 654 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 655 |
#ifdef CHECK_CUT_VALIDITY |
| 656 |
send_int_array(&vrp->feas_sol_size, 1); |
| 657 |
if (vrp->feas_sol_size){ |
| 658 |
send_int_array(vrp->feas_sol, vrp->feas_sol_size); |
| 659 |
} |
| 660 |
#endif |
| 661 |
#endif |
| 662 |
|
| 663 |
return(USER_SUCCESS); |
| 664 |
} |
| 665 |
|
| 666 |
/*===========================================================================*/ |
| 667 |
|
| 668 |
/*===========================================================================*\ |
| 669 |
* Here, we send the necessary data to the CP process. Notice that |
| 670 |
* there are two cases to deal with. If the CP, LP, or the TM are running |
| 671 |
* as separate processes, then we have to send the data by |
| 672 |
* message-passing. Otherwise, we can allocate the user-defined LP data |
| 673 |
* structure here and simply copy the necessary information. This is the |
| 674 |
* only place the user has to sorry about this distinction between |
| 675 |
* configurations. |
| 676 |
\*===========================================================================*/ |
| 677 |
|
| 678 |
int user_send_cp_data(void *user, void **user_cp) |
| 679 |
{ |
| 680 |
vrp_problem *vrp = (vrp_problem *)user; |
| 681 |
|
| 682 |
#if defined(COMPILE_IN_TM) && defined (COMPILE_IN_CP) |
| 683 |
/* This is is the case when we are copying data directly because |
| 684 |
the LP is not running separately. This code should be virtually |
| 685 |
identical to that of user_receive_cp_data() in the CP process.*/ |
| 686 |
|
| 687 |
vrp_cp_problem *vrp_cp = (vrp_cp_problem *) malloc (sizeof(vrp_cp_problem)); |
| 688 |
int i, j, k; |
| 689 |
|
| 690 |
vrp_cp->vertnum = vrp->vertnum; |
| 691 |
|
| 692 |
*user_cp = (void *)vrp_cp; |
| 693 |
|
| 694 |
vrp_cp->edgenum = vrp_cp->vertnum*(vrp_cp->vertnum-1)/2 + vrp_cp->vertnum-1; |
| 695 |
vrp_cp->edges = (int *) calloc ((int)2*vrp_cp->edgenum, sizeof(int)); |
| 696 |
|
| 697 |
/* create the edge list (we assume a complete graph) */ |
| 698 |
for (i = 1, k = 0; i < vrp_cp->vertnum; i++){ |
| 699 |
for (j = 0; j < i; j++){ |
| 700 |
vrp_cp->edges[2*k] = j; |
| 701 |
vrp_cp->edges[2*k+1] = i; |
| 702 |
k++; |
| 703 |
} |
| 704 |
} |
| 705 |
|
| 706 |
/* now add the duplicate copies of the depot edges to allow for |
| 707 |
routes with one customer */ |
| 708 |
for (i = 1; i < vrp_cp->vertnum; i++){ |
| 709 |
vrp_cp->edges[2*k] = 0; |
| 710 |
vrp_cp->edges[2*k+1] = i; |
| 711 |
k++; |
| 712 |
} |
| 713 |
#else |
| 714 |
/* Here, we send that data using message passing and the rest is |
| 715 |
done in user_receive_cp_data() in the CP process */ |
| 716 |
|
| 717 |
send_int_array(&vrp->vertnum, 1); |
| 718 |
#endif |
| 719 |
|
| 720 |
return(USER_SUCCESS); |
| 721 |
} |
| 722 |
|
| 723 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 724 |
/*===========================================================================*/ |
| 725 |
|
| 726 |
int user_send_sp_data(void *user) |
| 727 |
{ |
| 728 |
#ifdef COMPILE_HEURS |
| 729 |
vrp_problem *vrp = (vrp_problem *) user; |
| 730 |
int i, j; |
| 731 |
int size; |
| 732 |
_node *tour; |
| 733 |
int *coef; |
| 734 |
int tournum = vrp->tournum + 1 + vrp->sol_pool_col_num; |
| 735 |
int cur_node, next_node; |
| 736 |
int v0, v1; |
| 737 |
int vertnum = vrp->vertnum; |
| 738 |
/*FIXME: temporary fix to allow this to compile without PVM*/ |
| 739 |
|
| 740 |
coef = (int *) calloc (vrp->vertnum - 1 + vrp->numroutes, ISIZE); |
| 741 |
size = (vrp->vertnum-1 + vrp->numroutes) * ISIZE; |
| 742 |
|
| 743 |
send_int_array(&vrp->vertnum, 1); |
| 744 |
|
| 745 |
send_int_array(&tournum, 1); |
| 746 |
|
| 747 |
if (tournum <= 0){ |
| 748 |
return(USER_SUCCESS); |
| 749 |
} |
| 750 |
|
| 751 |
for (i = 0; i<=vrp->tournum; i++){ |
| 752 |
tour = vrp->tours[i].tour; |
| 753 |
coef[0] = INDEX(0, tour[0].next); |
| 754 |
for (cur_node = tour[0].next, next_node = tour[cur_node].next, j = 1; |
| 755 |
cur_node; |
| 756 |
cur_node = next_node, next_node = tour[next_node].next, j++){ |
| 757 |
if(tour[cur_node].route == tour[next_node].route){ |
| 758 |
coef[j] = INDEX(cur_node, next_node); |
| 759 |
}else if (next_node){ |
| 760 |
coef[j++] = INDEX(0, cur_node); |
| 761 |
if (coef[j-1] == coef[j-2]) |
| 762 |
coef[j-1] = vertnum*(vertnum-1)/2 + cur_node - 1; |
| 763 |
coef[j] = INDEX(0, next_node); |
| 764 |
}else{ |
| 765 |
coef[j] = INDEX(0, cur_node); |
| 766 |
} |
| 767 |
} |
| 768 |
|
| 769 |
qsort_i(coef, size/sizeof(int)); |
| 770 |
|
| 771 |
send_int_array(&size, 1); |
| 772 |
send_char_array((char *)coef, size); |
| 773 |
} |
| 774 |
|
| 775 |
for (i = 0; i<vrp->sol_pool_col_num; i++){ |
| 776 |
for (j = 0; j < 2*size/sizeof(int); j+=2){ |
| 777 |
v0 = vrp->sol_pool_cols[2*i*size/ISIZE + j]; |
| 778 |
v1 = vrp->sol_pool_cols[2*i*size/ISIZE + j + 1]; |
| 779 |
coef[j/2] = INDEX(v0, v1); |
| 780 |
} |
| 781 |
qsort_i(coef, size/ISIZE); |
| 782 |
|
| 783 |
send_int_array(&size, 1); |
| 784 |
send_char_array((char *)coef, size); |
| 785 |
} |
| 786 |
#endif |
| 787 |
|
| 788 |
return(USER_SUCCESS); |
| 789 |
} |
| 790 |
|
| 791 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 792 |
/*===========================================================================*/ |
| 793 |
|
| 794 |
/*===========================================================================*\ |
| 795 |
* Generally, this function is not needed but you might find some use |
| 796 |
* for it. Someone did :). |
| 797 |
\*===========================================================================*/ |
| 798 |
|
| 799 |
int user_process_own_messages(void *user, int msgtag) |
| 800 |
{ |
| 801 |
return(USER_DEFAULT); |
| 802 |
} |
| 803 |
|
| 804 |
/*===========================================================================*/ |
| 805 |
|
| 806 |
/*===========================================================================*\ |
| 807 |
* This is the user's chance to display the solution in whatever |
| 808 |
* manner desired. In my case, I can display a text version, which is |
| 809 |
* just a list of the customers on each route, or use the interactive |
| 810 |
* Graph Drawing application to graphically display the solution. |
| 811 |
\*===========================================================================*/ |
| 812 |
|
| 813 |
int user_display_solution(void *user, double lpetol, int varnum, int *indices, |
| 814 |
double *values, double objval) |
| 815 |
{ |
| 816 |
vrp_problem *vrp = (vrp_problem *)user; |
| 817 |
_node *tour = vrp->cur_tour->tour; |
| 818 |
int window = vrp->dg_id; |
| 819 |
|
| 820 |
int prev_node = 0, node, count = 0; |
| 821 |
|
| 822 |
if (!tour || vrp->cur_tour->cost > (int) objval){ /* Construct the tour */ |
| 823 |
int cur_vert = 0, prev_vert = 0, cur_route; |
| 824 |
elist *cur_route_start = NULL; |
| 825 |
edge *edge_data; |
| 826 |
double cost = 0; |
| 827 |
network *n = createnet(indices, values, varnum, lpetol, vrp->edges, |
| 828 |
vrp->demand, vrp->vertnum); |
| 829 |
vertex *verts = n->verts; |
| 830 |
|
| 831 |
if (!tour) |
| 832 |
tour = vrp->cur_tour->tour = (_node *) calloc (vrp->vertnum, |
| 833 |
sizeof(_node)); |
| 834 |
|
| 835 |
for (cur_route_start = verts[0].first, cur_route = 1, cost = 0, |
| 836 |
edge_data = cur_route_start->data; cur_route <= vrp->numroutes; |
| 837 |
cur_route++){ |
| 838 |
edge_data = cur_route_start->data; |
| 839 |
edge_data->scanned = TRUE; |
| 840 |
cur_vert = edge_data->v1; |
| 841 |
tour[prev_vert].next = cur_vert; |
| 842 |
tour[cur_vert].route = cur_route; |
| 843 |
prev_vert = 0; |
| 844 |
cost += vrp->dist.cost[INDEX(prev_vert, cur_vert)]; |
| 845 |
while (cur_vert){ |
| 846 |
if (verts[cur_vert].first->other_end != prev_vert){ |
| 847 |
prev_vert = cur_vert; |
| 848 |
edge_data = verts[cur_vert].first->data; |
| 849 |
cur_vert = verts[cur_vert].first->other_end; |
| 850 |
} |
| 851 |
else{ |
| 852 |
prev_vert = cur_vert; |
| 853 |
edge_data = verts[cur_vert].last->data; /*This statement could |
| 854 |
possibly be taken out |
| 855 |
to speed things up a |
| 856 |
bit */ |
| 857 |
cur_vert = verts[cur_vert].last->other_end; |
| 858 |
} |
| 859 |
tour[prev_vert].next = cur_vert; |
| 860 |
tour[cur_vert].route = cur_route; |
| 861 |
cost += vrp->dist.cost[INDEX(prev_vert, cur_vert)]; |
| 862 |
} |
| 863 |
edge_data->scanned = TRUE; |
| 864 |
|
| 865 |
while (cur_route_start->data->scanned){ |
| 866 |
if (!(cur_route_start = cur_route_start->next_edge)) break; |
| 867 |
} |
| 868 |
} |
| 869 |
free_net(n); |
| 870 |
} |
| 871 |
|
| 872 |
node = tour[0].next; |
| 873 |
|
| 874 |
if (tour[0].route == 1) |
| 875 |
printf("\n0 "); |
| 876 |
while (node != 0){ |
| 877 |
if (tour[prev_node].route != tour[node].route){ |
| 878 |
printf("\nRoute #%i: ", tour[node].route); |
| 879 |
count = 0; |
| 880 |
} |
| 881 |
printf("%i ", node); |
| 882 |
count++; |
| 883 |
if (count > 15){ |
| 884 |
printf("\n"); |
| 885 |
count = 0; |
| 886 |
} |
| 887 |
prev_node = node; |
| 888 |
node = tour[node].next; |
| 889 |
} |
| 890 |
printf("\n\n"); |
| 891 |
|
| 892 |
if (window){ |
| 893 |
char name[MAX_NAME_LENGTH] = {"feas_solution"}; |
| 894 |
disp_vrp_tour(window, TRUE, name, tour, vrp->vertnum, vrp->numroutes, |
| 895 |
CTOI_WAIT_FOR_CLICK_AND_REPORT); |
| 896 |
} |
| 897 |
|
| 898 |
#ifndef WIN32 |
| 899 |
if (window){ |
| 900 |
char name[MAX_NAME_LENGTH] = {"feas_solution"}; |
| 901 |
disp_vrp_tour(window, TRUE, name, tour, vrp->vertnum, vrp->numroutes, |
| 902 |
CTOI_WAIT_FOR_CLICK_AND_REPORT); |
| 903 |
} |
| 904 |
#endif |
| 905 |
|
| 906 |
return(USER_SUCCESS); |
| 907 |
} |
| 908 |
|
| 909 |
/*===========================================================================*/ |
| 910 |
|
| 911 |
/*===========================================================================*\ |
| 912 |
* This is a debugging feature which might |
| 913 |
* allow you to find out why a known feasible solution is being cut off. |
| 914 |
\*===========================================================================*/ |
| 915 |
|
| 916 |
int user_send_feas_sol(void *user, int *feas_sol_size, int **feas_sol) |
| 917 |
{ |
| 918 |
#ifdef TRACE_PATH |
| 919 |
vrp_problem *vrp = (vrp_problem *)user; |
| 920 |
|
| 921 |
*feas_sol_size = vrp->feas_sol_size; |
| 922 |
*feas_sol = vrp->feas_sol; |
| 923 |
#endif |
| 924 |
return(USER_SUCCESS); |
| 925 |
} |
| 926 |
|
| 927 |
/*===========================================================================*/ |
| 928 |
|
| 929 |
/*===========================================================================*\ |
| 930 |
* This function frees everything. |
| 931 |
\*===========================================================================*/ |
| 932 |
|
| 933 |
int user_free_master(void **user) |
| 934 |
{ |
| 935 |
vrp_problem *vrp = (vrp_problem *)(*user); |
| 936 |
|
| 937 |
if (vrp->cur_tour){ |
| 938 |
FREE(vrp->cur_tour->tour); |
| 939 |
FREE(vrp->cur_tour->route_info); |
| 940 |
FREE(vrp->cur_tour); |
| 941 |
} |
| 942 |
FREE(vrp->posy); |
| 943 |
FREE(vrp->posx); |
| 944 |
FREE(vrp->dist.coordx); |
| 945 |
FREE(vrp->dist.coordy); |
| 946 |
FREE(vrp->dist.coordz); |
| 947 |
#if !(defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP)) |
| 948 |
FREE(vrp->dist.cost); |
| 949 |
FREE(vrp->edges); |
| 950 |
FREE(vrp->demand); |
| 951 |
#endif |
| 952 |
#ifdef COMPILE_HEURS |
| 953 |
if (vrp->tours){ |
| 954 |
FREE(vrp->tours[0].tour); |
| 955 |
if (vrp->tourorder) |
| 956 |
for (i=0; i<=vrp->tournum; i++) |
| 957 |
FREE(vrp->tours[vrp->tourorder[i]].route_info); |
| 958 |
FREE(vrp->tours); |
| 959 |
} |
| 960 |
FREE(vrp->tourorder); |
| 961 |
if (vrp->lb){ |
| 962 |
FREE(vrp->lb->tree); |
| 963 |
FREE(vrp->lb->best_edges); |
| 964 |
FREE(vrp->lb); |
| 965 |
} |
| 966 |
FREE(vrp->par.rand_seed); |
| 967 |
#endif |
| 968 |
if (vrp->g){ |
| 969 |
FREE(vrp->g->edges); |
| 970 |
FREE(vrp->g); |
| 971 |
} |
| 972 |
#ifdef CHECK_CUT_VALIDITY |
| 973 |
FREE(vrp->feas_sol); |
| 974 |
#endif |
| 975 |
FREE(vrp->zero_vars); |
| 976 |
FREE(vrp); |
| 977 |
|
| 978 |
return(USER_SUCCESS); |
| 979 |
} |
| 980 |
|
| 981 |
/*===========================================================================*/ |
| 982 |
|
| 983 |
/*===========================================================================*\ |
| 984 |
* This function is used to lift the user created cuts during warm starting * |
| 985 |
\*===========================================================================*/ |
| 986 |
|
| 987 |
int user_ws_update_cuts (void *user, int *size, char **coef, double * rhs, |
| 988 |
char *sense, char type, int new_col_num, |
| 989 |
int change_type) |
| 990 |
{ |
| 991 |
return(USER_DEFAULT); |
| 992 |
} |
| 993 |
|
| 994 |
/*===========================================================================*/ |
| 995 |
|
| 996 |
|
| 997 |
|
| 998 |
|
| 999 |
|