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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : MaxCliquesSeparator.cpp
00004 //  Description      : Exact clique separation.
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 14:49:52 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 "MaxCliquesSeparator.hh"
00023 #include "Clique.hh"
00024 #include "CliqueConstraint.hh"
00025 #include "Graph.hh"
00026 #include "StableSetLPSolution.hh"
00027 #include "StableSetMaster.hh"
00028 
00029 
00030 
00031 // -----------------------------------------------------------------------------
00032 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00033 // -----------------------------------------------------------------------------
00034 
00035 
00036 // -----------------------------------------------------------------------------
00037 // C o n s t r u c t o r
00038 //
00039 // The main part of this constructor is the initialization of the abstract
00040 // template class ABA_SEPARATOR. The second argument is true because we do
00041 // not want double constraints in the buffer and the nuber 500 states the
00042 // maximla number of cuttings planes which are stored.
00043 // -----------------------------------------------------------------------------
00044 MaxCliquesSeparator::MaxCliquesSeparator(ABA_MASTER *master,
00045                         StableSetLPSolution *solution, Graph *theGraph,
00046                         Clique *clique):
00047     ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 500),
00048     master_(master),
00049     lpSolution(solution),
00050     itsGraph(theGraph),
00051     maxCliques(clique)
00052 {
00053 }
00054 
00055 
00056 // -----------------------------------------------------------------------------
00057 // D e s t r u c t o r
00058 // -----------------------------------------------------------------------------
00059 MaxCliquesSeparator::~MaxCliquesSeparator() {
00060 }
00061 
00062 
00063 // -----------------------------------------------------------------------------
00064 // s e p a r a t e
00065 //
00066 // This function initializes the exact separation of the max clique
00067 // inequalities. It constructs the last maximal clique found and calls the
00068 // function getNextClique(..) untill the timelimit is reached or all maximal
00069 // cliques have been computed. If one clique is found this function adds the
00070 // coresponding inequality only if the clique is a new one and the weight of
00071 // the clique is greater than 1 plus a tolerance.
00072 // -----------------------------------------------------------------------------
00073 void MaxCliquesSeparator::separate() {
00074 
00075     clock_t t1 = clock();       // Get current time.
00076 
00077     int    i;                   // Loop variable.
00078     int    cliqueSize;          // Size of a clique.
00079     int    *lastClique;         // Store a clique.
00080     bool   maxCliqueFound;      // true if a maximal clique has been computed.
00081     bool   added;               // true if a clique could be added.
00082     bool   fixed;               // true if the variables of the clique could
00083                                 // be fixed.
00084     double weight;              // Weight of a clique.
00085     double *solutionValue = lpSolution->zVal();     // LP solution
00086     double minViolation = stableSetMaster()->m_minAbsViolationClique;
00087     double timeLimit = stableSetMaster()->m_timeLimitForMaxCliqueSep;
00088     vector<int> nodesOfClique;  // Store the nodes of a clique.
00089     CliqueConstraint *cliqueConstr;     // Pointer to clique constraint.
00090 
00091 
00092     // Fill vector nodesOfClique with last found max clique.
00093     lastClique = maxCliques->getLastMaxClique();
00094     if (lastClique != NULL) {
00095         cliqueSize = lastClique[0];
00096         nodesOfClique.resize(cliqueSize);
00097         for (i=0; i<cliqueSize; i++) {
00098             nodesOfClique[i] = lastClique[i+1];
00099         }
00100     }
00101     else {
00102         // No cliques found, yet.
00103         nodesOfClique.push_back(-1);
00104     }
00105 
00106     // Produce new maximal cliques untill time limit is reached
00107     // or all cliques are computed.
00108     while ((!maxCliques->allMaximalCliquesFound())
00109            && (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC)
00110           ) {
00111         // Compute next maximal clique.
00112         maxCliqueFound = getNextClique(&nodesOfClique);
00113         if (!maxCliqueFound) {
00114             continue;
00115         }
00116 
00117 
00118         // Store this clique if it is not part of a greater one and non of
00119         // its variables could be fixed!
00120         added = maxCliques->addMaxClique(&nodesOfClique);
00121         if (!added) {
00122             continue;
00123         }
00124 
00125         // This clique is a new maximal clique and therefore we
00126         // compute the weight of it.
00127 
00128         weight = 0;
00129         for (i=0; i<nodesOfClique.size(); i++) {
00130             weight += solutionValue[nodesOfClique[i]];
00131         }
00132 
00133         if (weight >= 1 + minViolation) {
00134             // This clique constraint is violated.
00135             // So we have a new clique costraint to be added.
00136             cliqueConstr = new CliqueConstraint(master_, &nodesOfClique, itsGraph);
00137             cutFound(cliqueConstr);
00138         }
00139     }// end: while(..)
00140 
00141 
00142 } // end: void separate()
00143 
00144 
00145 
00146 // -----------------------------------------------------------------------------
00147 // --------------- M e t h o d s  ( p r i v a t e ) ----------------------------
00148 // -----------------------------------------------------------------------------
00149 
00150 
00151 // -----------------------------------------------------------------------------
00152 // g e t N e x t C l i q u e
00153 //
00154 // This function computes the next maximal clique in the following way:
00155 // 1.) Delete last node of clique 'nodesOfClique'
00156 //     (if it has only one member: increase this node)
00157 // 2.) Find all adjacent nodes to the vertecies of the clique and store them in
00158 //     vector 'adjacentNodes'.
00159 // 3.) If there are no adjacent nodes -> goto 1.)
00160 //     Else increase clique until there are no more adjacent nodes.
00161 // The function returns true, if a max clique inequality could be found;
00162 // else the returned value is false. In the latter case all maximal cliques
00163 // are found.
00164 // -----------------------------------------------------------------------------
00165 bool MaxCliquesSeparator::getNextClique(vector<int> *nodesOfClique) const {
00166 
00167     int  i, j;             // Loop counter.
00168     int  lastNode;         // Save node which has been deleted from the clique.
00169     int  node;             // A node.
00170     int  vertex;           // A vertex.
00171     int  nodeOfClique;     // Node of the clique.
00172     int  minIndex;         // Index of node with the minimal size of its
00173                            // adjacent list.
00174     int  minValue = -1;    // Size of the adjacent list of the node
00175                            // corresponding to minIndex
00176     int  adjacentListSize; // Size of an adjacent list.
00177     int  numberOfNodes = itsGraph->numberOfNodes();
00178     int  cliqueSize = nodesOfClique->size();
00179     int  begin[cliqueSize];
00180     vector<int> adjacentNodes;  // Store all adjacent nodes of the clique
00181                                 // 'nodesOfClique'.
00182     bool found;            // Flag which shows if something is found.
00183 
00184     for (i=0; i<cliqueSize; i++) {
00185         begin[i] = 0;
00186     }
00187 
00188 
00189     // Delete last element of vector nodesOfClique.
00190     if (cliqueSize == 1) {
00191         // Only one element in this vector
00192         // -> increase this node to search for new cliques.
00193         lastNode = (*nodesOfClique)[0];
00194         if (lastNode < (numberOfNodes - 1)) {
00195             (*nodesOfClique)[0] = lastNode + 1;
00196         }
00197         else {
00198             maxCliques->setAllCliquesFound();
00199             return false;
00200         }
00201     }
00202     else {
00203         lastNode = nodesOfClique->back();
00204         nodesOfClique->pop_back();
00205         --cliqueSize;
00206     }
00207 
00208      // Get element with minimal number of adjacent nodes.
00209     for (i=0; i<cliqueSize; i++) {
00210         adjacentListSize = itsGraph->adjacentListSize((*nodesOfClique)[i]);
00211         if ((adjacentListSize < minValue) || (minValue == -1)) {
00212             minValue = adjacentListSize;
00213             minIndex = i;
00214         }
00215     }
00216     nodeOfClique = (*nodesOfClique)[minIndex];
00217 
00218     // Compute all adjacent nodes to the nodes of the clique stored in
00219     // nodesOfClique.
00220     adjacentListSize = itsGraph->adjacentListSize(nodeOfClique);
00221     for (i=0; i<adjacentListSize; i++ ) {
00222         // Ignore all nodes, which have allready been checked.
00223         vertex = itsGraph->adjacentListElement(nodeOfClique, i);
00224         if((vertex > (*nodesOfClique)[0]) && (vertex > lastNode)) {
00225             // Check for all other nodes:
00226             // Is vertex adjacent to all other nodes of the clique?
00227             found = true;
00228             j = 0;
00229             while ((j < cliqueSize) && found) {
00230                 node = (*nodesOfClique)[j];
00231                 if((minIndex != j) && (vertex != node)) {
00232                     found = itsGraph->isMemberOfAdjacentList(node, begin[j],
00233                                                                  vertex);
00234                 }
00235                 j++;
00236             }
00237 
00238             if (found || (cliqueSize == 1)) {
00239                 adjacentNodes.push_back(vertex);
00240             }
00241         }// end: if
00242     }// end: for
00243 
00244     if (adjacentNodes.size() == 0) {
00245         // No max clique possible.
00246         return getNextClique(nodesOfClique);
00247     }
00248     else {
00249         // Increase clique untill there are no more adjacent nodes.
00250         while (true) {
00251             // Add the first node of the adjacent list to the clique.
00252             node = adjacentNodes[0];
00253             nodesOfClique->push_back(node);
00254             adjacentNodes.erase(adjacentNodes.begin());
00255             j = 0;
00256 
00257             // Update adjacent nodes:
00258             // find out for each node of the adjacent list if it is also
00259             // adjacent to the new added node.
00260             for (i=0; i<adjacentNodes.size(); i++) {
00261                 // Find node adjacentNodes[i] in adjacent list of node.
00262                 if(!itsGraph->isMemberOfAdjacentList(node, j,
00263                                                      adjacentNodes[i])) {
00264                     // This node is not a memebr of the adjacent list
00265                     // -> delete this node.
00266                     adjacentNodes.erase(adjacentNodes.begin() + i);
00267                     i--;
00268                 }
00269             }
00270 
00271             // If vector adjacentNodes is empty than there are no more
00272             // adjacent nodes in the graph to the nodes of the clique of
00273             // vector nodesOfClique. You have to check if the clique
00274             // is great enough - all cliques with size 2 are ignored.
00275             // The check if the clique is a new one or only a subset of a
00276             // greater clique is done by the function separate().
00277             if (adjacentNodes.empty() && nodesOfClique->size() > 2) {
00278                 // New maximal clique found.
00279                 return true;
00280             }
00281             else {
00282                 if(adjacentNodes.empty()) {
00283                     return getNextClique(nodesOfClique);
00284                 }
00285             }
00286         }
00287     }// else
00288 
00289 }// end: bool getNextClique(..)
00290 
00291 
00292 // -----------------------------------------------------------------------------
00293 // s t a b l e S e t M a s t e r
00294 //
00295 // This function returns a pointer to the corresponding object of the class
00296 // StableSetMaster.
00297 // -----------------------------------------------------------------------------
00298 StableSetMaster *MaxCliquesSeparator::stableSetMaster() {
00299    return (StableSetMaster *)master_;
00300 }
00301 
00302 

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