C:/Programme/home/Administrator/CD/stableSetCode/ImprovementHeuristic.cpp

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : ImprovementHeuristic.cpp
00004 //  Description      :
00005 //  Author           : Steffen Rebennack
00006 //  Email            : srebenac@ix.urz.uni-heidelberg.de;
00007 //                     steffen.rebennack@web.de
00008 //  Copyright        : (C) 2006 by the University of Heidelberg
00009 //  Created on       : Wed Apr 05 13:55:54 2006
00010 //  Last modified by : -
00011 //  Last modified on : -
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
00017 //  ----        ----            ------------------
00018 //
00020 
00021 
00022 #include "ImprovementHeuristic.hh"
00023 #include "Graph.hh"
00024 #include "StableSetMaster.hh"
00025 #include "StableSetStatistics.hh"
00026 
00027 
00028 
00029 // -----------------------------------------------------------------------------
00030 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00031 // -----------------------------------------------------------------------------
00032 
00033 
00034 // -----------------------------------------------------------------------------
00035 // C o n s t r u c t o r
00036 // -----------------------------------------------------------------------------
00037 ImprovementHeuristic::ImprovementHeuristic(ABA_MASTER *master, Graph *theGraph,
00038                                            StableSetStatistics *theStatistics):
00039     master_(master),
00040     itsGraph(theGraph),
00041     itsStatistics(theStatistics)
00042 {
00043 }
00044 
00045 
00046 // -----------------------------------------------------------------------------
00047 // D e s t r u c t o r
00048 // -----------------------------------------------------------------------------
00049 ImprovementHeuristic::~ImprovementHeuristic() {
00050 }
00051 
00052 
00053 // -----------------------------------------------------------------------------
00054 // i m p r o v e
00055 //
00056 // Start with a stable set. Check for three nodes of the stable set if there
00057 // are two path of length 3 which connect two of them. If there is such a path
00058 // with the property that no node of the path is adjacent to one node of the
00059 // current stable set then you can improve the stable set.
00060 // -----------------------------------------------------------------------------
00061 int ImprovementHeuristic::improve(double &value) {
00062 
00063     clock_t t1 = clock();       // Get current time.
00064 
00065     int i, j, k;        // Loop counter.
00066     int cnt;            // Counter.
00067     int cnt2;
00068     int vertex;         // A node.
00069     int indexOfVertex;  // Index of node vertex.
00070     int indexOfNode;
00071     int node;
00072     int index;
00073     int nodeOfPathOne;
00074     int nodeOfPathTwo;
00075     int v11, v12, v13;  // Three nodes of a path.
00076     int v21, v22, v23;  // Three nodes of a path.
00077     int beginOne;
00078     int beginTwo;
00079     int stack;
00080     int member;
00081     int status = 0;     // Return value;
00082     double timeLimit = stableSetMaster()->m_timeLimitForImprovementHeuristic;
00083     vector<int> *solution = stableSetMaster()->getSolution();
00084     if (solution->size() <= 2) {
00085         return status;
00086     }
00087 
00088     //
00089     // Improve until time limit is reached.
00090     //
00091     while (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC) {
00092 
00093         // Choose randomly two nodes to start from.
00094         indexOfVertex = stableSetMaster()->getRandomNumber(solution->size());
00095         vertex = (*solution)[indexOfVertex];
00096         index  = stableSetMaster()->getRandomNumber(solution->size());
00097         if (index == indexOfVertex) {
00098             index++;
00099             index = index % solution->size();
00100         }
00101         node = index +1;
00102         node = node % solution->size();
00103         if (node == indexOfVertex) {
00104             node++;
00105             node = node % solution->size();
00106         }
00107         cnt  = 0;
00108         v11 = -1;
00109         v12 = -1;
00110         while((cnt < 2) && (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC)) {
00111             if (node == index) {
00112                 break;
00113             }
00114             // Find path from 'vertex' to '(*solution)[node]' with length 3.
00115             if (calculateDistance(vertex, (*solution)[node], v11, v12, v21,
00116                                   v22)) {
00117                 cnt++;
00118                 if (cnt == 1) {
00119                     v13 = (*solution)[node];
00120                 }
00121                 else {
00122                     v23 = (*solution)[node];
00123                 }
00124             }
00125             node++;
00126             node = node % solution->size();
00127             if (node == indexOfVertex) {
00128                 node++;
00129                 node = node % solution->size();
00130             }
00131         }
00132         
00133         //
00134         // Two paths have been computed. Try to improve the stable set.
00135         //
00136         if (cnt == 2) {
00137 
00138             cnt2 = 0;
00139             // Solution is allways sorted!
00140             beginOne = 0;
00141             beginTwo = 0;
00142             for (j=0; j<solution->size(); j++) {
00143                 stack = (*solution)[j];
00144                 if (stack != vertex) {
00145                     if(itsGraph->isMemberOfAdjacentList(v11, beginOne, stack)) {
00146                         cnt2++;
00147                         member = stack;
00148                     }
00149                     else {
00150                         if(itsGraph->isMemberOfAdjacentList(v21, beginTwo,
00151                                                             stack)) {
00152                             cnt2++;
00153                             member = stack;
00154                         }
00155                     }
00156                 }
00157                 if (cnt2 > 1) {
00158                     break;
00159                 }
00160             }
00161  
00162             //
00163             // If cnt = 0 the new stable set will have a greater size.
00164             //
00165             if (cnt2 < 2) {
00166                 // Update solution.
00167                 solution->erase(solution->begin() + indexOfVertex);
00168                 if (cnt2 == 1) {
00169                     k = 0;
00170                     while ((*solution)[k] != member) {
00171                         k++;
00172                     }
00173                     solution->erase(solution->begin() + k);
00174                 }
00175 
00176                 solution->push_back(v11);
00177                 solution->push_back(v21);
00178                 sort(solution->begin(), solution->end());
00179                 testStableSet(solution);
00180                 if (cnt2 == 0) {
00181                     itsStatistics->improvementHeuristics();
00182                 }
00183             }
00184         }
00185 
00186     }
00187 
00188     value = 1.0*solution->size();
00189 
00190     // Update bounds.
00191     if (master_->betterPrimal(value)) {
00192         // Heuristic found better solution.
00193         master_->out() << "\nImprovement of heuristic was successful:\n";
00194         master_->out() << "\tNew value:\t" << value << endl;
00195         
00196         // Update lower bound (best known feasible solution)
00197         // (this is done automatically by ABACUS, too).
00198         master_->primalBound(value);
00199    
00200         // Update statistics.
00201         itsStatistics->solutionFound(2);
00202 
00203         status = 1;
00204     }
00205 
00206     // Return with status.
00207     return status;
00208 
00209 }// int improve(..)
00210 
00211 
00212 
00213 // -----------------------------------------------------------------------------
00214 // -------------- M e t h o d s  ( p r i v a t e ) -----------------------------
00215 // -----------------------------------------------------------------------------
00216 
00217 
00218 // -----------------------------------------------------------------------------
00219 // c a l c u l a t e D i s t a n c e
00220 //
00221 // Find path from node 'start' to node 'end' with length 3. Store the nodes
00222 // of the path in n11, n12, n21 or n22.
00223 // -----------------------------------------------------------------------------
00224 bool ImprovementHeuristic::calculateDistance(int start, int end, int &n11,
00225                                              int &n12, int &n21, int &n22)
00226                                              const {
00227 
00228     int i, j, k, l;  // Loop counter.
00229     int startSize = itsGraph->adjacentListSize(start);
00230     int endSize   = itsGraph->adjacentListSize(end);
00231     int indexOne  = ((StableSetMaster *)master_)->getRandomNumber(startSize);
00232     int indexTwo;
00233     int vertex;
00234     int node;
00235     int index;
00236     vector<int> *solution = ((StableSetMaster*)master_)->getSolution();
00237 
00238     //
00239     // Check all adjacent nodes to the start node.
00240     //
00241     for (i=0; i<startSize; i++) {
00242         vertex   = itsGraph->adjacentListElement(start, indexOne);
00243         indexTwo = ((StableSetMaster *)master_)->getRandomNumber(endSize);
00244         index = 0;
00245         //
00246         // Check all adjacent nodes to the end node.
00247         //
00248         for (j=0; j<endSize; j++) {
00249             node = itsGraph->adjacentListElement(end, indexTwo);
00250             l = 0;
00251             if(itsGraph->isMemberOfAdjacentList(vertex, index, node)
00252                && (node != n11) && (node != n12)
00253                && (vertex != n11) && (vertex != n12)
00254                && ((n11 == -1) || !itsGraph->isMemberOfAdjacentList(n11, l,
00255                                                          vertex))
00256               ) {
00257                 // Look for vertex in stable set solution.
00258                 k = 0;
00259                 while ((k < (solution->size()-1))
00260                        && ((*solution)[k] < vertex)
00261                       ) {
00262                     k++;
00263                 }
00264                 if ((*solution)[k] == vertex) {
00265                     continue;
00266                 }
00267                 k = 0;
00268                 while ((k < (solution->size()-1))
00269                        && ((*solution)[k] < node)
00270                       ) {
00271                     k++;
00272                 }
00273                 if ((*solution)[k] == node) {
00274                     continue;
00275                 }
00276                 if (n11 == -1) {
00277                     n11 = vertex;
00278                     n12 = node;
00279                 }
00280                 else {
00281                     n21 = vertex;
00282                     n22 = node;
00283                 }
00284 
00285                 return true;
00286             }
00287             indexTwo++;
00288             indexTwo = indexTwo % endSize;
00289             if (indexTwo == 0) {
00290                 index = 0;
00291             }
00292         }
00293         indexOne++;
00294         indexOne = indexOne % startSize;
00295     }
00296 
00297     return false;
00298 }// bool calculateDistance(..)
00299 
00300 
00301 // -----------------------------------------------------------------------------
00302 // t e s t S t a b l e S e t
00303 // -----------------------------------------------------------------------------
00304 void ImprovementHeuristic::testStableSet(vector<int> *stableSet) {
00305 
00306     int i, j, l;  // Loop counter
00307 
00308     for (i=1; i<stableSet->size(); i++) {
00309         for (j=(i-1); j>=0; j--) {
00310             l = 0;
00311             if (itsGraph->isMemberOfAdjacentList((*stableSet)[i], l,
00312                                                         (*stableSet)[j])) {
00313                 master_->err() << "ImprovementHeuristic::testStableSet:\t";
00314                 master_->err() << "The constructed vector is no stable set!\n";
00315                 master_->err() << "Solution:\t";
00316                 for (l=0; l<stableSet->size(); l++) {
00317                     master_->err() << (*stableSet)[l] << " ";
00318                 }
00319                 master_->err() << endl;
00320                 exit(master_->Fatal);
00321             }// if
00322         }
00323     }// for
00324 }
00325 
00326 
00327 // -----------------------------------------------------------------------------
00328 // s t a b l e S e t M a s t e r
00329 //
00330 // This function returns a pointer to the corresponding object of the class
00331 // StableSetMaster.
00332 // -----------------------------------------------------------------------------
00333 StableSetMaster *ImprovementHeuristic::stableSetMaster() {
00334    return ((StableSetMaster *)master_);
00335 }
00336 
00337 
00338 
00339 
00340 
00341 
00342 
00343 

Generated on Fri Apr 28 15:49:59 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO