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-2013 Ted Ralphs. All Rights Reserved. */ 8 /* */ 9 /* This application was developed by Ted Ralphs (ted@lehigh.edu) */ 10 /* */ 11 /* This software is licensed under the Eclipse Public License. Please see */ 12 /* accompanying file for terms. */ 13 /* */ 14 /*===========================================================================*/ 15 16 #ifndef _VRP_TYPES2_H 17 #define _VRP_TYPES2_H 18 19 /* SYMPHONY include files */ 20 #include "sym_proto.h" 21 22 /* VRP include files */ 23 #include "vrp_common_types.h" 24 #include "vrp_cg_params.h" 25 #include "vrp_lp_params.h" 26 #ifdef COMPILE_HEURS 27 #include "heur_params.h" 28 #include "lb_params.h" 29 30 /*---------------------------------------------------------------------------*\ 31 * Here we keep track of the computation time for the lower and upper 32 * bounding procedures 33 \*---------------------------------------------------------------------------*/ 34 35 typedef struct BD_TIMES{ 36 double ub_overhead; /*overhead time used doing the upper bounding*/ 37 double ub_heurtime; /*actual comp time spent doing the upper bounding*/ 38 double lb_overhead; /*overhead time spent doing the lower bounding*/ 39 double lb_heurtime; /*actual comp time spent doing the lower bounding*/ 40 }bd_times; 41 42 /*---------------------------------------------------------------------------*\ 43 * The heurs structure is used to keep track of the various heuristic processes 44 * which are currently running. The jobs field contains the number of processes 45 * currently running. The tids field is an array containing the tid's of these 46 * processes. 47 \*---------------------------------------------------------------------------*/ 48 49 typedef struct HEURS{ 50 int jobs; 51 int *tids; 52 char *finished; 53 int *starter; 54 }heurs; 55 56 /*---------------------------------------------------------------------------*\ 57 * Contains the tree correspoding to the best lower bound found using 58 * lagrangian relaxation 59 \*---------------------------------------------------------------------------*/ 60 61 typedef struct LOW_BD{ 62 int *tree; 63 edge_data *best_edges; 64 double lower_bound; 65 }low_bd; 66 67 /*---------------------------------------------------------------------------*\ 68 * This structure contains the values of the time out parameters for 69 * upper and lower bounding routines. 70 \*---------------------------------------------------------------------------*/ 71 72 typedef struct TIME_OUT_PAR{ 73 int ub; 74 int lb; 75 }time_out_par; 76 #endif 77 78 /*__BEGIN_EXPERIMENTAL_SECTION__*/ 79 /*---------------------------------------------------------------------------*\ 80 * Here we store the names of the executables to be used for each part of the 81 * code. This way, we can run different versions of each part of the code 82 * simply by changing the parameter file 83 \*---------------------------------------------------------------------------*/ 84 85 typedef struct EXEC{ 86 char winprog[MAX_FILE_NAME_LENGTH]; 87 #ifdef COMPILE_HEURS 88 char heuristics[MAX_FILE_NAME_LENGTH]; 89 #endif 90 }exec; 91 92 /*---------------------------------------------------------------------------*\ 93 * This structure contains debugging parameters for PVM. If they are zero, 94 * then no debugging window comes up when the process is spawned. If any of 95 * them are set at 4, then a debugging window for that process will be 96 * launched on the host machine. 0 and 4 are the only two meaningful values 97 \*---------------------------------------------------------------------------*/ 98 99 typedef struct DEBUGGING{ 100 int winprog; 101 int heuristics; 102 }debugging; 103 /*___END_EXPERIMENTAL_SECTION___*/ 104 105 /*---------------------------------------------------------------------------*\ 106 * The "small_graph" data structure is used to store the subset of the 107 * edges that will be used initially in actually solving the problem. 108 * These edges usually consist of any edges found among the ones used in 109 * the heuristics solutions and the set of shortest edges adjacent to 110 * each node in the graph 111 \*---------------------------------------------------------------------------*/ 112 113 typedef struct SMALL_GRAPH{ /* this gets passed eg. to lin-kerninghan */ 114 int vertnum; /* vertnum in the restricted (small) graph */ 115 int edgenum; /* edgenum in the restricted (small) graph */ 116 int allocated_edgenum; 117 int del_edgenum; 118 edge_data *edges; /* The data for these edges */ 119 }small_graph; 120 121 #ifndef COMPILE_HEURS 122 typedef struct CLOSENODE{ /*close node to a particular one */ 123 int node; 124 int cost; 125 }closenode; 126 #endif 127 128 typedef struct VRP_PARAMS{ 129 char infile[MAX_FILE_NAME_LENGTH + 1]; 130 int verbosity; 131 char tsp_prob; 132 /*__BEGIN_EXPERIMENTAL_SECTION__*/ 133 char bpp_prob; 134 /*___END_EXPERIMENTAL_SECTION___*/ 135 int k_closest; 136 int min_closest; 137 int max_closest; 138 int add_all_edges; 139 int add_depot_edges; 140 int base_variable_selection; 141 int use_small_graph; 142 char small_graph_file[MAX_FILE_NAME_LENGTH]; 143 int colgen_strat[2]; 144 /*__BEGIN_EXPERIMENTAL_SECTION__*/ 145 exec executables; 146 debugging debug; 147 /*___END_EXPERIMENTAL_SECTION___*/ 148 #ifdef COMPILE_HEURS 149 int *rand_seed; 150 int tours_to_keep; 151 time_out_par time_out; 152 int do_heuristics; 153 #endif 154 155 int test; 156 char test_dir[MAX_FILE_NAME_LENGTH +1]; /* Test files directory */ 157 }vrp_params; 158 159 /*---------------------------------------------------------------------------*\ 160 * The problem data structure contains the data for a problem instance, as 161 * well as some of the tours that have been generated. 162 \*---------------------------------------------------------------------------*/ 163 164 typedef struct VRP_PROBLEM{ 165 char name[100]; /* the name of the problem instance */ 166 vrp_params par; 167 vrp_cg_params cg_par; 168 vrp_lp_params lp_par; 169 #ifdef COMPILE_HEURS 170 heur_params heur_par; 171 lb_params lb_par; 172 #endif 173 int dg_id; /* drawgraph process id */ 174 int vertnum; /* the number of nodes in the problem, including 175 the depot */ 176 int edgenum; /* number of edges in the problem */ 177 int *edges; 178 int numroutes; /* contains the number of routes that the problem 179 is to be solved with. can be prespecified. */ 180 int depot; /* the index of the depot, usually 1 */ 181 int capacity; /* the capacity of a truck */ 182 int *demand; /* an array containing the demands for each node. 183 node i's demand is p->demand[i-1] */ 184 int *posx; /* x coordinate for display purposes */ 185 int *posy; /* y coordinate for display purposes */ 186 187 distances dist; /* the data about the distances in the problem */ 188 189 best_tours *cur_tour; /* temporary tour storage */ 190 #ifdef COMPILE_HEURS 191 best_tours *tours; /* an array of the best tours found */ 192 int *tourorder; /* a binary tree containing the ordering of the 193 tours in best_tours */ 194 int tournum; /* the number of tours stored in best_tours-1 */ 195 low_bd *lb; /* contains the information on the best lower 196 bound */ 197 #endif 198 small_graph *g; /* contains the edge data for the reduced graph*/ 199 #if defined(CHECK_CUT_VALIDITY) || defined(TRACE_PATH) 200 int feas_sol_size; 201 int *feas_sol; 202 #endif 203 #ifdef COMPILE_HEURS 204 bd_times bd_time; 205 #endif 206 /*__BEGIN_EXPERIMENTAL_SECTION__*/ 207 int sol_pool_col_num; 208 int *sol_pool_cols; 209 /*___END_EXPERIMENTAL_SECTION___*/ 210 int *zero_vars; 211 int zero_varnum; 212 }vrp_problem; 213 214 #endif 215