| 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 |
/* Capacitated Network Routing Problems. */ |
| 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 <string.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_dg_params.h" |
| 29 |
#include "sym_master_u.h" |
| 30 |
|
| 31 |
/* CNRP include files */ |
| 32 |
#include "cnrp_const.h" |
| 33 |
#include "cnrp_types.h" |
| 34 |
#include "cnrp_io.h" |
| 35 |
#include "compute_cost.h" |
| 36 |
#include "cnrp_master_functions.h" |
| 37 |
#include "cnrp_dg_functions.h" |
| 38 |
#include "cnrp_macros.h" |
| 39 |
#include "small_graph.h" |
| 40 |
#include "network.h" |
| 41 |
#ifdef COMPILE_IN_TM |
| 42 |
#ifdef COMPILE_IN_LP |
| 43 |
#include "cnrp_lp.h" |
| 44 |
#ifdef COMPILE_IN_CG |
| 45 |
#include "cnrp_cg.h" |
| 46 |
#endif |
| 47 |
#ifdef COMPILE_IN_CP |
| 48 |
#include "cnrp_cp.h" |
| 49 |
#endif |
| 50 |
#endif |
| 51 |
#endif |
| 52 |
|
| 53 |
/*===========================================================================*/ |
| 54 |
|
| 55 |
/*===========================================================================*\ |
| 56 |
* This file contains the user-written functions for the master process. |
| 57 |
\*===========================================================================*/ |
| 58 |
|
| 59 |
void user_usage(void){ |
| 60 |
printf("master [ -HEP ] [ -S file ] [ -F file ] [ -B rule ]\n" |
| 61 |
"[ -V sel ] [ -K closest ] [ -N routes ] [ -C capacity ]\n" |
| 62 |
"[ -D level ] [ -M ] [ -X toggle ] [ -Y toggle ] \n" |
| 63 |
"[ -Z toggle ] [-G tau] \n" |
| 64 |
"\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" |
| 65 |
"\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\t%s\n\n", |
| 66 |
"-H: help", |
| 67 |
"-E: use sparse edge set", |
| 68 |
"-D level: verbosity level for displaying LP solutions", |
| 69 |
"-P type: specify problem type", |
| 70 |
"-S file: load sparse graph from 'file'", |
| 71 |
"-F file: problem data is in 'file'", |
| 72 |
"-B i: which candidates to check in strong branching", |
| 73 |
"-V i: how to construct the base set of variables", |
| 74 |
"-K k: use 'k' closest edges to build sparse graph", |
| 75 |
"-N n: use 'n' routes", |
| 76 |
"-M : use min cut subroutine", |
| 77 |
"-C c: use capacity 'c'", |
| 78 |
"-X t: toggles generation of X cuts", |
| 79 |
"-Y t: toggles generation of capacity cuts", |
| 80 |
"-Z t: toggles generation of tight capacity cuts", |
| 81 |
"-G t: set tau to 't'"); |
| 82 |
} |
| 83 |
|
| 84 |
/*===========================================================================*\ |
| 85 |
* Initialize user-defined data structures. In this case, I store all |
| 86 |
* problem-specific data such as the location of the customers, edge costs, |
| 87 |
* etc. in this data-structure. |
| 88 |
\*===========================================================================*/ |
| 89 |
|
| 90 |
int user_initialize(void **user) |
| 91 |
{ |
| 92 |
cnrp_problem *cnrp = (cnrp_problem *) calloc(1, sizeof(cnrp_problem)); |
| 93 |
|
| 94 |
*user = cnrp; |
| 95 |
|
| 96 |
return(USER_SUCCESS); |
| 97 |
} |
| 98 |
|
| 99 |
/*===========================================================================*/ |
| 100 |
|
| 101 |
/*===========================================================================*\ |
| 102 |
* In this function, I set up the user parameters. The first step is to cast |
| 103 |
* the void pointer in order to access my data. In the readparams() function, |
| 104 |
* I read in parameters from the parameter file given on the command line. |
| 105 |
\*===========================================================================*/ |
| 106 |
|
| 107 |
int user_readparams(void *user, char *filename, int argc, char **argv) |
| 108 |
{ |
| 109 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 110 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 111 |
#if 0 |
| 112 |
p->par.lp_par.problem_type = INTEGER_PROBLEM; |
| 113 |
strcpy(p->par.dg_par.source_path, "/home/tkr/BlackBox/DrawGraph/IGD_1.0/"); |
| 114 |
#endif |
| 115 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 116 |
|
| 117 |
cnrp_readparams(cnrp, filename, argc, argv); |
| 118 |
|
| 119 |
return(USER_SUCCESS); |
| 120 |
} |
| 121 |
|
| 122 |
/*===========================================================================*/ |
| 123 |
|
| 124 |
/*===========================================================================*\ |
| 125 |
* After I've read in the parameters, I can now read in the data file, whose |
| 126 |
* name was given in the parameter file. This file contains instance data. |
| 127 |
\*===========================================================================*/ |
| 128 |
|
| 129 |
int user_io(void *user) |
| 130 |
{ |
| 131 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 132 |
|
| 133 |
cnrp_io(cnrp, cnrp->par.infile); |
| 134 |
|
| 135 |
if (cnrp->par.use_small_graph == LOAD_SMALL_GRAPH){ |
| 136 |
read_small_graph(cnrp); |
| 137 |
} |
| 138 |
|
| 139 |
if (!cnrp->numroutes && cnrp->par.prob_type == VRP){ |
| 140 |
printf("\nError: Number of trucks not specified or computed " |
| 141 |
"for VRP\n\n"); |
| 142 |
exit(1); |
| 143 |
} |
| 144 |
|
| 145 |
if (cnrp->numroutes > 1){ |
| 146 |
printf("NUMBER OF TRUCKS: \t%i\n", cnrp->numroutes); |
| 147 |
printf("TIGHTNESS: \t\t%.2f\n", |
| 148 |
cnrp->demand[0]/(cnrp->capacity*(double)cnrp->numroutes)); |
| 149 |
} |
| 150 |
|
| 151 |
/* Selects the cheapest edges adjacent to each node for the base set */ |
| 152 |
|
| 153 |
if (cnrp->par.use_small_graph == SAVE_SMALL_GRAPH){ |
| 154 |
if (!cnrp->g) make_small_graph(cnrp, 0); |
| 155 |
save_small_graph(cnrp); |
| 156 |
}else if (!cnrp->g){ |
| 157 |
make_small_graph(cnrp, 0); |
| 158 |
} |
| 159 |
|
| 160 |
return(USER_SUCCESS); |
| 161 |
} |
| 162 |
|
| 163 |
/*===========================================================================*/ |
| 164 |
|
| 165 |
/*===========================================================================*\ |
| 166 |
* Here is where the heuristics are performed and an upper bound is calculated. |
| 167 |
* An upper bound can also be specified in the parameter file. The |
| 168 |
* other thing I do in this routine is build up a graph of the |
| 169 |
* cheapest k edges adjacent to the each node plus any edges chosen |
| 170 |
* during the heuristics to comprise my base set later. |
| 171 |
\*===========================================================================*/ |
| 172 |
|
| 173 |
int user_start_heurs(void *user, double *ub, double *ub_estimate) |
| 174 |
{ |
| 175 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 176 |
|
| 177 |
if (*ub > 0){ |
| 178 |
cnrp->cur_tour->cost = (int) (*ub); |
| 179 |
}else{ |
| 180 |
cnrp->cur_tour->cost = MAXINT; |
| 181 |
} |
| 182 |
|
| 183 |
cnrp->cur_tour->numroutes = cnrp->numroutes; |
| 184 |
|
| 185 |
if (cnrp->par.use_small_graph == LOAD_SMALL_GRAPH){ |
| 186 |
if (*ub <= 0 && cnrp->cur_tour->cost > 0) |
| 187 |
*ub = (int)(cnrp->cur_tour->cost); |
| 188 |
cnrp->numroutes = cnrp->cur_tour->numroutes; |
| 189 |
} |
| 190 |
|
| 191 |
#if 0 |
| 192 |
if(cnrp->par.prob_tpye == BPP) |
| 193 |
*ub = 1; |
| 194 |
#endif |
| 195 |
|
| 196 |
if (*ub > 0 && !(cnrp->par.prob_type == BPP)) |
| 197 |
printf("INITIAL UPPER BOUND: \t%i\n\n", (int)(*ub)); |
| 198 |
else if (!(cnrp->par.prob_type == BPP)) |
| 199 |
printf("INITIAL UPPER BOUND: \tNone\n\n"); |
| 200 |
else |
| 201 |
printf("\n\n"); |
| 202 |
|
| 203 |
return(USER_SUCCESS); |
| 204 |
} |
| 205 |
|
| 206 |
/*===========================================================================*/ |
| 207 |
|
| 208 |
/*===========================================================================*\ |
| 209 |
* If graph drawing will be use, the user must initialize the drawing |
| 210 |
* window here. |
| 211 |
\*===========================================================================*/ |
| 212 |
|
| 213 |
int user_init_draw_graph(void *user, int dg_id) |
| 214 |
{ |
| 215 |
#ifndef WIN32 /* FIXME : None of this works in Windows */ |
| 216 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 217 |
int s_bufid; |
| 218 |
|
| 219 |
if (!(cnrp->posx && cnrp->posy)) return(USER_SUCCESS); |
| 220 |
if ( (cnrp->dg_id = dg_id) ){ |
| 221 |
int i, zero = 0, eight = 0x08; |
| 222 |
char node_place[MAX_NAME_LENGTH] = {"node_placement"}; |
| 223 |
char weight[5]; |
| 224 |
int *posx = cnrp->posx, *posy = cnrp->posy; |
| 225 |
int minx=MAXINT, miny=MAXINT, maxx=-MAXINT, maxy=-MAXINT, xx, yy; |
| 226 |
int width = 1000, height = 700; |
| 227 |
#if 0 |
| 228 |
int width=p->par.dg_par.canvas_width, height=p->par.dg_par.canvas_height; |
| 229 |
#endif |
| 230 |
double mult; |
| 231 |
|
| 232 |
for (i = cnrp->vertnum - 1; i >= 0; i--){ |
| 233 |
if (posx[i] < minx) minx = posx[i]; |
| 234 |
if (posx[i] > maxx) maxx = posx[i]; |
| 235 |
if (posy[i] < miny) miny = posy[i]; |
| 236 |
if (posy[i] > maxy) maxy = posy[i]; |
| 237 |
} |
| 238 |
xx = maxx - minx; |
| 239 |
yy = maxy - miny; |
| 240 |
mult = (int) MIN((width - 20.0)/xx, (height-20.0)/yy); |
| 241 |
width = (int) (xx * mult + 30); |
| 242 |
height = (int) (yy * mult + 30); |
| 243 |
for (i = cnrp->vertnum-1; i >= 0; i--){ |
| 244 |
posx[i] = (int) ((posx[i] - minx) * mult + 10); |
| 245 |
posy[i] = (int) ((maxy - posy[i]) * mult + 10); |
| 246 |
} |
| 247 |
|
| 248 |
init_window(dg_id, node_place, width, height); |
| 249 |
/* Now pack the placement of the nodes of the graph */ |
| 250 |
s_bufid = init_send(DataInPlace); |
| 251 |
send_str(node_place); |
| 252 |
send_int_array(&cnrp->vertnum, 1); |
| 253 |
for (i = 0; i < cnrp->vertnum; i++){ |
| 254 |
send_int_array(&i, 1); |
| 255 |
send_int_array(posx + i, 1); |
| 256 |
send_int_array(posy + i, 1); |
| 257 |
send_int_array(&eight, 1); |
| 258 |
sprintf(weight, "%i", (int)(cnrp->demand[i])); |
| 259 |
send_str(weight); |
| 260 |
} |
| 261 |
/* No edges are passed to the default graph */ |
| 262 |
send_int_array(&zero, 1); |
| 263 |
send_msg(dg_id, CTOI_SET_GRAPH); |
| 264 |
freebuf(s_bufid); |
| 265 |
|
| 266 |
display_graph(dg_id, node_place); |
| 267 |
} |
| 268 |
#endif |
| 269 |
|
| 270 |
return(USER_SUCCESS); |
| 271 |
} |
| 272 |
|
| 273 |
/*===========================================================================*/ |
| 274 |
|
| 275 |
/*===========================================================================*\ |
| 276 |
* In this routine, I build the initial edge set for the root. There are |
| 277 |
* several things going on here. First, there is a user-defined parameter |
| 278 |
* defining whether or not to just go ahead and add all variables to the |
| 279 |
* problem up front (cnrp->par.add_all_edges). Currently, this seems to be the |
| 280 |
* best option since the problems are small anyway. Further, I am doing some |
| 281 |
* preprocessing here by eliminating edges for which the sum of the demands of |
| 282 |
* their endpoints is greater than the capacity since these edges cannot |
| 283 |
* be in any feasible solution. |
| 284 |
* |
| 285 |
* Notice that there are several options programmed for which set |
| 286 |
* of edges should be in the base set. The |
| 287 |
* base constraints are just the degree constraints from the IP |
| 288 |
* formulation. These do not have to be specified explicitly, just the |
| 289 |
* number of them given. |
| 290 |
\*===========================================================================*/ |
| 291 |
|
| 292 |
int user_initialize_root_node(void *user, int *basevarnum, int **basevars, |
| 293 |
int *basecutnum, int *extravarnum, |
| 294 |
int **extravars, char *obj_sense, |
| 295 |
double *obj_offset, char ***colnames, |
| 296 |
int *colgen_strat) |
| 297 |
{ |
| 298 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 299 |
|
| 300 |
*basevarnum = cnrp->basevarnum; |
| 301 |
*basevars = cnrp->basevars; |
| 302 |
*extravarnum = cnrp->extravarnum; |
| 303 |
*extravars = cnrp->extravars; |
| 304 |
*basecutnum = cnrp->basecutnum; |
| 305 |
|
| 306 |
if (!cnrp->par.colgen_strat[0]){ |
| 307 |
if (cnrp->par.add_all_edges || |
| 308 |
cnrp->par.base_variable_selection == SOME_ARE_BASE){ |
| 309 |
colgen_strat[0]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD | |
| 310 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 311 |
}else{ |
| 312 |
colgen_strat[0] = (FATHOM__DO_NOT_GENERATE_COLS__SEND | |
| 313 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 314 |
} |
| 315 |
}else{ |
| 316 |
colgen_strat[0] = cnrp->par.colgen_strat[0]; |
| 317 |
} |
| 318 |
if (!cnrp->par.colgen_strat[1]){ |
| 319 |
if (cnrp->par.add_all_edges || |
| 320 |
cnrp->par.base_variable_selection == SOME_ARE_BASE){ |
| 321 |
colgen_strat[1]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD | |
| 322 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 323 |
}else{ |
| 324 |
colgen_strat[1] = (FATHOM__GENERATE_COLS__RESOLVE | |
| 325 |
BEFORE_BRANCH__DO_NOT_GENERATE_COLS); |
| 326 |
} |
| 327 |
}else{ |
| 328 |
colgen_strat[1] = cnrp->par.colgen_strat[1]; |
| 329 |
} |
| 330 |
|
| 331 |
return(USER_SUCCESS); |
| 332 |
} |
| 333 |
|
| 334 |
/*===========================================================================*/ |
| 335 |
|
| 336 |
/*===========================================================================*\ |
| 337 |
* In my case, a feasible solution is specified most compactly by |
| 338 |
* essentially a permutation of the customers along with routes numbers, |
| 339 |
* specifying the order of the customers on their routes. This is just |
| 340 |
* sent as a character array which then gets cast to an array of |
| 341 |
* structures, one for each customers specifying the route number and |
| 342 |
* the next customer on the route. |
| 343 |
\*===========================================================================*/ |
| 344 |
|
| 345 |
int user_receive_feasible_solution(void *user, int msgtag, double cost, |
| 346 |
int numvars, int *indices, double *values) |
| 347 |
{ |
| 348 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 349 |
|
| 350 |
if (cnrp->par.prob_type == TSP || cnrp->par.prob_type == VRP || |
| 351 |
cnrp->par.prob_type == BPP) |
| 352 |
receive_char_array((char *)cnrp->cur_tour->tour, |
| 353 |
cnrp->vertnum*sizeof(_node)); |
| 354 |
else |
| 355 |
receive_int_array(cnrp->cur_sol_tree, cnrp->vertnum); |
| 356 |
|
| 357 |
return(USER_SUCCESS); |
| 358 |
} |
| 359 |
|
| 360 |
/*===========================================================================*/ |
| 361 |
|
| 362 |
/*===========================================================================*\ |
| 363 |
* Here, we send the necessary data to the LP process. Notice that |
| 364 |
* there are two cases to deal with. If the LP or the TM are running |
| 365 |
* as separate processes, then we have to send the data by |
| 366 |
* message-passing. Otherwise, we can allocate the user-defined LP data |
| 367 |
* structure here and simply copy the necessary information. This is the |
| 368 |
* only place the user has to sorry about this distinction between |
| 369 |
* configurations. |
| 370 |
\*===========================================================================*/ |
| 371 |
|
| 372 |
int user_send_lp_data(void *user, void **user_lp) |
| 373 |
{ |
| 374 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 375 |
|
| 376 |
#if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) |
| 377 |
/* This is the case when we are copying data directly because |
| 378 |
the LP is not running separately. This code should be virtually |
| 379 |
identical to that of user_receive_lp_data() in the LP process.*/ |
| 380 |
|
| 381 |
cnrp_spec *cnrp_lp = (cnrp_spec *) calloc(1, sizeof(cnrp_spec)); |
| 382 |
int zero_varnum = cnrp->zero_varnum; |
| 383 |
int *zero_vars = cnrp->zero_vars; |
| 384 |
int vertnum, i, j, k, l; |
| 385 |
|
| 386 |
*user_lp = (void *)cnrp_lp; |
| 387 |
|
| 388 |
cnrp_lp->par = cnrp->lp_par; |
| 389 |
cnrp_lp->window = cnrp->dg_id; |
| 390 |
cnrp_lp->numroutes = cnrp->numroutes; |
| 391 |
vertnum = cnrp_lp->vertnum = cnrp->vertnum; |
| 392 |
cnrp_lp->edges = cnrp->edges; |
| 393 |
cnrp_lp->demand = cnrp->demand; |
| 394 |
cnrp_lp->capacity = cnrp->capacity; |
| 395 |
cnrp_lp->costs = cnrp->dist.cost; |
| 396 |
cnrp_lp->utopia_fixed = cnrp->utopia_fixed; |
| 397 |
cnrp_lp->utopia_variable = cnrp->utopia_variable; |
| 398 |
cnrp_lp->variable_cost = cnrp_lp->fixed_cost = MAXDOUBLE; |
| 399 |
cnrp_lp->ub = cnrp->ub; |
| 400 |
|
| 401 |
if (cnrp->par.prob_type == VRP || cnrp->par.prob_type == TSP || |
| 402 |
cnrp->par.prob_type == BPP){ |
| 403 |
cnrp_lp->cur_sol = (_node *) calloc (cnrp->vertnum, sizeof(_node)); |
| 404 |
}else{ |
| 405 |
cnrp_lp->cur_sol_tree = (int *) calloc (cnrp->vertnum - 1, ISIZE); |
| 406 |
} |
| 407 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 408 |
if (cnrp_lp->window){ |
| 409 |
copy_node_set(cnrp_lp->window, TRUE, (char *)"Weighted solution"); |
| 410 |
copy_node_set(cnrp_lp->window, TRUE, (char *)"Flow solution"); |
| 411 |
} |
| 412 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 413 |
|
| 414 |
#else |
| 415 |
/* Here, we send that data using message passing and the rest is |
| 416 |
done in user_receive_lp_data() in the LP process */ |
| 417 |
|
| 418 |
send_char_array((char *)(&cnrp->lp_par), sizeof(cnrp_lp_params)); |
| 419 |
send_int_array(&cnrp->dg_id, 1); |
| 420 |
send_int_array(&cnrp->numroutes, 1); |
| 421 |
send_int_array(&cnrp->vertnum, 1); |
| 422 |
send_dbl_array(cnrp->demand, cnrp->vertnum); |
| 423 |
send_dbl_array(&cnrp->capacity, 1); |
| 424 |
send_int_array(cnrp->dist.cost, cnrp->edgenum); |
| 425 |
send_int_array(&cnrp->zero_varnum, 1); |
| 426 |
if (cnrp->zero_varnum){ |
| 427 |
send_int_array(cnrp->zero_vars, cnrp->zero_varnum); |
| 428 |
} |
| 429 |
send_dbl_array(&cnrp->utopia_fixed, 1); |
| 430 |
send_dbl_array(&cnrp->utopia_variable, 1); |
| 431 |
send_dbl_array(&cnrp->ub, 1); |
| 432 |
#endif |
| 433 |
|
| 434 |
return(USER_SUCCESS); |
| 435 |
} |
| 436 |
|
| 437 |
/*===========================================================================*/ |
| 438 |
|
| 439 |
/*===========================================================================*\ |
| 440 |
* Here, we send the necessary data to the CG process. Notice that |
| 441 |
* there are two cases to deal with. If the CG, LP, or the TM are running |
| 442 |
* as separate processes, then we have to send the data by |
| 443 |
* message-passing. Otherwise, we can allocate the user-defined LP data |
| 444 |
* structure here and simply copy the necessary information. This is the |
| 445 |
* only place the user has to sorry about this distinction between |
| 446 |
* configurations. |
| 447 |
\*===========================================================================*/ |
| 448 |
|
| 449 |
int user_send_cg_data(void *user, void **user_cg) |
| 450 |
{ |
| 451 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 452 |
|
| 453 |
#if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CG) |
| 454 |
/* This is is the case when we are copying data directly because |
| 455 |
the CG is not running separately. This code should be virtually |
| 456 |
identical to that of user_receive_cg_data() in the CG process.*/ |
| 457 |
|
| 458 |
cg_cnrp_spec *cnrp_cg = (cg_cnrp_spec *) malloc (sizeof(cg_cnrp_spec)); |
| 459 |
int edgenum, vertnum, i, j, k; |
| 460 |
|
| 461 |
*user_cg = (void *)cnrp_cg; |
| 462 |
|
| 463 |
cnrp_cg->par = cnrp->cg_par; |
| 464 |
cnrp_cg->numroutes = cnrp->numroutes; |
| 465 |
vertnum = cnrp_cg->vertnum = cnrp->vertnum; |
| 466 |
cnrp_cg->demand = cnrp->demand; |
| 467 |
cnrp_cg->capacity = cnrp->capacity; |
| 468 |
cnrp_cg->dg_id = cnrp->dg_id; |
| 469 |
|
| 470 |
edgenum = cnrp->vertnum*(cnrp->vertnum-1)/2; |
| 471 |
|
| 472 |
cnrp_cg->in_set = (char *) calloc(cnrp->vertnum, sizeof(char)); |
| 473 |
cnrp_cg->ref = (int *) malloc(cnrp->vertnum*sizeof(int)); |
| 474 |
cnrp_cg->new_demand = (double *) malloc(cnrp->vertnum*sizeof(double)); |
| 475 |
cnrp_cg->cut_val = (double *) calloc(cnrp->vertnum, sizeof(double)); |
| 476 |
cnrp_cg->cut_list = (char *) malloc(((cnrp->vertnum >> DELETE_POWER)+1)* |
| 477 |
(cnrp->cg_par.max_num_cuts_in_shrink + 1)* |
| 478 |
sizeof(char)); |
| 479 |
|
| 480 |
cnrp_cg->edges = (int *) calloc (2*edgenum, sizeof(int)); |
| 481 |
|
| 482 |
/*create the edge list (we assume a complete graph)*/ |
| 483 |
for (i = 1, k = 0; i < vertnum; i++){ |
| 484 |
for (j = 0; j < i; j++){ |
| 485 |
cnrp_cg->edges[2*k] = j; |
| 486 |
cnrp_cg->edges[2*k+1] = i; |
| 487 |
k++; |
| 488 |
} |
| 489 |
} |
| 490 |
|
| 491 |
#ifdef CHECK_CUT_VALIDITY |
| 492 |
if ((cnrp_cg->feas_sol_size = cnrp->feas_sol_size)){ |
| 493 |
cnrp_cg->feas_sol = cnrp->feas_sol; |
| 494 |
} |
| 495 |
#endif |
| 496 |
#else |
| 497 |
/* Here, we send that data using message passing and the rest is |
| 498 |
done in user_receive_cg_data() in the CG process */ |
| 499 |
|
| 500 |
send_char_array((char *)&cnrp->cg_par, sizeof(cnrp_cg_params)); |
| 501 |
send_int_array(&cnrp->dg_id, 1); |
| 502 |
send_int_array(&cnrp->numroutes, 1); |
| 503 |
send_int_array(&cnrp->vertnum, 1); |
| 504 |
send_dbl_array(cnrp->demand, cnrp->vertnum); |
| 505 |
send_dbl_array(&cnrp->capacity, 1); |
| 506 |
#ifdef CHECK_CUT_VALIDITY |
| 507 |
send_int_array(&cnrp->feas_sol_size, 1); |
| 508 |
if (cnrp->feas_sol_size){ |
| 509 |
send_int_array(cnrp->feas_sol, cnrp->feas_sol_size); |
| 510 |
} |
| 511 |
#endif |
| 512 |
#endif |
| 513 |
|
| 514 |
return(USER_SUCCESS); |
| 515 |
} |
| 516 |
|
| 517 |
/*===========================================================================*/ |
| 518 |
|
| 519 |
/*===========================================================================*\ |
| 520 |
* Here, we send the necessary data to the CP process. Notice that |
| 521 |
* there are two cases to deal with. If the CP, LP, or the TM are running |
| 522 |
* as separate processes, then we have to send the data by |
| 523 |
* message-passing. Otherwise, we can allocate the user-defined LP data |
| 524 |
* structure here and simply copy the necessary information. This is the |
| 525 |
* only place the user has to sorry about this distinction between |
| 526 |
* configurations. |
| 527 |
\*===========================================================================*/ |
| 528 |
|
| 529 |
int user_send_cp_data(void *user, void **user_cp) |
| 530 |
{ |
| 531 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 532 |
|
| 533 |
#if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CP) |
| 534 |
/* This is is the case when we are copying data directly because |
| 535 |
the LP is not running separately. This code should be virtually |
| 536 |
identical to that of user_receive_cp_data() in the CP process.*/ |
| 537 |
|
| 538 |
cnrp_spec_cp *cnrp_cp = (cnrp_spec_cp *) malloc (sizeof(cnrp_spec_cp)); |
| 539 |
int i, j, k; |
| 540 |
|
| 541 |
cnrp_cp->par = cnrp->cp_par; |
| 542 |
cnrp_cp->vertnum = cnrp->vertnum; |
| 543 |
cnrp_cp->capacity = cnrp->capacity; |
| 544 |
cnrp_cp->demand = (double *) malloc(cnrp->vertnum * DSIZE); |
| 545 |
memcpy((char *)cnrp_cp->demand, (char *) cnrp->demand, cnrp->vertnum * DSIZE); |
| 546 |
|
| 547 |
*user_cp = (void *)cnrp_cp; |
| 548 |
|
| 549 |
cnrp_cp->edgenum = |
| 550 |
cnrp_cp->vertnum*(cnrp_cp->vertnum-1)/2 + cnrp_cp->vertnum-1; |
| 551 |
cnrp_cp->edges = (int *) calloc ((int)2*cnrp_cp->edgenum, sizeof(int)); |
| 552 |
|
| 553 |
/* create the edge list (we assume a complete graph) */ |
| 554 |
for (i = 1, k = 0; i < cnrp_cp->vertnum; i++){ |
| 555 |
for (j = 0; j < i; j++){ |
| 556 |
cnrp_cp->edges[2*k] = j; |
| 557 |
cnrp_cp->edges[2*k+1] = i; |
| 558 |
k++; |
| 559 |
} |
| 560 |
} |
| 561 |
|
| 562 |
/* now add the duplicate copies of the depot edges to allow for |
| 563 |
routes with one customer */ |
| 564 |
for (i = 1; i < cnrp_cp->vertnum; i++){ |
| 565 |
cnrp_cp->edges[2*k] = 0; |
| 566 |
cnrp_cp->edges[2*k+1] = i; |
| 567 |
k++; |
| 568 |
} |
| 569 |
#else |
| 570 |
/* Here, we send that data using message passing and the rest is |
| 571 |
done in user_receive_cp_data() in the CP process */ |
| 572 |
|
| 573 |
send_int_array(&cnrp->vertnum, 1); |
| 574 |
send_dbl_array(&cnrp->capacity, 1); |
| 575 |
send_dbl_array(cnrp->demand, cnrp->vertnum); |
| 576 |
|
| 577 |
#endif |
| 578 |
|
| 579 |
return(USER_SUCCESS); |
| 580 |
} |
| 581 |
|
| 582 |
/*__BEGIN_EXPERIMENTAL_SECTION__*/ |
| 583 |
/*===========================================================================*/ |
| 584 |
|
| 585 |
int user_send_sp_data(void *user) |
| 586 |
{ |
| 587 |
return(USER_SUCCESS); |
| 588 |
} |
| 589 |
|
| 590 |
/*___END_EXPERIMENTAL_SECTION___*/ |
| 591 |
/*===========================================================================*/ |
| 592 |
|
| 593 |
/*===========================================================================*\ |
| 594 |
* Generally, this function is not needed but you might find some use |
| 595 |
* for it. Someone did :). |
| 596 |
\*===========================================================================*/ |
| 597 |
|
| 598 |
int user_process_own_messages(void *user, int msgtag) |
| 599 |
{ |
| 600 |
return(USER_DEFAULT); |
| 601 |
} |
| 602 |
|
| 603 |
/*===========================================================================*/ |
| 604 |
|
| 605 |
/*===========================================================================*\ |
| 606 |
* This is the user's chance to display the solution in whatever |
| 607 |
* manner desired. In my case, I can display a text version, which is |
| 608 |
* just a list of the customers on each route, or use the interactive |
| 609 |
* Graph Drawing application to graphically display the solution. |
| 610 |
\*===========================================================================*/ |
| 611 |
|
| 612 |
int user_display_solution(void *user, double lpetol, int varnum, int *indices, |
| 613 |
double *values, double objval) |
| 614 |
{ |
| 615 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 616 |
_node *tour = cnrp->cur_tour->tour; |
| 617 |
int *tree = cnrp->cur_sol_tree, node, prev_node; |
| 618 |
int cur_vert = 0, prev_vert = 0, cur_route, i, count; |
| 619 |
elist *cur_route_start = NULL; |
| 620 |
edge *edge_data; |
| 621 |
vertex *verts; |
| 622 |
double fixed_cost = 0.0, variable_cost = 0.0; |
| 623 |
int window = cnrp->dg_id; |
| 624 |
int vertnum = cnrp->vertnum, v0, v1; |
| 625 |
int total_edgenum = vertnum*(vertnum-1)/2; |
| 626 |
network *n; |
| 627 |
|
| 628 |
/* FIXME: This is UGLY! */ |
| 629 |
#if (defined(MULTI_CRITERIA) && defined(FIND_NONDOMINATED_SOLUTIONS)) && \ |
| 630 |
(defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP)) && 0 |
| 631 |
|
| 632 |
problem *p = get_problem_ptr(FALSE); |
| 633 |
cnrp_spec *cnrp_lp = (cnrp_spec *) p->tm->lpp[0]->user; |
| 634 |
|
| 635 |
cnrp->fixed_cost = cnrp_lp->fixed_cost; |
| 636 |
cnrp->variable_cost = cnrp_lp->variable_cost; |
| 637 |
|
| 638 |
tour = cnrp_lp->cur_sol; |
| 639 |
tree = cnrp_lp->cur_sol_tree; |
| 640 |
printf("\nSolution Found:\n"); |
| 641 |
#ifdef ADD_FLOW_VARS |
| 642 |
printf("Solution Fixed Cost: %.1f\n", cnrp->fixed_cost); |
| 643 |
printf("Solution Variable Cost: %.1f\n", cnrp->variable_cost); |
| 644 |
#else |
| 645 |
printf("Solution Cost: %.0f\n", fixed_cost); |
| 646 |
#endif |
| 647 |
#else |
| 648 |
printf("\nSolution Found:\n"); |
| 649 |
#endif |
| 650 |
|
| 651 |
#if 0 |
| 652 |
if (tour){ |
| 653 |
node = tour[0].next; |
| 654 |
if (tour[0].route == 1) |
| 655 |
printf("\n0 "); |
| 656 |
while (node != 0){ |
| 657 |
if (tour[prev_node].route != tour[node].route){ |
| 658 |
printf("\nRoute #%i: ", tour[node].route); |
| 659 |
count = 0; |
| 660 |
} |
| 661 |
printf("%i ", node); |
| 662 |
count++; |
| 663 |
if (count > 15){ |
| 664 |
printf("\n"); |
| 665 |
count = 0; |
| 666 |
} |
| 667 |
prev_node = node; |
| 668 |
node = tour[node].next; |
| 669 |
} |
| 670 |
printf("\n\n"); |
| 671 |
|
| 672 |
if (window){ |
| 673 |
char name[MAX_NAME_LENGTH] = {"feas_solution"}; |
| 674 |
disp_vrp_tour(window, TRUE, name, tour, cnrp->vertnum, |
| 675 |
cnrp->numroutes, CTOI_WAIT_FOR_CLICK_AND_REPORT); |
| 676 |
} |
| 677 |
return(USER_SUCCESS); |
| 678 |
} |
| 679 |
|
| 680 |
if (tree){ |
| 681 |
printf("Edge List:\n"); |
| 682 |
for (i = 0; i < vertnum - 1; i++){ |
| 683 |
BOTH_ENDS(tree[i], &v0, &v1); |
| 684 |
printf("%i %i\n", v1, v0); |
| 685 |
} |
| 686 |
printf("\n\n"); |
| 687 |
|
| 688 |
if (window){ |
| 689 |
char name[MAX_NAME_LENGTH] = {"feas_solution"}; |
| 690 |
copy_node_set(window, TRUE, name); |
| 691 |
draw_edge_set_from_userind(window, name, vertnum - 1, tree); |
| 692 |
display_graph(window, name); |
| 693 |
wait_for_click(window, name, CTOI_WAIT_FOR_CLICK_NO_REPORT); |
| 694 |
} |
| 695 |
return(USER_SUCCESS); |
| 696 |
} |
| 697 |
#endif |
| 698 |
|
| 699 |
/*Otherwise, construct the solution from scratch*/ |
| 700 |
|
| 701 |
#ifdef ADD_FLOW_VARS |
| 702 |
n = create_flow_net(indices, values, varnum, lpetol, cnrp->edges, |
| 703 |
cnrp->demand, vertnum); |
| 704 |
#else |
| 705 |
n = create_net(indices, values, varnum, lpetol, cnrp->edges, cnrp->demand, |
| 706 |
vertnum); |
| 707 |
#endif |
| 708 |
|
| 709 |
for (i = 0; i < n->edgenum; i++){ |
| 710 |
if (n->edges[i].weight > 1 - lpetol){ |
| 711 |
fixed_cost += cnrp->dist.cost[INDEX(n->edges[i].v0, n->edges[i].v1)]; |
| 712 |
} |
| 713 |
#ifdef ADD_FLOW_VARS |
| 714 |
variable_cost += (n->edges[i].flow1+n->edges[i].flow2)* |
| 715 |
cnrp->dist.cost[INDEX(n->edges[i].v0, n->edges[i].v1)]; |
| 716 |
#endif |
| 717 |
} |
| 718 |
cnrp->fixed_cost = fixed_cost; |
| 719 |
cnrp->variable_cost = variable_cost; |
| 720 |
#if defined(ADD_FLOW_VARS) && defined(MULTI_CRITERIA) |
| 721 |
printf("Solution Fixed Cost: %.1f\n", fixed_cost); |
| 722 |
printf("Solution Variable Cost: %.1f\n", variable_cost); |
| 723 |
#else |
| 724 |
printf("Solution Cost: %.0f\n", fixed_cost); |
| 725 |
#endif |
| 726 |
|
| 727 |
if (cnrp->par.prob_type == TSP || cnrp->par.prob_type == VRP || |
| 728 |
cnrp->par.prob_type == BPP){ |
| 729 |
|
| 730 |
verts = n->verts; |
| 731 |
|
| 732 |
/*construct the tour corresponding to this solution vector*/ |
| 733 |
for (cur_route_start = verts[0].first, cur_route = 1, |
| 734 |
edge_data = cur_route_start->data; cur_route <= cnrp->numroutes; |
| 735 |
cur_route++){ |
| 736 |
edge_data = cur_route_start->data; |
| 737 |
edge_data->scanned = TRUE; |
| 738 |
cur_vert = edge_data->v1; |
| 739 |
tour[prev_vert].next = cur_vert; |
| 740 |
tour[cur_vert].route = cur_route; |
| 741 |
prev_vert = 0; |
| 742 |
while (cur_vert){ |
| 743 |
if (verts[cur_vert].first->other_end != prev_vert){ |
| 744 |
prev_vert = cur_vert; |
| 745 |
edge_data = verts[cur_vert].first->data; |
| 746 |
cur_vert = verts[cur_vert].first->other_end; |
| 747 |
} |
| 748 |
else{ |
| 749 |
prev_vert = cur_vert; |
| 750 |
edge_data = verts[cur_vert].last->data; /*This statement |
| 751 |
could possibly |
| 752 |
be taken out to speed |
| 753 |
things up a bit*/ |
| 754 |
cur_vert = verts[cur_vert].last->other_end; |
| 755 |
} |
| 756 |
tour[prev_vert].next = cur_vert; |
| 757 |
tour[cur_vert].route = cur_route; |
| 758 |
} |
| 759 |
edge_data->scanned = TRUE; |
| 760 |
|
| 761 |
while (cur_route_start->data->scanned){ |
| 762 |
if (!(cur_route_start = cur_route_start->next_edge)) break; |
| 763 |
} |
| 764 |
} |
| 765 |
|
| 766 |
/* Display the solution */ |
| 767 |
|
| 768 |
cur_vert = tour[0].next; |
| 769 |
|
| 770 |
if (tour[0].route == 1) |
| 771 |
printf("\n0 "); |
| 772 |
while (cur_vert != 0){ |
| 773 |
if (tour[prev_vert].route != tour[cur_vert].route){ |
| 774 |
printf("\nRoute #%i: ", tour[cur_vert].route); |
| 775 |
count = 0; |
| 776 |
} |
| 777 |
printf("%i ", cur_vert); |
| 778 |
count++; |
| 779 |
if (count > 15){ |
| 780 |
printf("\n"); |
| 781 |
count = 0; |
| 782 |
} |
| 783 |
prev_vert = cur_vert; |
| 784 |
cur_vert = tour[cur_vert].next; |
| 785 |
} |
| 786 |
printf("\n"); |
| 787 |
}else{ |
| 788 |
|
| 789 |
for (i = 0; i < n->edgenum; i++){ |
| 790 |
cnrp->cur_sol_tree[i] = INDEX(n->edges[i].v0, n->edges[i].v1); |
| 791 |
} |
| 792 |
|
| 793 |
/* Display the solution */ |
| 794 |
|
| 795 |
for (i = 0; i < n->edgenum; i++){ |
| 796 |
printf("%i %i\n", n->edges[i].v0, n->edges[i].v1); |
| 797 |
} |
| 798 |
printf("\n"); |
| 799 |
} |
| 800 |
free_net(n); |
| 801 |
|
| 802 |
return(USER_SUCCESS); |
| 803 |
} |
| 804 |
|
| 805 |
/*===========================================================================*/ |
| 806 |
|
| 807 |
/*===========================================================================*\ |
| 808 |
* This is a debugging feature which might |
| 809 |
* allow you to find out why a known feasible solution is being cut off. |
| 810 |
\*===========================================================================*/ |
| 811 |
|
| 812 |
int user_send_feas_sol(void *user, int *feas_sol_size, int **feas_sol) |
| 813 |
{ |
| 814 |
#ifdef TRACE_PATH |
| 815 |
cnrp_problem *cnrp = (cnrp_problem *)user; |
| 816 |
|
| 817 |
*feas_sol_size = cnrp->feas_sol_size; |
| 818 |
*feas_sol = cnrp->feas_sol; |
| 819 |
#endif |
| 820 |
return(USER_SUCCESS); |
| 821 |
} |
| 822 |
|
| 823 |
/*===========================================================================*/ |
| 824 |
|
| 825 |
/*===========================================================================*\ |
| 826 |
* This function frees everything. |
| 827 |
\*===========================================================================*/ |
| 828 |
|
| 829 |
int user_free_master(void **user) |
| 830 |
{ |
| 831 |
cnrp_problem *cnrp = (cnrp_problem *)(*user); |
| 832 |
|
| 833 |
if (cnrp->cur_tour){ |
| 834 |
FREE(cnrp->cur_tour->tour); |
| 835 |
FREE(cnrp->cur_tour->route_info); |
| 836 |
FREE(cnrp->cur_tour); |
| 837 |
} |
| 838 |
FREE(cnrp->cur_sol_tree); |
| 839 |
FREE(cnrp->posy); |
| 840 |
FREE(cnrp->posx); |
| 841 |
FREE(cnrp->dist.coordx); |
| 842 |
FREE(cnrp->dist.coordy); |
| 843 |
FREE(cnrp->dist.coordz); |
| 844 |
FREE(cnrp->dist.cost); |
| 845 |
FREE(cnrp->edges); |
| 846 |
FREE(cnrp->demand); |
| 847 |
if (cnrp->g){ |
| 848 |
FREE(cnrp->g->edges); |
| 849 |
FREE(cnrp->g); |
| 850 |
} |
| 851 |
#ifdef CHECK_CUT_VALIDITY |
| 852 |
FREE(cnrp->feas_sol); |
| 853 |
#endif |
| 854 |
FREE(cnrp->zero_vars); |
| 855 |
FREE(cnrp); |
| 856 |
|
| 857 |
return(USER_SUCCESS); |
| 858 |
} |
| 859 |
/*===========================================================================*/ |
| 860 |
|
| 861 |
/*===========================================================================*\ |
| 862 |
* This function is used to lift the user created cuts during warm starting * |
| 863 |
\*===========================================================================*/ |
| 864 |
|
| 865 |
int user_ws_update_cuts (void *user, int *size, char **coef, double * rhs, |
| 866 |
char *sense, char type, int new_col_num, |
| 867 |
int change_type) |
| 868 |
{ |
| 869 |
return(USER_DEFAULT); |
| 870 |
} |
| 871 |
|
| 872 |
/*===========================================================================*/ |
| 873 |
|
| 874 |
|
| 875 |
|
| 876 |
|
| 877 |
|
| 878 |
|
| 879 |
|