TSP problem fixed
authorYanhuaSun <sun51@illinois.edu>
Mon, 6 Jun 2011 02:21:17 +0000 (21:21 -0500)
committerYanhuaSun <sun51@illinois.edu>
Mon, 6 Jun 2011 02:21:17 +0000 (21:21 -0500)
examples/charm++/state_space_searchengine/TSP_SE/Makefile
examples/charm++/state_space_searchengine/TSP_SE/data/dj38.tsp
examples/charm++/state_space_searchengine/TSP_SE/main.C
examples/charm++/state_space_searchengine/TSP_SE/searchEngineAPI.C
examples/charm++/state_space_searchengine/searchengineLib/searchEngine.C
examples/charm++/state_space_searchengine/searchengineLib/searchEngine.h
examples/charm++/state_space_searchengine/searchengineLib/searchEngine_impl.h

index 4665963c7cab0766a78bbe6a27bdbf11b33dc5f8..2f4251212b72f026ed7feb0b9ba1c4bb0ea6fd14 100644 (file)
@@ -1,4 +1,4 @@
-OPTS =  -DBRANCHBOUND -DUSEINTPRIORITY #-DSTATISTIC#  -DOPTIMIZE #-DUSEPRIORITY -DOPTIMIZE #-DADPATIVE
+OPTS =  -DBRANCHBOUND #-DSTATISTIC#  -DOPTIMIZE #-DUSEPRIORITY -DOPTIMIZE #-DADPATIVE
 
 OPTS += -I../searchengineLib -L../searchengineLib
 
index 5aec80c9bb178acb9e39fb6bac0b526ce14a5d1d..f3fbe62db7259438b6d161f63c325f3b580d511c 100644 (file)
@@ -5,7 +5,7 @@ COMMENT : This file is a corrected version of dj89, where duplications
 COMMENT:  have been removed.  Thanks to Jay Muthuswamy and others for
 COMMENT:  requesting data sets without duplications.
 TYPE: TSP
-DIMENSION: 38
+DIMENSION : 38
 EDGE_WEIGHT_TYPE: EUC_2D
 NODE_COORD_SECTION
 1 11003.611100 42102.500000
index a8073324f95540e11fe94f977ec08c9c75aeef73..94d1125bb9f3aa80e99133d0873870db547353c2 100644 (file)
@@ -2,7 +2,7 @@
 
 #include "searchEngine.h"
 #include "exampleTsp.h"
-
+#include <time.h>
 #include <vector>
 using namespace std;
 int initial_grainsize;
@@ -34,6 +34,82 @@ int geom_edgelen (int i, int j, CCdatagroup *dat)
      return (int) (6378388.0 * atan2(sqrt(q1*q1 + q2*q2), q5) + 1.0);
 }
 */
+
+void writeOutput()
+{
+    FILE *file;
+    char filename[10];
+    sprintf(filename, "%d.tsp", N);
+    file = fopen(filename, "w");
+    if(file == NULL)
+    {
+        printf("file write error %s\n", filename);
+        CkExit();
+    }
+    fprintf(file, "%d", N);
+    graph.resize(N*N);
+    srand(time(0));
+    for (int i = 0; i < N; i++) {
+        for (int j = 0; j < i; j++) {
+            int edge = (int)( 1.1 * abs( (rand() % 701)) );
+            graph[i*N+j] = edge;
+            graph[j*N+i] = edge;
+            //CkPrintf("%d\t", edge);
+            fprintf(file, "%d ",edge); 
+        }
+        fprintf(file, "\n");
+        //CkPrintf("\n");
+    }
+    fclose(file);
+
+}
+void readinput_2(char* filename)
+{
+    FILE *file;
+
+    char line[128];
+    char value[64];
+    vector<double> xcoord;
+    vector<double> ycoord;
+    int start;
+    int k, j;
+
+    file = fopen(filename, "r");
+    if(file == NULL)
+    {
+        printf("file read error %s\n", filename);
+        CkExit();
+    }
+    /* parse the header lines to get the number of vertices*/
+    fgets(line, 128, file);
+    sscanf(line, "%d", &N);
+    graph.resize(N*N);
+    for(int i=1; i<N; i++)
+    {
+        fgets(line, 128, file);
+        k = 0;
+        start = 0;
+        j=0;
+        while(line[k]!='\0')
+        {
+            if(line[k]==' ')
+            {
+                memcpy(value, line+start, k-start); 
+                value[k-start]='\0';
+                //CkPrintf("value=%s, length=%d",  value, k-start);
+                start = k+1;
+                graph[i*N+j] = atof(value);
+                graph[j*N+i] = atof(value);
+                //CkPrintf("%f ", graph[i*N+j]);
+                j++;
+            }
+            k++;
+        }
+        //CkPrintf("\n");
+    }
+    fclose(file);
+}
+
 void readinput(char* filename)
 {
     FILE *file;
@@ -41,8 +117,8 @@ void readinput(char* filename)
     char line[128];
     char variable[64];
     char value[64];
-    vector<int> xcoord;
-    vector<int> ycoord;
+    vector<double> xcoord;
+    vector<double> ycoord;
 
     file = fopen(filename, "r");
     if(file == NULL)
@@ -65,14 +141,16 @@ void readinput(char* filename)
 
     xcoord.resize(N);
     ycoord.resize(N);
-    int index, x, y; 
+    int index;
+    float x, y; 
     for(int i=0; i<N; i++)
     {
         fgets(line, sizeof line, file);
 
-        sscanf(line, "%d %d %d", &index, &x, &y);
+        sscanf(line, "%d %f %f", &index, &x, &y);
         xcoord[i] = x;
         ycoord[i] = y;
+        CkPrintf("%d %f %f\n", index, x, y);
     }
     graph.resize(N*N);
     for(int i=0; i<N; i++)
@@ -82,6 +160,8 @@ void readinput(char* filename)
             graph[i*N+j]= distance;
             graph[j*N+i]= distance;
         }
