/*===========================================================================*/ /* */ /* This file is part of a demonstration application for use with the */ /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ /* Capacitated Network Routing Problems. */ /* */ /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */ /* */ /* This application was developed by Ted Ralphs (ted@lehigh.edu) */ /* */ /* This software is licensed under the Eclipse Public License. Please see */ /* accompanying file for terms. */ /* */ /*===========================================================================*/ /* system include files */ #include #include #include /* SYMPHONY include files */ /*__BEGIN_EXPERIMENTAL_SECTION__*/ #include "sym_master.h" /*___END_EXPERIMENTAL_SECTION___*/ #include "sym_macros.h" #include "sym_constants.h" #include "sym_proccomm.h" #include "sym_dg_params.h" #include "sym_master_u.h" /* CNRP include files */ #include "cnrp_const.h" #include "cnrp_types.h" #include "cnrp_io.h" #include "compute_cost.h" #include "cnrp_master_functions.h" #include "cnrp_dg_functions.h" #include "cnrp_macros.h" #include "small_graph.h" #include "network.h" #ifdef COMPILE_IN_TM #ifdef COMPILE_IN_LP #include "cnrp_lp.h" #ifdef COMPILE_IN_CG #include "cnrp_cg.h" #endif #ifdef COMPILE_IN_CP #include "cnrp_cp.h" #endif #endif #endif /*===========================================================================*/ /*===========================================================================*\ * This file contains the user-written functions for the master process. \*===========================================================================*/ void user_usage(void){ printf("master [ -HEP ] [ -S file ] [ -F file ] [ -B rule ]\n" "[ -V sel ] [ -K closest ] [ -N routes ] [ -C capacity ]\n" "[ -D level ] [ -M ] [ -X toggle ] [ -Y toggle ] \n" "[ -Z toggle ] [-G tau] \n" "\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" "\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", "-H: help", "-E: use sparse edge set", "-D level: verbosity level for displaying LP solutions", "-P type: specify problem type", "-S file: load sparse graph from 'file'", "-F file: problem data is in 'file'", "-B i: which candidates to check in strong branching", "-V i: how to construct the base set of variables", "-K k: use 'k' closest edges to build sparse graph", "-N n: use 'n' routes", "-M : use min cut subroutine", "-C c: use capacity 'c'", "-X t: toggles generation of X cuts", "-Y t: toggles generation of capacity cuts", "-Z t: toggles generation of tight capacity cuts", "-G t: set tau to 't'"); } /*===========================================================================*\ * Initialize user-defined data structures. In this case, I store all * problem-specific data such as the location of the customers, edge costs, * etc. in this data-structure. \*===========================================================================*/ int user_initialize(void **user) { cnrp_problem *cnrp = (cnrp_problem *) calloc(1, sizeof(cnrp_problem)); *user = cnrp; return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * In this function, I set up the user parameters. The first step is to cast * the void pointer in order to access my data. In the readparams() function, * I read in parameters from the parameter file given on the command line. \*===========================================================================*/ int user_readparams(void *user, char *filename, int argc, char **argv) { cnrp_problem *cnrp = (cnrp_problem *)user; /*__BEGIN_EXPERIMENTAL_SECTION__*/ #if 0 p->par.lp_par.problem_type = INTEGER_PROBLEM; strcpy(p->par.dg_par.source_path, "/home/tkr/BlackBox/DrawGraph/IGD_1.0/"); #endif /*___END_EXPERIMENTAL_SECTION___*/ cnrp_readparams(cnrp, filename, argc, argv); return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * After I've read in the parameters, I can now read in the data file, whose * name was given in the parameter file. This file contains instance data. \*===========================================================================*/ int user_io(void *user) { cnrp_problem *cnrp = (cnrp_problem *)user; cnrp_io(cnrp, cnrp->par.infile); if (cnrp->par.use_small_graph == LOAD_SMALL_GRAPH){ read_small_graph(cnrp); } if (!cnrp->numroutes && cnrp->par.prob_type == VRP){ printf("\nError: Number of trucks not specified or computed " "for VRP\n\n"); exit(1); } if (cnrp->numroutes > 1){ printf("NUMBER OF TRUCKS: \t%i\n", cnrp->numroutes); printf("TIGHTNESS: \t\t%.2f\n", cnrp->demand[0]/(cnrp->capacity*(double)cnrp->numroutes)); } /* Selects the cheapest edges adjacent to each node for the base set */ if (cnrp->par.use_small_graph == SAVE_SMALL_GRAPH){ if (!cnrp->g) make_small_graph(cnrp, 0); save_small_graph(cnrp); }else if (!cnrp->g){ make_small_graph(cnrp, 0); } return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * Here is where the heuristics are performed and an upper bound is calculated. * An upper bound can also be specified in the parameter file. The * other thing I do in this routine is build up a graph of the * cheapest k edges adjacent to the each node plus any edges chosen * during the heuristics to comprise my base set later. \*===========================================================================*/ int user_start_heurs(void *user, double *ub, double *ub_estimate) { cnrp_problem *cnrp = (cnrp_problem *)user; if (*ub > 0){ cnrp->cur_tour->cost = (int) (*ub); }else{ cnrp->cur_tour->cost = MAXINT; } cnrp->cur_tour->numroutes = cnrp->numroutes; if (cnrp->par.use_small_graph == LOAD_SMALL_GRAPH){ if (*ub <= 0 && cnrp->cur_tour->cost > 0) *ub = (int)(cnrp->cur_tour->cost); cnrp->numroutes = cnrp->cur_tour->numroutes; } #if 0 if(cnrp->par.prob_tpye == BPP) *ub = 1; #endif if (*ub > 0 && !(cnrp->par.prob_type == BPP)) printf("INITIAL UPPER BOUND: \t%i\n\n", (int)(*ub)); else if (!(cnrp->par.prob_type == BPP)) printf("INITIAL UPPER BOUND: \tNone\n\n"); else printf("\n\n"); return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * If graph drawing will be use, the user must initialize the drawing * window here. \*===========================================================================*/ int user_init_draw_graph(void *user, int dg_id) { #ifndef WIN32 /* FIXME : None of this works in Windows */ cnrp_problem *cnrp = (cnrp_problem *)user; int s_bufid; if (!(cnrp->posx && cnrp->posy)) return(USER_SUCCESS); if ( (cnrp->dg_id = dg_id) ){ int i, zero = 0, eight = 0x08; char node_place[MAX_NAME_LENGTH] = {"node_placement"}; char weight[5]; int *posx = cnrp->posx, *posy = cnrp->posy; int minx=MAXINT, miny=MAXINT, maxx=-MAXINT, maxy=-MAXINT, xx, yy; int width = 1000, height = 700; #if 0 int width=p->par.dg_par.canvas_width, height=p->par.dg_par.canvas_height; #endif double mult; for (i = cnrp->vertnum - 1; i >= 0; i--){ if (posx[i] < minx) minx = posx[i]; if (posx[i] > maxx) maxx = posx[i]; if (posy[i] < miny) miny = posy[i]; if (posy[i] > maxy) maxy = posy[i]; } xx = maxx - minx; yy = maxy - miny; mult = (int) MIN((width - 20.0)/xx, (height-20.0)/yy); width = (int) (xx * mult + 30); height = (int) (yy * mult + 30); for (i = cnrp->vertnum-1; i >= 0; i--){ posx[i] = (int) ((posx[i] - minx) * mult + 10); posy[i] = (int) ((maxy - posy[i]) * mult + 10); } init_window(dg_id, node_place, width, height); /* Now pack the placement of the nodes of the graph */ s_bufid = init_send(DataInPlace); send_str(node_place); send_int_array(&cnrp->vertnum, 1); for (i = 0; i < cnrp->vertnum; i++){ send_int_array(&i, 1); send_int_array(posx + i, 1); send_int_array(posy + i, 1); send_int_array(&eight, 1); sprintf(weight, "%i", (int)(cnrp->demand[i])); send_str(weight); } /* No edges are passed to the default graph */ send_int_array(&zero, 1); send_msg(dg_id, CTOI_SET_GRAPH); freebuf(s_bufid); display_graph(dg_id, node_place); } #endif return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * In this routine, I build the initial edge set for the root. There are * several things going on here. First, there is a user-defined parameter * defining whether or not to just go ahead and add all variables to the * problem up front (cnrp->par.add_all_edges). Currently, this seems to be the * best option since the problems are small anyway. Further, I am doing some * preprocessing here by eliminating edges for which the sum of the demands of * their endpoints is greater than the capacity since these edges cannot * be in any feasible solution. * * Notice that there are several options programmed for which set * of edges should be in the base set. The * base constraints are just the degree constraints from the IP * formulation. These do not have to be specified explicitly, just the * number of them given. \*===========================================================================*/ int user_initialize_root_node(void *user, int *basevarnum, int **basevars, int *basecutnum, int *extravarnum, int **extravars, char *obj_sense, double *obj_offset, char ***colnames, int *colgen_strat) { cnrp_problem *cnrp = (cnrp_problem *)user; *basevarnum = cnrp->basevarnum; *basevars = cnrp->basevars; *extravarnum = cnrp->extravarnum; *extravars = cnrp->extravars; *basecutnum = cnrp->basecutnum; if (!cnrp->par.colgen_strat[0]){ if (cnrp->par.add_all_edges || cnrp->par.base_variable_selection == SOME_ARE_BASE){ colgen_strat[0]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD | BEFORE_BRANCH__DO_NOT_GENERATE_COLS); }else{ colgen_strat[0] = (FATHOM__DO_NOT_GENERATE_COLS__SEND | BEFORE_BRANCH__DO_NOT_GENERATE_COLS); } }else{ colgen_strat[0] = cnrp->par.colgen_strat[0]; } if (!cnrp->par.colgen_strat[1]){ if (cnrp->par.add_all_edges || cnrp->par.base_variable_selection == SOME_ARE_BASE){ colgen_strat[1]=(FATHOM__DO_NOT_GENERATE_COLS__DISCARD | BEFORE_BRANCH__DO_NOT_GENERATE_COLS); }else{ colgen_strat[1] = (FATHOM__GENERATE_COLS__RESOLVE | BEFORE_BRANCH__DO_NOT_GENERATE_COLS); } }else{ colgen_strat[1] = cnrp->par.colgen_strat[1]; } return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * In my case, a feasible solution is specified most compactly by * essentially a permutation of the customers along with routes numbers, * specifying the order of the customers on their routes. This is just * sent as a character array which then gets cast to an array of * structures, one for each customers specifying the route number and * the next customer on the route. \*===========================================================================*/ int user_receive_feasible_solution(void *user, int msgtag, double cost, int numvars, int *indices, double *values) { cnrp_problem *cnrp = (cnrp_problem *)user; if (cnrp->par.prob_type == TSP || cnrp->par.prob_type == VRP || cnrp->par.prob_type == BPP) receive_char_array((char *)cnrp->cur_tour->tour, cnrp->vertnum*sizeof(_node)); else receive_int_array(cnrp->cur_sol_tree, cnrp->vertnum); return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * Here, we send the necessary data to the LP process. Notice that * there are two cases to deal with. If the LP or the TM are running * as separate processes, then we have to send the data by * message-passing. Otherwise, we can allocate the user-defined LP data * structure here and simply copy the necessary information. This is the * only place the user has to sorry about this distinction between * configurations. \*===========================================================================*/ int user_send_lp_data(void *user, void **user_lp) { cnrp_problem *cnrp = (cnrp_problem *)user; #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) /* This is the case when we are copying data directly because the LP is not running separately. This code should be virtually identical to that of user_receive_lp_data() in the LP process.*/ cnrp_spec *cnrp_lp = (cnrp_spec *) calloc(1, sizeof(cnrp_spec)); int zero_varnum = cnrp->zero_varnum; int *zero_vars = cnrp->zero_vars; int vertnum, i, j, k, l; *user_lp = (void *)cnrp_lp; cnrp_lp->par = cnrp->lp_par; cnrp_lp->window = cnrp->dg_id; cnrp_lp->numroutes = cnrp->numroutes; vertnum = cnrp_lp->vertnum = cnrp->vertnum; cnrp_lp->edges = cnrp->edges; cnrp_lp->demand = cnrp->demand; cnrp_lp->capacity = cnrp->capacity; cnrp_lp->costs = cnrp->dist.cost; cnrp_lp->utopia_fixed = cnrp->utopia_fixed; cnrp_lp->utopia_variable = cnrp->utopia_variable; cnrp_lp->variable_cost = cnrp_lp->fixed_cost = MAXDOUBLE; cnrp_lp->ub = cnrp->ub; if (cnrp->par.prob_type == VRP || cnrp->par.prob_type == TSP || cnrp->par.prob_type == BPP){ cnrp_lp->cur_sol = (_node *) calloc (cnrp->vertnum, sizeof(_node)); }else{ cnrp_lp->cur_sol_tree = (int *) calloc (cnrp->vertnum - 1, ISIZE); } /*__BEGIN_EXPERIMENTAL_SECTION__*/ if (cnrp_lp->window){ copy_node_set(cnrp_lp->window, TRUE, (char *)"Weighted solution"); copy_node_set(cnrp_lp->window, TRUE, (char *)"Flow solution"); } /*___END_EXPERIMENTAL_SECTION___*/ #else /* Here, we send that data using message passing and the rest is done in user_receive_lp_data() in the LP process */ send_char_array((char *)(&cnrp->lp_par), sizeof(cnrp_lp_params)); send_int_array(&cnrp->dg_id, 1); send_int_array(&cnrp->numroutes, 1); send_int_array(&cnrp->vertnum, 1); send_dbl_array(cnrp->demand, cnrp->vertnum); send_dbl_array(&cnrp->capacity, 1); send_int_array(cnrp->dist.cost, cnrp->edgenum); send_int_array(&cnrp->zero_varnum, 1); if (cnrp->zero_varnum){ send_int_array(cnrp->zero_vars, cnrp->zero_varnum); } send_dbl_array(&cnrp->utopia_fixed, 1); send_dbl_array(&cnrp->utopia_variable, 1); send_dbl_array(&cnrp->ub, 1); #endif return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * Here, we send the necessary data to the CG process. Notice that * there are two cases to deal with. If the CG, LP, or the TM are running * as separate processes, then we have to send the data by * message-passing. Otherwise, we can allocate the user-defined LP data * structure here and simply copy the necessary information. This is the * only place the user has to sorry about this distinction between * configurations. \*===========================================================================*/ int user_send_cg_data(void *user, void **user_cg) { cnrp_problem *cnrp = (cnrp_problem *)user; #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CG) /* This is is the case when we are copying data directly because the CG is not running separately. This code should be virtually identical to that of user_receive_cg_data() in the CG process.*/ cg_cnrp_spec *cnrp_cg = (cg_cnrp_spec *) malloc (sizeof(cg_cnrp_spec)); int edgenum, vertnum, i, j, k; *user_cg = (void *)cnrp_cg; cnrp_cg->par = cnrp->cg_par; cnrp_cg->numroutes = cnrp->numroutes; vertnum = cnrp_cg->vertnum = cnrp->vertnum; cnrp_cg->demand = cnrp->demand; cnrp_cg->capacity = cnrp->capacity; cnrp_cg->dg_id = cnrp->dg_id; edgenum = cnrp->vertnum*(cnrp->vertnum-1)/2; cnrp_cg->in_set = (char *) calloc(cnrp->vertnum, sizeof(char)); cnrp_cg->ref = (int *) malloc(cnrp->vertnum*sizeof(int)); cnrp_cg->new_demand = (double *) malloc(cnrp->vertnum*sizeof(double)); cnrp_cg->cut_val = (double *) calloc(cnrp->vertnum, sizeof(double)); cnrp_cg->cut_list = (char *) malloc(((cnrp->vertnum >> DELETE_POWER)+1)* (cnrp->cg_par.max_num_cuts_in_shrink + 1)* sizeof(char)); cnrp_cg->edges = (int *) calloc (2*edgenum, sizeof(int)); /*create the edge list (we assume a complete graph)*/ for (i = 1, k = 0; i < vertnum; i++){ for (j = 0; j < i; j++){ cnrp_cg->edges[2*k] = j; cnrp_cg->edges[2*k+1] = i; k++; } } #ifdef CHECK_CUT_VALIDITY if ((cnrp_cg->feas_sol_size = cnrp->feas_sol_size)){ cnrp_cg->feas_sol = cnrp->feas_sol; } #endif #else /* Here, we send that data using message passing and the rest is done in user_receive_cg_data() in the CG process */ send_char_array((char *)&cnrp->cg_par, sizeof(cnrp_cg_params)); send_int_array(&cnrp->dg_id, 1); send_int_array(&cnrp->numroutes, 1); send_int_array(&cnrp->vertnum, 1); send_dbl_array(cnrp->demand, cnrp->vertnum); send_dbl_array(&cnrp->capacity, 1); #ifdef CHECK_CUT_VALIDITY send_int_array(&cnrp->feas_sol_size, 1); if (cnrp->feas_sol_size){ send_int_array(cnrp->feas_sol, cnrp->feas_sol_size); } #endif #endif return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * Here, we send the necessary data to the CP process. Notice that * there are two cases to deal with. If the CP, LP, or the TM are running * as separate processes, then we have to send the data by * message-passing. Otherwise, we can allocate the user-defined LP data * structure here and simply copy the necessary information. This is the * only place the user has to sorry about this distinction between * configurations. \*===========================================================================*/ int user_send_cp_data(void *user, void **user_cp) { cnrp_problem *cnrp = (cnrp_problem *)user; #if defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP) && defined (COMPILE_IN_CP) /* This is is the case when we are copying data directly because the LP is not running separately. This code should be virtually identical to that of user_receive_cp_data() in the CP process.*/ cnrp_spec_cp *cnrp_cp = (cnrp_spec_cp *) malloc (sizeof(cnrp_spec_cp)); int i, j, k; cnrp_cp->par = cnrp->cp_par; cnrp_cp->vertnum = cnrp->vertnum; cnrp_cp->capacity = cnrp->capacity; cnrp_cp->demand = (double *) malloc(cnrp->vertnum * DSIZE); memcpy((char *)cnrp_cp->demand, (char *) cnrp->demand, cnrp->vertnum * DSIZE); *user_cp = (void *)cnrp_cp; cnrp_cp->edgenum = cnrp_cp->vertnum*(cnrp_cp->vertnum-1)/2 + cnrp_cp->vertnum-1; cnrp_cp->edges = (int *) calloc ((int)2*cnrp_cp->edgenum, sizeof(int)); /* create the edge list (we assume a complete graph) */ for (i = 1, k = 0; i < cnrp_cp->vertnum; i++){ for (j = 0; j < i; j++){ cnrp_cp->edges[2*k] = j; cnrp_cp->edges[2*k+1] = i; k++; } } /* now add the duplicate copies of the depot edges to allow for routes with one customer */ for (i = 1; i < cnrp_cp->vertnum; i++){ cnrp_cp->edges[2*k] = 0; cnrp_cp->edges[2*k+1] = i; k++; } #else /* Here, we send that data using message passing and the rest is done in user_receive_cp_data() in the CP process */ send_int_array(&cnrp->vertnum, 1); send_dbl_array(&cnrp->capacity, 1); send_dbl_array(cnrp->demand, cnrp->vertnum); #endif return(USER_SUCCESS); } /*__BEGIN_EXPERIMENTAL_SECTION__*/ /*===========================================================================*/ int user_send_sp_data(void *user) { return(USER_SUCCESS); } /*___END_EXPERIMENTAL_SECTION___*/ /*===========================================================================*/ /*===========================================================================*\ * Generally, this function is not needed but you might find some use * for it. Someone did :). \*===========================================================================*/ int user_process_own_messages(void *user, int msgtag) { return(USER_DEFAULT); } /*===========================================================================*/ /*===========================================================================*\ * This is the user's chance to display the solution in whatever * manner desired. In my case, I can display a text version, which is * just a list of the customers on each route, or use the interactive * Graph Drawing application to graphically display the solution. \*===========================================================================*/ int user_display_solution(void *user, double lpetol, int varnum, int *indices, double *values, double objval) { cnrp_problem *cnrp = (cnrp_problem *)user; _node *tour = cnrp->cur_tour->tour; int *tree = cnrp->cur_sol_tree, node, prev_node; int cur_vert = 0, prev_vert = 0, cur_route, i, count; elist *cur_route_start = NULL; edge *edge_data; vertex *verts; double fixed_cost = 0.0, variable_cost = 0.0; int window = cnrp->dg_id; int vertnum = cnrp->vertnum, v0, v1; int total_edgenum = vertnum*(vertnum-1)/2; network *n; /* FIXME: This is UGLY! */ #if (defined(MULTI_CRITERIA) && defined(FIND_NONDOMINATED_SOLUTIONS)) && \ (defined(COMPILE_IN_TM) && defined(COMPILE_IN_LP)) && 0 problem *p = get_problem_ptr(FALSE); cnrp_spec *cnrp_lp = (cnrp_spec *) p->tm->lpp[0]->user; cnrp->fixed_cost = cnrp_lp->fixed_cost; cnrp->variable_cost = cnrp_lp->variable_cost; tour = cnrp_lp->cur_sol; tree = cnrp_lp->cur_sol_tree; printf("\nSolution Found:\n"); #ifdef ADD_FLOW_VARS printf("Solution Fixed Cost: %.1f\n", cnrp->fixed_cost); printf("Solution Variable Cost: %.1f\n", cnrp->variable_cost); #else printf("Solution Cost: %.0f\n", fixed_cost); #endif #else printf("\nSolution Found:\n"); #endif #if 0 if (tour){ node = tour[0].next; if (tour[0].route == 1) printf("\n0 "); while (node != 0){ if (tour[prev_node].route != tour[node].route){ printf("\nRoute #%i: ", tour[node].route); count = 0; } printf("%i ", node); count++; if (count > 15){ printf("\n"); count = 0; } prev_node = node; node = tour[node].next; } printf("\n\n"); if (window){ char name[MAX_NAME_LENGTH] = {"feas_solution"}; disp_vrp_tour(window, TRUE, name, tour, cnrp->vertnum, cnrp->numroutes, CTOI_WAIT_FOR_CLICK_AND_REPORT); } return(USER_SUCCESS); } if (tree){ printf("Edge List:\n"); for (i = 0; i < vertnum - 1; i++){ BOTH_ENDS(tree[i], &v0, &v1); printf("%i %i\n", v1, v0); } printf("\n\n"); if (window){ char name[MAX_NAME_LENGTH] = {"feas_solution"}; copy_node_set(window, TRUE, name); draw_edge_set_from_userind(window, name, vertnum - 1, tree); display_graph(window, name); wait_for_click(window, name, CTOI_WAIT_FOR_CLICK_NO_REPORT); } return(USER_SUCCESS); } #endif /*Otherwise, construct the solution from scratch*/ #ifdef ADD_FLOW_VARS n = create_flow_net(indices, values, varnum, lpetol, cnrp->edges, cnrp->demand, vertnum); #else n = create_net(indices, values, varnum, lpetol, cnrp->edges, cnrp->demand, vertnum); #endif for (i = 0; i < n->edgenum; i++){ if (n->edges[i].weight > 1 - lpetol){ fixed_cost += cnrp->dist.cost[INDEX(n->edges[i].v0, n->edges[i].v1)]; } #ifdef ADD_FLOW_VARS variable_cost += (n->edges[i].flow1+n->edges[i].flow2)* cnrp->dist.cost[INDEX(n->edges[i].v0, n->edges[i].v1)]; #endif } cnrp->fixed_cost = fixed_cost; cnrp->variable_cost = variable_cost; #if defined(ADD_FLOW_VARS) && defined(MULTI_CRITERIA) printf("Solution Fixed Cost: %.1f\n", fixed_cost); printf("Solution Variable Cost: %.1f\n", variable_cost); #else printf("Solution Cost: %.0f\n", fixed_cost); #endif if (cnrp->par.prob_type == TSP || cnrp->par.prob_type == VRP || cnrp->par.prob_type == BPP){ verts = n->verts; /*construct the tour corresponding to this solution vector*/ for (cur_route_start = verts[0].first, cur_route = 1, edge_data = cur_route_start->data; cur_route <= cnrp->numroutes; cur_route++){ edge_data = cur_route_start->data; edge_data->scanned = TRUE; cur_vert = edge_data->v1; tour[prev_vert].next = cur_vert; tour[cur_vert].route = cur_route; prev_vert = 0; while (cur_vert){ if (verts[cur_vert].first->other_end != prev_vert){ prev_vert = cur_vert; edge_data = verts[cur_vert].first->data; cur_vert = verts[cur_vert].first->other_end; } else{ prev_vert = cur_vert; edge_data = verts[cur_vert].last->data; /*This statement could possibly be taken out to speed things up a bit*/ cur_vert = verts[cur_vert].last->other_end; } tour[prev_vert].next = cur_vert; tour[cur_vert].route = cur_route; } edge_data->scanned = TRUE; while (cur_route_start->data->scanned){ if (!(cur_route_start = cur_route_start->next_edge)) break; } } /* Display the solution */ cur_vert = tour[0].next; if (tour[0].route == 1) printf("\n0 "); while (cur_vert != 0){ if (tour[prev_vert].route != tour[cur_vert].route){ printf("\nRoute #%i: ", tour[cur_vert].route); count = 0; } printf("%i ", cur_vert); count++; if (count > 15){ printf("\n"); count = 0; } prev_vert = cur_vert; cur_vert = tour[cur_vert].next; } printf("\n"); }else{ for (i = 0; i < n->edgenum; i++){ cnrp->cur_sol_tree[i] = INDEX(n->edges[i].v0, n->edges[i].v1); } /* Display the solution */ for (i = 0; i < n->edgenum; i++){ printf("%i %i\n", n->edges[i].v0, n->edges[i].v1); } printf("\n"); } free_net(n); return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * This is a debugging feature which might * allow you to find out why a known feasible solution is being cut off. \*===========================================================================*/ int user_send_feas_sol(void *user, int *feas_sol_size, int **feas_sol) { #ifdef TRACE_PATH cnrp_problem *cnrp = (cnrp_problem *)user; *feas_sol_size = cnrp->feas_sol_size; *feas_sol = cnrp->feas_sol; #endif return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * This function frees everything. \*===========================================================================*/ int user_free_master(void **user) { cnrp_problem *cnrp = (cnrp_problem *)(*user); if (cnrp->cur_tour){ FREE(cnrp->cur_tour->tour); FREE(cnrp->cur_tour->route_info); FREE(cnrp->cur_tour); } FREE(cnrp->cur_sol_tree); FREE(cnrp->posy); FREE(cnrp->posx); FREE(cnrp->dist.coordx); FREE(cnrp->dist.coordy); FREE(cnrp->dist.coordz); FREE(cnrp->dist.cost); FREE(cnrp->edges); FREE(cnrp->demand); if (cnrp->g){ FREE(cnrp->g->edges); FREE(cnrp->g); } #ifdef CHECK_CUT_VALIDITY FREE(cnrp->feas_sol); #endif FREE(cnrp->zero_vars); FREE(cnrp); return(USER_SUCCESS); } /*===========================================================================*/ /*===========================================================================*\ * This function is used to lift the user created cuts during warm starting * \*===========================================================================*/ int user_ws_update_cuts (void *user, int *size, char **coef, double * rhs, char *sense, char type, int new_col_num, int change_type) { return(USER_DEFAULT); } /*===========================================================================*/