VRPH  1.0
src/apps/SYMPHONY_vrp_main.c
Go to the documentation of this file.
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