+    CkPrintf("Done with reading\n");
+    fclose(file);
 }
  
 
@@ -94,35 +174,24 @@ public:
         int arg_index = 1;
         if(m->argc<2)
         {
-            CkPrintf("Usage: tsp type(0-random graph, 1 inputfile) (Size of Problem) initialgrain\n");
+            CkPrintf("Usage: tsp type(0-random graph, 1 inputfile, 2 inputfile) (Size of Problem) initialgrain\n");
             delete m;
             CkExit();
         }
         int type = atoi(m->argv[1]);
         if(type == 0)
         {
-            // Input Problem parameters
             N = atoi(m->argv[2]);
-            initial_grainsize = atoi(m->argv[3]);
-
-            graph.resize(N*N);
-            // Allocate 2-D array for storing the distance
-            // // Asymmetric Problem
-            for (int i = 0; i < N; i++) {
-                for (int j = 0; j < i; j++) {
-                    int edge = (int)( 1.1 * abs( (rand() % 1000)) );
-                    graph[i*N+j] = edge;
-                    graph[j*N+i] = edge;
-                    CkPrintf("%d\t", graph[i*N+j]);
-                               }
-                CkPrintf("\n");
-                       }
+            writeOutput();
         }else if(type == 1) //read from file
         {
             /* input file */
             readinput(m->argv[2]);
-            initial_grainsize = atoi(m->argv[3]);
+        }else if(type == 2)
+        {
+            readinput_2(m->argv[2]);
         }
+        initial_grainsize = atoi(m->argv[3]);
 
         CkPrintf("start\n");
         searchEngineProxy.start();
index 6bff5b90971c02abc0043dedfb163e0a9d62fefa..e56eca65660a172c9c0b606f055504426b031dd4 100644 (file)
@@ -2,7 +2,6 @@
  * exampleTsp.C
  *
  *  Created on: Mar 4, 2010
- *      Author: gagan
  */
 
 #include "searchEngine.h"
@@ -15,6 +14,7 @@
 #include <algorithm>
 using namespace std;
 
+extern int se_statesize;
 
 /*readonly*/ extern int initial_grainsize;
 #define MAX 100000
@@ -24,8 +24,9 @@ class TspBase: public StateBase
 public:
        int length; // length
        double cost;
+    double lowerBoundValue;
     int *tour;
-    int *intour;
+    int *intour; //whether a node is in tour or not
 
     void initialize()
     {
@@ -36,7 +37,7 @@ public:
     {
         length = parent->length;
         cost = parent->cost;
-
+        lowerBoundValue = parent->lowerBoundValue;
         for(int i=0;i<length; i++)
         {
             tour[i] = parent->tour[i];
@@ -79,17 +80,23 @@ public:
                 lower_sum += m_min+m2_min;
             }
         }
-        return (cost + 0.5*lower_sum); 
+        lowerBoundValue = (cost + 0.5*lower_sum);
+        return lowerBoundValue; 
+    }
+
+    double getLowerBound()
+    {
+        return lowerBoundValue;
     }
 
     void printInfo()
     {
-        CkPrintf(" length=%d, cost=%.4f\n[", length, cost);
+        CkPrintf("\n length=%d, lowerBound=%f", length, lowerBoundValue);
         for(int i=0; i<length; i++)
         {
-            CkPrintf("(%d,%d)", tour[i], intour[tour[i]]);
+            CkPrintf("(%d, value=%f", tour[i], graph[tour[i]*N+tour[(i+1)%N]]);
+            CkPrintf("%d)", intour[tour[i]]);
         }
-        CkPrintf("] lower bound=%f\n", lowerbound());
     }
 };
 
