VRP_Concorde.h

Go to the documentation of this file.
00001 //===========================================================================//
00002 // This file is part of the Decomp Solver Framework.                         //
00003 //                                                                           //
00004 // Decomp is distributed under the Common Public License as part of the      //
00005 // COIN-OR repository (http://www.coin-or.org).                              //
00006 //                                                                           //
00007 // Author: Matthew Galati, Lehigh University                                 //
00008 //                                                                           //
00009 // Copyright (C) 2002-2015, Lehigh University, Matthew Galati, and Ted Ralphs//
00010 // All Rights Reserved.                                                      //
00011 //===========================================================================//
00012 
00013 #ifndef VRP_CONCORDE_INCLUDED
00014 #define VRP_CONCORDE_INCLUDED
00015 
00016 //---
00017 //--- Interface class to Concorde (TSP solver)
00018 //---
00019 
00020 // --------------------------------------------------------------------- //
00021 #include "VRP_ConcordeI.h"
00022 
00023 // --------------------------------------------------------------------- //
00024 #define VRP_CONCORDE_DEBUG       0
00025 #define VRP_CONCORDE_SOLVER_TINY 1
00026 //#define VRP_CONCORDE_SOLVER_TINY 0
00027 
00028 // --------------------------------------------------------------------- //
00029 // --------------------------------------------------------------------- //
00030 class ConcordeGraph {
00031  public:
00032    int    m_nEdges;
00033    int    m_nVerts;
00034    int  * m_edgeList;
00035    int  * m_edgeValue;
00036 
00037    //index on complete graph to index on complete graph minus d-to-d edges
00038    //int  * m_edgeMapCtoN;
00039    //index on complete graph minus d-to-d edges to index on complete graph
00040    //int  * m_edgeMapNtoC;
00041 
00042  public:
00043  ConcordeGraph() :
00044    m_nEdges        (0),
00045       m_nVerts     (0),
00046       m_edgeList   (0),
00047       m_edgeValue  (0)
00048       //m_edgeMapCtoN(0),
00049       //m_edgeMapNtoC(0)
00050 {};
00051    
00052    void clear(){
00053       m_nEdges   = 0;
00054       m_nVerts   = 0;
00055       UTIL_DELARR(m_edgeList);
00056       UTIL_DELARR(m_edgeValue);
00057       //UTIL_DELARR(m_edgeMapCtoN);
00058       //UTIL_DELARR(m_edgeMapNtoC);
00059    }
00060 
00061    void setEdgeValue(const double * edgeValue){
00062       
00063    }
00064 
00065    void init(const int nVerts,
00066          const int nEdges){
00067       m_nVerts = nVerts;
00068       m_nEdges = nEdges;
00069       if(nEdges > 0){
00070      m_edgeList    = new int[2 * m_nEdges];
00071      m_edgeValue   = new int[    m_nEdges];
00072          //m_edgeMapCtoN = new int[    m_nEdges];
00073          //m_edgeMapNtoC = new int[    m_nEdges];
00074          //UtilFillN(m_edgeMapCtoN, m_nEdges, -1);
00075          //UtilFillN(m_edgeMapNtoC, m_nEdges, -1);
00076      CoinAssertHint(m_edgeList    && m_edgeValue,
00077                         //m_edgeMapCtoN && m_edgeMapNtoC, 
00078                         "Error: Out of Memory");
00079       }
00080    }
00081    
00082    ~ConcordeGraph() {
00083       clear();
00084    };
00085 };
00086 
00087 // --------------------------------------------------------------------- //
00088 // --------------------------------------------------------------------- //
00089 class VRP_Concorde {
00090  public:   
00091    const VRP_Instance * m_vrp;        //ptr to vrp instance
00092    ConcordeGraph        m_cgExpand;   //complete graph expanded
00093    int                * m_CCoptTour;  //store optimal tour out of concorde
00094    double               m_CCoptVal;   //store optimal obj  out of concorde
00095    //tmp storage of doubles (sz = num of original edges)
00096    double             * tmpDblNOrigE;   
00097    //tmp storage of doubles (sz = num of original edges)
00098    int                * tmpIntNOrigE;
00099 
00100  public:
00101  VRP_Concorde() :
00102    m_vrp          (0),
00103       m_cgExpand  ( ) ,
00104       m_CCoptTour (0),
00105       m_CCoptVal  ( ) ,
00106       tmpDblNOrigE( ) ,
00107       tmpIntNOrigE( ) {}
00108    
00109    ~VRP_Concorde() {
00110       UTIL_DELARR(m_CCoptTour);
00111       UTIL_DELARR(tmpDblNOrigE);
00112       UTIL_DELARR(tmpIntNOrigE);
00113    }
00114    
00115  public:
00116 
00118    void init(const VRP_Instance * vrp) {
00119       m_vrp       = vrp;
00120       buildExpandedCompleteGraph();
00121       m_CCoptTour = new int[m_cgExpand.m_nVerts];
00122       CoinAssertHint(m_CCoptTour, "Error: Out of Memory");
00123 
00124       const UtilGraphLib & graphLib  = m_vrp->m_graphLib;
00125       tmpDblNOrigE = new double[graphLib.n_edges];
00126       tmpIntNOrigE = new int   [graphLib.n_edges];
00127       CoinAssertHint(tmpDblNOrigE && tmpIntNOrigE,
00128              "Error: Out of Memory");
00129    }
00130 
00131 
00132    void buildExpandedCompleteGraph(){
00133       //---
00134       //--- To represent a VRP graph as a TSP instance we need to 
00135       //--- create (nRoutes-1) additional dummy depots and  their 
00136       //--- associated customer edges.
00137       //---
00138       //--- Original VRP graph has depot=0 and n_vertices-1 customers
00139       //---    depot => 0
00140       //---       C  => {1,..,n_vertices-1}
00141       //--- Now, we will shift the customers back to index:
00142       //---       C  => {0,..,n_vertices-2}
00143       //--- and make the depot indices 
00144       //---    depot => n_vertices-1, .... n_vertices - 1 + nRoutes
00145       //---
00146       //--- We do not want or need edges between dummy depots. But, it
00147       //--- actually makes the accounting easier to have them. So, we will
00148       //--- include them and treat this like a complete graph but make the
00149       //--- edge weights on depot-depot edges high (or just fix to 0).
00150       //---
00151       //--- NOTE: changed to remove depot-to-depot edges, now using
00152       //---   a mapping for the book-keeping
00153       //---
00154       int i, j, edgeIndex;
00155       const UtilGraphLib & graphLib  = m_vrp->m_graphLib;
00156       const int nRoutes              = m_vrp->m_numRoutes;
00157       int       nCustomers           = graphLib.n_vertices - 1;
00158       int       nVerts               = nCustomers + nRoutes;
00159       int       nEdges               = UtilNumEdgesU(nVerts);
00160       int     * edgeList             = NULL;
00161       //int     * edgeMapCtoN          = NULL;
00162       //int     * edgeMapNtoC          = NULL;
00163       
00164       //---
00165       //--- Assumption: a complete undirected graph, 
00166       //---   (i,j) = (j,i), i!=j (setup for i>j)      
00167       //--- Loop thru edges: i: 1 -> n-1, j: 0 -> i-1
00168       //--- Number of edges: m = (n^2 - n)/2 - (nR^2 - nR)/2
00169       //---
00170       m_cgExpand.init(nVerts, nEdges);
00171       edgeIndex   = 0;
00172       //edgeIndexC  = 0;
00173       edgeList    = m_cgExpand.m_edgeList;
00174       //edgeMapCtoN = m_cgExpand.m_edgeMapCtoN;
00175       //edgeMapNtoC = m_cgExpand.m_edgeMapNtoC;
00176       for(i = 1; i < nVerts; i++){
00177          for(j = 0; j < i; j++){
00178             //printf("(i=%d, j=%d) edgeIndexC:%d edgeIndex:%d", 
00179             //     i,j,edgeIndexC,edgeIndex);
00180             //if(i >= nCustomers && j >= nCustomers)
00181             // printf("  --> depot edge");
00182             //printf("\n");
00183             //edgeMapCtoN[edgeIndexC] = edgeIndex;
00184             //edgeMapNtoC[edgeIndex ] = edgeIndexC;
00185             //exclude depot-to-depot edges            
00186             //if(i < nCustomers || j < nCustomers){
00187                edgeList[2*edgeIndex  ]  = i;
00188                edgeList[2*edgeIndex+1]  = j;
00189                CoinAssert(edgeIndex < nEdges);                           
00190                edgeIndex++;
00191                //}
00192                //edgeIndexC++;
00193      }
00194       }
00195       //TODO: or, open up less, except for m_edgeMapCtoN?
00196       //      m_cgExpand.m_nEdges = edgeIndex;
00197       //assert(m_cgExpand.m_nEdges == 
00198       //     (UtilNumEdgesU(nVerts) - UtilNumEdgesU(nRoutes)));
00199    }
00200    
00201    void setExpandedCost(const double * origGraphCost){
00202       //---
00203       //--- origGraphCost contains the costs based on original graph
00204       //---
00205       //--- Original VRP graph has depot=0 and n_vertices-1 customers
00206       //---    depot => 0
00207       //---       C  => {1,..,n_vertices-1}
00208       //---
00209       const UtilGraphLib & graphLib         = m_vrp->m_graphLib;
00210       const int            nOrigEdges       = graphLib.n_edges;
00211       const int            nOrigVerts       = graphLib.n_vertices;
00212       const int            nRoutes          = m_vrp->m_numRoutes;      
00213       const int            nEdges           = m_cgExpand.m_nEdges;
00214       const int            nCustomers       = nOrigVerts - 1;
00215       double             * origGraphCostDbl = tmpDblNOrigE;
00216       int                * origGraphCostInt = tmpIntNOrigE;
00217       int                * edgeValue        = m_cgExpand.m_edgeValue;
00218       int i;
00219       //---
00220       //--- offset the orig (reduced costs) costs so all positive
00221       //---
00222 #if VRP_CONCORDE_DEBUG > 0  
00223       for(i = 0; i < nOrigEdges; i++){
00224          printf("origGraphCost[%d -> %s]: %10.5f\n", 
00225                 i, UtilEdgeToStr(i).c_str(), origGraphCost[i]);
00226       }
00227 #endif
00228       const double * minElement = min_element(origGraphCost, 
00229                           origGraphCost + nOrigEdges);
00230       const double   offset     = min(0.0, *minElement);
00231 #if VRP_CONCORDE_DEBUG > 0
00232       printf("minElement = %10.5f offset = %10.5f\n", *minElement, -offset);
00233 #endif
00234       memcpy(origGraphCostDbl, origGraphCost, nOrigEdges * sizeof(double));
00235       if(offset < 0.0){
00236      UtilAddOffsetArr(nOrigEdges, -offset, origGraphCostDbl);
00237       }
00238       
00239       //---
00240       //--- scale to integers (do something very simple)
00241       //---    just multiply by 1.0e4 and then round
00242       //---    this should avoid any kind of overflow and
00243       //---    give accuracy at the 4th decimal place which should be
00244       //---    sufficient
00245       //--- NOTE: epsilon=1.0e-6, 1.0e-4 causes overflow issues
00246       //---
00247       //int scaleFactor = 
00248       UtilScaleDblToIntArr(nOrigEdges, 
00249                            origGraphCostDbl,
00250                            origGraphCostInt, 1.0e-3);
00251       //UtilScaleDblToIntArrCC(nOrigEdges, 
00252       //                                   origGraphCostDbl,
00253       //                                   origGraphCostInt);
00254 #if VRP_CONCORDE_DEBUG > 0
00255       //printf("scaleFactor = %d\n", scaleFactor);      
00256       for(i = 0; i < nOrigEdges; i++){
00257          printf("origGraphCost[%d]: %10.5f -> %10d\n", 
00258                 i, 
00259                 origGraphCostDbl[i],
00260                 origGraphCostInt[i]);
00261          //CoinAssert(origGraphCostInt[i] < bigCost);
00262       }
00263 #endif
00264 
00265       //---
00266       //--- find max edge length for "bigM" on depot-to-depot edges
00267       //---   check for integer overflow
00268       //---
00269       int    bigCost    = 0;
00270       double bigCostDbl = 0.0;
00271       int    maxEdgeLen = *max_element(origGraphCostInt,
00272                                        origGraphCostInt+nOrigEdges);
00273       bigCostDbl = ((double)maxEdgeLen+1.0) * (double)m_cgExpand.m_nVerts;
00274       if((256*bigCostDbl) > (double)CCutil_MAXINT) {
00275          printf("WARNING: Large edge lengths!!!!\n");
00276          bigCost = CCutil_MAXINT / 256;         
00277       }
00278       else
00279          bigCost = (maxEdgeLen+1) * m_cgExpand.m_nVerts;
00280       
00281       while(maxEdgeLen > bigCost){
00282          printf("maxEdgeLen=%d > bigCost=%d !!! SCALE BY 10\n",
00283                 maxEdgeLen, bigCost);
00284          //scale by 10
00285          for(i = 0; i < nOrigEdges; i++){
00286             origGraphCostInt[i] /= 10;//and int will trunc it
00287          }
00288          maxEdgeLen /= 10;
00289       }
00290       assert(maxEdgeLen < bigCost);
00291          
00292       //---
00293       //--- shift the customers back to index
00294       //---       C  => {0,..,n_vertices-2}
00295       //--- and make the depot indices 
00296       //---    depot => n_vertices-1, .... n_vertices - 1 + nRoutes
00297       //---                  
00298       //--- set all depot to depot costs to a big number (DON'T NEED)
00299       //---   and
00300       //--- duplicate the original depot to customer edges for dummies
00301       //---
00302       int origDepot = 0;      
00303       int origCost  = 0;
00304       int u, v, d, d1, d2, origIndex, newIndex, custIndex, depot;
00305       for(u = 1; u < nOrigVerts; u++){
00306      for(v = 1; v < u; v++){
00307         origIndex = UtilIndexU(u,v);
00308         newIndex  = UtilIndexU(u-1, v-1);
00309 #if VRP_CONCORDE_DEBUG > 0
00310         printf("origIndex: [%d -> %s] to newIndex: [%d -> %s]\n",
00311                    origIndex, UtilEdgeToStr(origIndex).c_str(),
00312                    newIndex,  UtilEdgeToStr(newIndex).c_str());
00313 #endif
00314             CoinAssert(origGraphCostInt[origIndex] >= 0);            
00315             CoinAssert(origGraphCostInt[origIndex] < bigCost);
00316         edgeValue[newIndex] = origGraphCostInt[origIndex];
00317      }
00318       }
00319       for(u = 1; u <= nCustomers; u++){
00320          //get the original cost of customer to depot
00321      origIndex = UtilIndexU(u, origDepot);
00322          origCost  = origGraphCostInt[origIndex];
00323          //in the concorde graph, the customers are 0..c-1
00324      custIndex = u - 1;
00325          //in the concorde graph, the depots    are c..c+r-1
00326      for(d = 0; d < nRoutes; d++){
00327         depot    = nCustomers + d; 
00328             //get the index in the concorde graph based on complete graph
00329         //newIndex = edgeMapCtoN[UtilIndexU(custIndex, depot)];
00330             newIndex = UtilIndexU(custIndex, depot);
00331         CoinAssert(newIndex < nEdges);
00332             //CoinAssert(origGraphCostInt[origIndex] < bigCost);
00333 #if VRP_CONCORDE_DEBUG > 0
00334             printf("(u:%d,0) origIndex=%d origCost=%d d=%d cInd=%d nInd=%d\n",
00335                    u, origIndex, origCost, d, 
00336                    UtilIndexU(custIndex, depot), newIndex);
00337 #endif
00338         edgeValue[newIndex] = origCost;
00339      }
00340       }
00341       for(d1 = 1; d1 < nRoutes; d1++){
00342      for(d2 = 0; d2 < d1; d2++){
00343         newIndex = UtilIndexU(nCustomers + d1,
00344                   nCustomers + d2);            
00345             edgeValue[newIndex] = bigCost;//bigCost (causing overflow)
00346      }
00347       }
00348 
00349       //#if VRP_CONCORDE_DEBUG > 0
00350       //for(i = 0; i < nEdges; i++){
00351          //printf("newGraphCostInt[%d -> %s]: %d\n", 
00352          //     i, UtilEdgeToStr(i).c_str(), edgeValue[i]);
00353          //printf("newGraphCostInt[%d -> (%d,%d)]: %d\n", 
00354         //        i, 
00355       //     edgeList[2*i],
00356       //        edgeList[2*i+1], 
00357       //        edgeValue[i]);
00358       //}
00359       //#endif
00360    }
00361 
00362    int solveTSP(vector<int>    & vrpRouteInd,
00363         vector<double> & vrpRouteEls){
00364 
00365 
00366       //---
00367       //--- NOTE: using this requires linking with Cplex right now
00368       //---
00369       //--- int CCtsp_solve_dat (int           ncount, 
00370       //---                      CCdatagroup * indat, 
00371       //---                      int         * in_tour,
00372       //---                      int         * out_tour, 
00373       //---                      double      * in_val, 
00374       //---                      double      * optval, 
00375       //---              int         * success,
00376       //---                      int         * foundtour, 
00377       //---          char        * name, 
00378       //---          double      * timebound, 
00379       //---          int         * hit_timebound,
00380       //---          int           silent, 
00381       //---          CCrandstate * rstate);
00382       //---
00383       
00384       //---
00385       //--- Description:
00386       //--- SOLVES the TSP over the graph specfied in the edgelist.
00387       //---   - elist is an array giving the ends of the edges (in pairs)
00388       //---   - elen is an array giving the weights of the edges.
00389       //---   - in_tour gives a starting tour in node node node format (it can
00390       //---     be NULL)
00391       //---   - out_tour will return the optimal tour (it can be NULL, if it is
00392       //---     not NULL then it should point to an array of length at least
00393       //---     ncount.
00394       //---   - in_val can be used to specify an initial upperbound (it can be
00395       //---     NULL)
00396       //---   - optval will return the value of the optimal tour.
00397       //---   - success will be set to 1 if the run finished normally, 
00398       //---     and set to if the search was terminated early (by hitting 
00399       //---     some predefined limit)
00400       //---   - foundtour will be set to 1 if a tour has been found (if success
00401       //---     is 0, then it may not be the optimal tour)
00402       //---   - name specifes a char string that will be used to name various
00403       //---     files that are written during the branch and bound search 
00404       //---     (if it is NULL, then "noname" will be used - this will 
00405       //---     cause problems in a multithreaded program, so specify a 
00406       //---     distinct name in that case).
00407       //---   - silent will suppress most output if set to a nonzero value.
00408       //---
00409       int returnCode = 0;
00410       int silent     = 2;
00411       int success, foundtour, hit_timebound;
00412       
00413       CCrandstate rstate;
00414       int seed       = 1;
00415       CCutil_sprand(seed, &rstate);
00416 
00417 
00418       //do this once
00419       int    i, d1, d2;
00420       const  UtilGraphLib & graphLib = m_vrp->m_graphLib;
00421       int    nRoutes    = m_vrp->m_numRoutes;      
00422       int    nOrigVerts = graphLib.n_vertices;
00423       int    nCustomers = nOrigVerts - 1;
00424       double upbound    = DecompInf;
00425       double optval     = DecompInf;      
00426 
00427       //---
00428       //--- try tiny first, switch if needed... if fails
00429       //---   for now, full blown solver is overkill... ?
00430       //---
00431       int * lower      = new int[m_cgExpand.m_nEdges];
00432       int * upper      = new int[m_cgExpand.m_nEdges];
00433       int * xsol       = new int[m_cgExpand.m_nEdges];
00434       for(i = 0; i < m_cgExpand.m_nEdges; i++){
00435          lower[i] = 0;
00436          upper[i] = 1;
00437          xsol[i]  = 0;
00438       }
00439       for(d1 = 1; d1 < nRoutes; d1++){
00440      for(d2 = 0; d2 < d1; d2++){
00441         upper[UtilIndexU(nCustomers + d1, nCustomers + d2)] = 0;
00442          }
00443       }
00444       returnCode = CCtiny_bnc_msp (m_cgExpand.m_nVerts,
00445                                    m_cgExpand.m_nEdges,
00446                                    m_cgExpand.m_edgeList,
00447                                    m_cgExpand.m_edgeValue,
00448                                    -1,//depot
00449                                    lower, 
00450                                    upper, 
00451                                    &upbound, 
00452                                    CC_TINYTSP_MINIMIZE,
00453                                    &optval, 
00454                                    xsol,
00455                                    1,      //checkresult (make option)
00456                                    1000); //nodelimit
00457 
00458       assert(returnCode != CC_TINYTSP_ERROR);
00459       assert(returnCode != CC_TINYTSP_INFEASIBLE);
00460       bool useFullSolver = false;
00461       if(returnCode == CC_TINYTSP_SEARCHLIMITEXCEEDED){
00462      printf("Search limit exceeded - let's go to full solver\n");
00463      useFullSolver = true;
00464       }
00465 
00466       delete [] lower;
00467       delete [] upper;
00468 
00469       if(useFullSolver){
00470      CCdatagroup dataGroup;
00471      returnCode = CCutil_graph2dat_matrix(m_cgExpand.m_nVerts,      
00472                           m_cgExpand.m_nEdges,
00473                           m_cgExpand.m_edgeList,
00474                           m_cgExpand.m_edgeValue, 
00475                           -1, &dataGroup);      
00476      char nameC[100];
00477      string name = UtilStringRandom(10);
00478      strcpy(nameC, name.c_str());
00479      
00480 #if VRP_CONCORDE_DEBUG > 0
00481      printf("CONCORDE GRAPH:\n");
00482      printf("   nVerts=%d nEdges=%d\n", 
00483         m_cgExpand.m_nVerts,
00484         m_cgExpand.m_nEdges);
00485      for(i =  0; i < m_cgExpand.m_nEdges; i++){
00486         printf("(%4d,%4d) val:%4d\n",
00487            m_cgExpand.m_edgeList[2*i],
00488            m_cgExpand.m_edgeList[2*i+1],
00489            m_cgExpand.m_edgeValue[i]);
00490      }
00491 #endif
00492      
00493      returnCode = CCtsp_solve_dat(m_cgExpand.m_nVerts,
00494                       &dataGroup,
00495                       NULL, //in_tour
00496                       m_CCoptTour,
00497                       NULL, //in_val,
00498                       &m_CCoptVal,
00499                       &success,
00500                       &foundtour,
00501                       nameC,
00502                       NULL, //timebound
00503                       &hit_timebound,
00504                       silent,
00505                       &rstate);
00506      CoinAssert((success == 1) && (foundtour == 1));
00507       }
00508 
00509 #if VRP_CONCORDE_DEBUG > 0    
00510       printf("Optimal Route:\n");
00511 #endif
00512 
00513       
00514       if(!useFullSolver){
00515      vector<int> edgeListSol;
00516      for(i = 0; i < m_cgExpand.m_nEdges; i++){
00517         if(xsol[i]){
00518 #if VRP_CONCORDE_DEBUG > 0
00519            printf("(%d,%d) wt:%d\n", 
00520               m_cgExpand.m_edgeList[2*i],
00521               m_cgExpand.m_edgeList[2*i+1],
00522               m_cgExpand.m_edgeValue[i]);
00523 #endif
00524            edgeListSol.push_back(m_cgExpand.m_edgeList[2*i]);
00525            edgeListSol.push_back(m_cgExpand.m_edgeList[2*i+1]);               
00526         }
00527      }
00528      createVrpRouteFromTspEdgeList(edgeListSol,
00529                        vrpRouteInd,
00530                        vrpRouteEls);
00531       }
00532       else{
00533      createVrpRouteFromTspRoute(m_CCoptTour, 
00534                     m_cgExpand.m_nVerts,
00535                     vrpRouteInd,
00536                     vrpRouteEls);
00537       }
00538       return returnCode;
00539    }
00540    
00541    void createVrpRouteFromTspEdgeList(vector<int>    & tspEdgeList,
00542                                       vector<int>    & vrpRouteInd,
00543                                       vector<double> & vrpRouteEls){
00544       
00545       int i, u, v;
00546       int        nVerts               = m_vrp->m_graphLib.n_vertices;
00547       int        nCustomers           = m_vrp->m_graphLib.n_vertices - 1;
00548       int      * depotEdges           = tmpIntNOrigE;
00549       
00550       //---
00551       //--- keep track of depot edges separate for 1-routes (els=2.0)
00552       //---
00553       UtilFillN(depotEdges, nVerts, 0);
00554 #if VRP_CONCORDE_DEBUG > 0    
00555       printf("Optimal Route:\n");
00556 #endif
00557       for(i = 0; i < m_cgExpand.m_nVerts; i++){
00558          //for(i = 0; i < tspRouteLen-1; i++){
00559          u = tspEdgeList[2*i];
00560          v = tspEdgeList[2*i+1];
00561      u = u >= nCustomers ? 0 : u+1;  
00562      v = v >= nCustomers ? 0 : v+1;
00563      CoinAssert((u + v) > 0);
00564      if(u == 0){
00565         depotEdges[v]++; //(0,v) depot edge
00566      }
00567      else if(v == 0){
00568         depotEdges[u]++; //(u,0) depot edge
00569      }
00570      else{
00571         vrpRouteInd.push_back(UtilIndexU(u,v));
00572 #if VRP_CONCORDE_DEBUG > 0    
00573             printf("(%d,%d) -> %d\n", u, v, UtilIndexU(u,v));
00574 #endif  
00575      } 
00576       }
00577       UtilFillN(vrpRouteEls, vrpRouteInd.size(), 1.0);
00578 
00579       for(v = 1; v < nVerts; v++){
00580      if(depotEdges[v]){
00581         CoinAssert(depotEdges[v] >= 0);
00582         CoinAssert(depotEdges[v] <= 2);
00583         vrpRouteInd.push_back(UtilIndexU(v, 0));
00584         vrpRouteEls.push_back(static_cast<double>(depotEdges[v]));
00585 #if VRP_CONCORDE_DEBUG > 0    
00586             printf("%d D(%d,%d) -> %d\n", 
00587                    depotEdges[v], v, 0, UtilIndexU(v,0));
00588 #endif
00589      }
00590       }
00591    }
00592 
00593    void createVrpRouteFromTspRoute(const int      * tspRoute,
00594                    const int        tspRouteLen,
00595                    vector<int>    & vrpRouteInd,
00596                    vector<double> & vrpRouteEls){
00597                    
00598       int i, u, v;
00599       int        nVerts               = m_vrp->m_graphLib.n_vertices;
00600       int        nCustomers           = m_vrp->m_graphLib.n_vertices - 1;
00601       int      * depotEdges           = tmpIntNOrigE;
00602       
00603       //---
00604       //--- keep track of depot edges separate for 1-routes (els=2.0)
00605       //---
00606       UtilFillN(depotEdges, nVerts, 0);
00607 #if VRP_CONCORDE_DEBUG > 0    
00608       printf("Optimal Route Nodes:");
00609       for(i = 0; i < tspRouteLen; i++){
00610          printf("%d ", tspRoute[i]);
00611       }      
00612       printf("\nOptimal Route Edges:\n");
00613 #endif
00614       for(i = 0; i < tspRouteLen-1; i++){
00615      u = tspRoute[i]   >= nCustomers ? 0 : tspRoute[i]  +1;  
00616      v = tspRoute[i+1] >= nCustomers ? 0 : tspRoute[i+1]+1;
00617      CoinAssert((u + v) > 0);
00618      if(u == 0){
00619         depotEdges[v]++; //(0,v) depot edge
00620      }
00621      else if(v == 0){
00622         depotEdges[u]++; //(u,0) depot edge
00623      }
00624      else{
00625         vrpRouteInd.push_back(UtilIndexU(u,v));
00626      }      
00627 #if VRP_CONCORDE_DEBUG > 0    
00628      printf("(%d,%d) -> %d\n", u, v, UtilIndexU(u,v));   
00629 #endif
00630       }
00631       u = tspRoute[tspRouteLen-1] >= nCustomers ? 0 
00632      : tspRoute[tspRouteLen-1]+1;    
00633       v = tspRoute[0] >= nCustomers ? 0 : tspRoute[0] + 1;
00634       CoinAssert((u + v) > 0);
00635       if(u == 0){
00636      depotEdges[v]++; //(0,v) depot edge
00637       }
00638       else if(v == 0){
00639      depotEdges[u]++; //(u,0) depot edge
00640       }
00641       else{
00642      vrpRouteInd.push_back(UtilIndexU(u,v));
00643       } 
00644 #if VRP_CONCORDE_DEBUG > 0        
00645       printf("(%d,%d) -> %d\n", u, v, UtilIndexU(u,v));
00646 #endif
00647       UtilFillN(vrpRouteEls, vrpRouteInd.size(), 1.0);
00648 
00649       for(v = 1; v < nVerts; v++){
00650      if(depotEdges[v]){
00651         CoinAssert(depotEdges[v] >= 0);
00652         CoinAssert(depotEdges[v] <= 2);
00653         vrpRouteInd.push_back(UtilIndexU(v, 0));
00654         vrpRouteEls.push_back(static_cast<double>(depotEdges[v]));
00655 #if VRP_CONCORDE_DEBUG > 0    
00656             printf("%d D(%d,%d) -> %d\n", 
00657                    depotEdges[v], v, 0, UtilIndexU(v,0));
00658 #endif
00659      }
00660       }
00661    }
00662 
00663    void createTSPLIBFile(const string fileName){
00664       ofstream    os;
00665       int         i, j, edgeIndex;
00666       const int   nVerts    = m_cgExpand.m_nVerts;
00667       const int * edgeValue = m_cgExpand.m_edgeValue;
00668 
00669       printf("Open File %s\n", fileName.c_str());
00670 
00671       UtilOpenFile(os, fileName);
00672       os << "NAME: " << fileName << "\n"
00673      << "TYPE: TSP\n"
00674      << "DIMENSION: " << nVerts << "\n"
00675      << "EDGE_WEIGHT_TYPE: EXPLICIT\n"
00676      << "EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW\n"
00677      << "EDGE_WEIGHT_SECTION\n";
00678       os << " 0\n";
00679       edgeIndex = 0;
00680       for(i = 1; i < nVerts; i++){
00681      for(j = 0; j < i; j++){
00682         os << edgeValue[edgeIndex] << " ";
00683         edgeIndex++;
00684      }
00685      os << " 0\n";
00686       }
00687       os << "EOF\n";
00688 
00689       os.close();
00690    }
00691 
00692 
00693 };
00694 
00695    
00696 #endif

Generated on 3 Jun 2015 for Dip-All by  doxygen 1.6.1