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