VRPH
1.0
|
00001 /*===========================================================================*/ 00002 /* */ 00003 /* This file is part of a demonstration application for use with the */ 00004 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ 00005 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */ 00006 /* */ 00007 /* (c) Copyright 2000-2007 Ted Ralphs. All Rights Reserved. */ 00008 /* */ 00009 /* This application was developed by Ted Ralphs (tkralphs@lehigh.edu) */ 00010 /* */ 00011 /* This software is licensed under the Common Public License. Please see */ 00012 /* accompanying file for terms. */ 00013 /* */ 00014 /*===========================================================================*/ 00015 00016 // This file is a modified version of SYMPHONY's vrp_main.c file that 00017 // adds the ability to determine an initial upper bound by running 00018 // heuristics from the VRPH library. 00019 // This capability can be turned off by setting USE_VRPH 0 below. 00020 00021 #define COMPILING_FOR_MASTER 00022 #define USE_VRPH 1 00023 // We will have VRPH generate NUM_VRPH_SOLUTIONS 00024 #define NUM_VRPH_SOLUTIONS 10 00025 /*===========================================================================*/ 00026 00027 /*===========================================================================*\ 00028 * This file contains the main() for the master process. 00029 \*===========================================================================*/ 00030 00031 #ifdef USE_OSI_INTERFACE 00032 00033 #include "OsiSymSolverInterface.hpp" 00034 00035 int main(int argc, char **argv) 00036 { 00037 OsiSymSolverInterface si; 00038 00039 //si.setSymParam(OsiSymVerbosity, 3); 00040 si.setSymParam(OsiSymGranularity, 0.9999); 00041 si.setSymParam("generate_cgl_cuts", FALSE); 00042 si.setSymParam("lp_executable_name", "vrp_lp_cg"); 00043 si.setSymParam("cp_executable_name", "vrp_cp"); 00044 00045 /* Parse the command line */ 00046 si.parseCommandLine(argc, argv); 00047 00048 /* Read in the problem */ 00049 si.loadProblem(); 00050 00051 /* Find a priori problem bounds */ 00052 si.findInitialBounds(); 00053 00054 /* Solve the problem */ 00055 si.branchAndBound(); 00056 00057 return(0); 00058 } 00059 00060 #else 00061 00062 #include "symphony.h" 00063 #include "sym_master.h" 00064 #include "vrp_types.h" 00065 #include "vrp_const.h" 00066 // Including VRPH.h is the only include file needed 00067 // You also have to add -lvrph to the compile line or 00068 // add this to the MSVC project 00069 #if USE_VRPH 00070 #include "VRPH.h" 00071 #endif 00072 00073 int vrp_test(sym_environment *env, int argc, char **argv); 00074 00075 int main(int argc, char **argv) 00076 { 00077 #if USE_VRPH 00078 // A few things required by VRPH 00079 int i; 00080 double best_sol=VRP_INFINITY; 00081 int best_sol_buff[500]; 00082 #endif 00083 00084 vrp_problem *vrp; 00085 00086 sym_environment *env = sym_open_environment(); 00087 00088 version(); 00089 00090 sym_parse_command_line(env, argc, argv); 00091 00092 sym_get_user_data(env, (void**)&vrp); 00093 00094 #if USE_VRPH 00095 // Get the size of the problem in the input file 00096 int n=VRPGetDimension(vrp->par.infile); 00097 // Declare a VRP object of size n 00098 VRP V(n); 00099 // Declare a ClarkeWright object of size n 00100 ClarkeWright CW(n); 00101 00102 // Populate the VRP object with the input file 00103 V.read_TSPLIB_file(vrp->par.infile); 00104 00105 // Now create NUM_VRPH_SOLUTIONS solutions using VRPH and set the 00106 // upper bound to the best solution discovered 00107 for(i=0;i<NUM_VRPH_SOLUTIONS;i++) 00108 { 00109 // Create default routes - each customer on its own route 00110 V.create_default_routes(); 00111 // Create a new random feasible solution with Clarke Wright 00112 CW.Construct(&V, .5+ lcgrand(1),false); 00113 // Improve it with the RTR heuristic 00114 V.RTR_solve(ONE_POINT_MOVE+TWO_POINT_MOVE+TWO_OPT+THREE_OPT, 00115 30,5,1,.01,25,VRPH_LI_PERTURB,VRPH_BEST_ACCEPT,false); 00116 if(V.get_total_route_length()-V.get_total_service_time()<best_sol) 00117 { 00118 best_sol=V.get_total_route_length()-V.get_total_service_time(); 00119 V.export_canonical_solution_buff(best_sol_buff); 00120 } 00121 // Reset VRPH's internal data structures 00122 V.reset(); 00123 } 00124 00125 // Import the best solution and display it - if SYMPHONY claims an infeasibility 00126 // because the VRPH solution is optimal, we wouldn't see it otherwise! 00127 printf("VRPH set SYMPHONY upper bound to %f based on solution:\n",best_sol); 00128 V.import_solution_buff(best_sol_buff); 00129 V.summary(); 00130 00131 // Set the upper bound using VRPH solution by accessing SYMPHONY's 00132 // internal data structures 00133 env->has_ub=1; 00134 env->ub=best_sol ; 00135 #if 0 00136 // Note that this might be incorrect if the VRPH solution is not optimal 00137 // So the # of trucks still needs to be passed in on the command line! 00138 vrp->numroutes=V.get_total_number_of_routes(); 00139 #endif 00140 #endif 00141 00142 // Now just let SYMPHONY do its thing. If an infeasibility is encountered, 00143 // then this certifies that the solution found by VRPH is indeed optimal 00144 // Note that the par.test will not work as we have processed only a single 00145 // file. Thus, we changed the following line 00146 // if (vrp->par.test){ 00147 if (0 && vrp->par.test){ 00148 00149 vrp_test(env, argc, argv); 00150 00151 } else { 00152 00153 sym_load_problem(env); 00154 00155 sym_find_initial_bounds(env); 00156 00157 sym_set_str_param(env, "lp_executable_name", "vrp_lp_cg"); 00158 sym_set_str_param(env, "cp_executable_name", "vrp_cp"); 00159 sym_set_int_param(env, "generate_cgl_cuts", FALSE); 00160 00161 sym_solve(env); 00162 00163 } 00164 00165 sym_close_environment(env); 00166 00167 return(0); 00168 } 00169 00170 /*===========================================================================*/ 00171 /*===========================================================================*/ 00172 00173 int vrp_test(sym_environment *env, int argc, char **argv) 00174 { 00175 00176 int termcode, i, file_num = 34; 00177 char input_files[34][MAX_FILE_NAME_LENGTH +1] = {"A/A-n34-k5", 00178 "A/A-n32-k5", 00179 "A/A-n33-k5", 00180 "E/E-n13-k4", 00181 "E/E-n22-k4", 00182 "E/E-n23-k3", 00183 "E/E-n30-k3", 00184 "E/E-n33-k4", 00185 "V/att-n48-k4", 00186 "E/E-n51-k5", 00187 "A/A-n33-k6", 00188 "A/A-n36-k5", 00189 "A/A-n37-k5", 00190 "A/A-n38-k5", 00191 "A/A-n39-k5", 00192 "A/A-n39-k6", 00193 "A/A-n45-k6", 00194 "A/A-n46-k7", 00195 "B/B-n31-k5", 00196 "B/B-n34-k5", 00197 "B/B-n35-k5", 00198 "B/B-n38-k6", 00199 "B/B-n39-k5", 00200 "B/B-n41-k6", 00201 "B/B-n43-k6", 00202 "B/B-n44-k7", 00203 "B/B-n45-k5", 00204 "B/B-n50-k7", 00205 "B/B-n51-k7", 00206 "B/B-n52-k7", 00207 "B/B-n56-k7", 00208 "B/B-n64-k9", 00209 "A/A-n48-k7", 00210 "A/A-n53-k7"}; 00211 00212 double sol[34] = {778, 784, 661, 247, 375, 569, 534, 835, 40002, 521, 742, 00213 799, 669, 730, 822, 831, 944, 914, 672, 788, 955, 805, 00214 549, 829, 742, 909, 751, 741, 1032, 747, 707, 861, 00215 1073, 1010}; 00216 00217 char *input_dir = (char*)malloc(CSIZE*(MAX_FILE_NAME_LENGTH+1)); 00218 char *infile = (char*)malloc(CSIZE*(MAX_FILE_NAME_LENGTH+1)); 00219 char *sgfile = (char*)malloc(CSIZE*(MAX_FILE_NAME_LENGTH+1)); 00220 double *obj_val = (double *)calloc(DSIZE,file_num); 00221 double tol = 1e-06, ub; 00222 00223 vrp_problem *vrp = (vrp_problem *) env->user; 00224 00225 if (strcmp(vrp->par.test_dir, "") == 0){ 00226 strcpy(input_dir, "../../../VRPLIB"); 00227 } else{ 00228 strcpy(input_dir, vrp->par.test_dir); 00229 } 00230 00231 for(i = 0; i<file_num; i++){ 00232 00233 strcpy(infile, ""); 00234 strcpy(sgfile, ""); 00235 sprintf(infile, "%s%s%s%s", input_dir, "/", input_files[i], ".vrp"); 00236 sprintf(sgfile, "%s%s%s", "./small_graph/", input_files[i], ".sg"); 00237 00238 00239 strcpy(vrp->par.infile, infile); 00240 strcpy(vrp->par.small_graph_file, sgfile); 00241 vrp->par.use_small_graph = LOAD_SMALL_GRAPH; 00242 00243 sym_load_problem(env); 00244 00245 sym_find_initial_bounds(env); 00246 00247 printf("Solving %s...\n", input_files[i]); 00248 00249 sym_solve(env); 00250 00251 sym_get_obj_val(env, &obj_val[i]); 00252 00253 if((obj_val[i] < sol[i] + tol) && 00254 (obj_val[i] > sol[i] - tol)){ 00255 printf("Success!\n"); 00256 } else { 00257 printf("Failure!(%f, %f) \n", obj_val[i], sol[i]); 00258 } 00259 00260 if(i+1 < file_num){ 00261 sym_close_environment(env); 00262 00263 env = sym_open_environment(); 00264 sym_parse_command_line(env, argc, argv); 00265 } 00266 00267 } 00268 return (0); 00269 } 00270 00271 #endif