@@ -101,12 +108,13 @@ inline double cost( StateBase *s )
 
 inline double lowerBound( StateBase *s)
 {
-    return ((TspBase*)s)->lowerbound();
+    return ((TspBase*)s)->getLowerBound();
 }
 
 inline void createInitialChildren(Solver *solver)
 {
 
+    se_statesize = sizeof(TspBase)+2*sizeof(int)*N;
     TspBase *state = (TspBase*)solver->registerRootState(sizeof(TspBase)+2*sizeof(int)*N, 0, 1);
     state->initialize();
     state->tour[0]=0;
@@ -114,6 +122,7 @@ inline void createInitialChildren(Solver *solver)
     state->cost = 0;
     for(int i=0; i<N; i++)
         state->intour[i]=0;
+    state->lowerbound();
 #ifdef USEINTPRIORITY
     solver->setPriority(state, (int)lowerBound(state));
 #endif
@@ -125,9 +134,12 @@ inline void createChildren( StateBase *_base , Solver* solver, bool parallel)
 
     TspBase *s = (TspBase*)alloca(sizeof(TspBase)+2*sizeof(int)*N);
     s->initialize();
+    ((TspBase*)_base)->initialize();
     s->copy((TspBase*)_base);
     int childIndex = 0;
     int last = s->tour[s->length-1];
+    int childNum = 0;
+    //CkPrintf("lower bound=%f\n", s->getLowerBound());
     /* construct the current graph, remove all the edges already in the path */
     //s->printInfo();
     for(int j=0; j<N; j++)
@@ -139,12 +151,14 @@ inline void createChildren( StateBase *_base , Solver* solver, bool parallel)
         {
             if(j == 0)
             {
-                s->printInfo();
+                //s->printInfo();
+                //CkPrintf(" cost=%f\n", s->cost+graph[last*N+j]);
                 solver->updateCost(s->cost+graph[last*N+j]);
                 //solver->reportSolution(); 
             }
         }else
         {
+            childNum++;
             TspBase *NewTour  = (TspBase*)solver->registerState(sizeof(TspBase)+2*sizeof(int)*N, childIndex, N);
             NewTour->initialize();
             NewTour->copy(s);
@@ -153,14 +167,15 @@ inline void createChildren( StateBase *_base , Solver* solver, bool parallel)
             NewTour->intour[last] = NewTour->intour[last]+1;
             NewTour->length = s->length + 1;
             NewTour->cost = s->cost + graph[last*N+j];
+            NewTour->lowerbound();
             //NewTour->printInfo();
 #ifdef USEINTPRIORITY
             solver->setPriority(NewTour, (int)lowerBound(NewTour));
 #endif
-            if(parallel)
-                solver->process(NewTour);
+            solver->process(NewTour);
         }
     }
+    //CkPrintf(" %d children created\n", childNum);
 }
 int parallelLevel()
 {
index 4fd2a72bfd74254e48ea335a6633df3d63162fde..7f0a1cf63a3013518733d226514731707ab94c3d 100644 (file)
@@ -14,7 +14,15 @@ using namespace std;
 #include <controlPoints.h>
 #endif
 
-#include "searchEngine_impl.h"
+#include "searchEngine.h"
+
+static SE_createInitialChildrenFn createInitialChildren = NULL;
+static SE_createChildrenFn createChildren = NULL;
+static SE_parallelLevelFn     parallelLevel = NULL;
+static SE_searchDepthLimitFn   searchDepthLimit = NULL;
+SE_lowerBoundFn   _lowerBoundFn = NULL;
+
+//#include "searchEngine_impl.h"
 
 void printPriority(SearchNodeMsg *pm){
 #if defined(USEBITPRIORITY) || defined(USEINTPRIORITY)
@@ -60,12 +68,6 @@ CProxy_SearchConductor searchEngineProxy;
 CProxy_SearchGroup groupProxy;
 
 
-static SE_createInitialChildrenFn createInitialChildren = NULL;
-static SE_createChildrenFn createChildren = NULL;
-static SE_parallelLevelFn     parallelLevel = NULL;
-static SE_searchDepthLimitFn   searchDepthLimit = NULL;
-static SE_lowerBoundFn   lowerBound = NULL;
-
 /****************************** search conductor  main chare */
 SearchConductor::SearchConductor( CkArgMsg *m )
 {
@@ -186,7 +188,29 @@ SearchGroup::SearchGroup()
     minCost = 1000000;
 #endif
 }
-
+#ifdef BRANCHBOUND
+inline void SearchGroup::updateCost(double c)
+{
+    if(c<minCost) 
+    {
+        minCost = c;
+    //   CkPrintf("min cost =%f\n", c);
+    //    void **copyqueue;
+    //    CqsEnumerateQueue((Queue)CpvAccess(CsdSchedQueue), &copyqueue);
+    //    for(int i=0; i<CqsLength((Queue)CpvAccess(CsdSchedQueue)); i++)
+    //    {
+    //        void* msgchare = copyqueue[i];
+    //        int prior = *(int*)CkPriorityPtr(msgchare);
+    //        if(prior > minCost)
+    //        {
+    //              CqsRemoveSpecific((Queue)CpvAccess(CsdSchedQueue), msgchare);
+    //              CkPrintf("node is removed, prior=%d, mincost=%f\n", prior, minCost);
+    //        }
+    //    }
+    //    //CmiFree(copyqueue);
+    }
+}
+#endif
 // This method is invoked via a broadcast. Each branch then reports 
 //  its count to the branch on 0 (or via a spanning tree.)
 inline void SearchGroup::sendCounts()
@@ -284,7 +308,8 @@ SearchNode::SearchNode( SearchNodeMsg *msg )
         solver.setParentInfo(msg, mySearchDepth);
 #ifdef BRANCHBOUND
         double minCost = myGroup->getCost();
-        double lb = lowerBound(mySearchClass);
+        double lb = _lowerBoundFn(mySearchClass);
+        //CkPrintf("best solution is %f\n", minCost);
         if(lb<minCost)
             createChildren(mySearchClass, &solver, true);
         else
@@ -329,7 +354,7 @@ void SE_register(SE_createInitialChildrenFn f1,
   createChildren = f2;
   parallelLevel = f3;
   searchDepthLimit = f4;
-  lowerBound = f5;
+  _lowerBoundFn = f5;
 
   CmiPoolAllocInit(30);
 }
index 4bb969e943b538275bf0b1617edf22d22f6fd3f8..1bb0ffdf3e5e754f5beafb1f27ce7686a3ce5732 100644 (file)
@@ -23,6 +23,7 @@ typedef int (*SE_parallelLevelFn)();
 typedef int (*SE_searchDepthLimitFn)();
 typedef double (*SE_lowerBoundFn)(StateBase *_base);
 
+extern SE_lowerBoundFn   _lowerBoundFn;
 
 void SE_register(SE_createInitialChildrenFn  f1,
                  SE_createChildrenFn  f2,
@@ -67,20 +68,17 @@ extern int se_statesize;
 #define SE_Register(state, f1, f2, f3, f4, f5)  \
     void registerSE() {    \
       SE_register(f1, f2, f3, f4, f5);   \
-      se_statesize = sizeof(state);    \
     }  \
      void createMultipleChildren(SearchGroup* myGroup, StateBase *parent, SequentialSolver* solver, bool parallel) {  \
        StateBase *state;  \
        double minCost = myGroup->getCost(); \
-       double lb = lowerBound(parent); \
+       double lb = f5(parent); \
         if(lb<minCost)  \
             f2(parent, solver, false);  \
-       else  \
-            CkPrintf("Node pruned with lower bound:%f, best solution:%f\n", lb, minCost);  \
         while((state=solver->dequeue()) != NULL) \
         {  \
             minCost = myGroup->getCost(); \
-            lb = lowerBound(parent); \
+            lb = f5(parent); \
             if(lb>=minCost)  \
             continue;  \
             f2(state, solver, parallel); \
@@ -90,7 +88,6 @@ extern int se_statesize;
 #define SE_Register(state, f1, f2, f3, f4, f5)  \
     void registerSE() {    \
       SE_register(f1, f2, f3, f4, f5);   \
-      se_statesize = sizeof(state);    \
     }  \
     void createMultipleChildren(SearchGroup* myGroup, StateBase *parent, SequentialSolver* solver, bool parallel) {  \
        StateBase *state;  \
@@ -99,17 +96,15 @@ extern int se_statesize;
        double instrument_start; \
        double accumulate_time = 0; \
        double minCost = myGroup->getCost(); \
-       double lb = lowerBound(parent); \
+       double lb = f5(parent); \
        instrument_start = CkWallTimer();  \
         if(lb<minCost)  \
             f2(parent, solver, false);  \
-       else  \
-            CkPrintf("Node pruned with lower bound:%f, best solution:%f\n", lb, minCost);  \
         accumulate_time = avgentrytime  = CkWallTimer() - instrument_start;  \
         while((state=solver->dequeue()) != NULL) \
         {  \
             minCost = myGroup->getCost(); \
-            lb = lowerBound(parent); \
+            lb = f5(parent); \
             if(lb>=minCost)  \
             continue;  \
             if(processed_nodes  == 20)  \
@@ -129,7 +124,6 @@ extern int se_statesize;
 #define registerSE_DEF(state, f1, f2, f3, f4)    \
     void registerSE() {    \
       SE_register(f1, f2, f3, f4);   \
-      se_statesize = sizeof(state);    \
     }
 #ifndef ADAPTIVE
 #define SE_Register(state, f1, f2, f3, f4)  \
index 38a5589f9fc2346eeda9fcb7d284881e212134a7..2c0c2e7a70e130e692c32ea98c8a5d701bd3af4b 100644 (file)
@@ -7,7 +7,6 @@
 #ifndef __SEARCHENGINE_IMPL_
 #define __SEARCHENGINE_IMPL_
 
-#include "searchEngine.h"
 
 
 #ifdef BRANCHBOUND
@@ -166,8 +165,8 @@ public:
     void increment() {myCount++;}
 #ifdef BRANCHBOUND
     double getCost() {return minCost;}
-    void  updateCostLocal(double c) { /*CkPrintf("before update best is:%f, new solution:%f\n", minCost, c); */if(c<minCost) minCost = c;}
-    void  updateCost(double c) {}
+    //void  updateCostLocal(double c) { /*CkPrintf("before update best is:%f, new solution:%f\n", minCost, c); */if(c<minCost) minCost = c;}
+    void  updateCost(double c);
 #endif
 #ifdef STATISTIC
     void inc_parallel_generate() {parallelnodes_generate++;}
@@ -228,7 +227,7 @@ inline void Solver::reportSolution()
 inline void Solver::updateCost(double c)
 {
     //CkPrintf("updating best solution:%.4f\n", c);
-    groupProxy.ckLocalBranch()->updateCostLocal(c);
+    groupProxy.updateCost(c);
 }
 #endif
 
@@ -312,6 +311,13 @@ public:
     inline void process(StateBase* s)
     {
         //SearchNodeMsg *msg = *(SearchNodeMsg**)((char*)s - 2*sizeof(void*));
+#ifdef BRANCHBOUND
+        if(_lowerBoundFn(s) >= groupProxy.ckLocalBranch()->getCost())
+        {
+            deleteState(s);
+            return;
+        }
+#endif
         SearchNodeMsg *msg = *((SearchNodeMsg**)s - 2);
         CProxy_SearchNode::ckNew(msg, NULL, -1);
 #ifdef STATISTIC
@@ -536,7 +542,7 @@ public:
 
     inline void setParentInfo(SearchNodeMsg *msg, int l)
     {
-#ifdef USEBITPRIORITY
+#if defined(USEBITPRIORITY) || defined(USEINTPRIORITY)
         parentBits = UsrToEnv(msg)->getPriobits();
         parentPtr = (unsigned int *)(CkPriorityPtr(msg));
 #endif
@@ -564,9 +570,7 @@ public:
         return (StateBase *)stack.push(size);
     }
 
-    inline void process(StateBase *state){}
-
-    /* pop up the top one since it is always a stack */
+       /* pop up the top one since it is always a stack */
     inline void deleteState(StateBase* s)
     {
         StateBase *state = stack.pop();
@@ -578,6 +582,14 @@ public:
 #endif
         }
     }
+    inline void process(StateBase *s)
+    {
+#ifdef BRANCHBOUND
+        if(_lowerBoundFn(s) >= groupProxy.ckLocalBranch()->getCost())
+            deleteState(s);
+        // sort again 
+#endif
+    }
 
     inline void reportSolution()
     {