#include <OddCyclesSeparator.hh>
Public Member Functions | |
OddCyclesSeparator (ABA_MASTER *master, StableSetLPSolution *solution, Graph *theGraph, bool flag) | |
~OddCyclesSeparator () | |
virtual void | separate () |
int | getSizeOfClique () const |
int | getCliqueElement (int i) const |
int | getNumberOfOddCycles () const |
int * | getOddCycle (int i) |
Definition at line 38 of file OddCyclesSeparator.hh.
|
Constructor.
Definition at line 38 of file OddCyclesSeparator.cpp. 00040 : 00041 ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 300), 00042 master_(master), 00043 itsGraph(theGraph), 00044 lpSolution(solution), 00045 lifting(flag) 00046 { 00047 }
|
|
Destructor. Definition at line 53 of file OddCyclesSeparator.cpp.
|
|
Get the i-th element of the vector clique.
Definition at line 437 of file OddCyclesSeparator.cpp.
|
|
Get the number of odd cycle inequalities found by this separation.
Definition at line 445 of file OddCyclesSeparator.cpp.
|
|
Get the i-th odd cycle of vector cycle.
Definition at line 453 of file OddCyclesSeparator.cpp.
|
|
Get the size of the vector clique.
Definition at line 429 of file OddCyclesSeparator.cpp. Referenced by StableSetSub::separate().
|
|
This method provides the separation procedure itself and overrides the pure virtual function of ABA_SEPARATOR.
Definition at line 75 of file OddCyclesSeparator.cpp. Referenced by StableSetSub::separate(). 00075 { 00076 00077 00078 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 00079 // Construct the auxiliary graph. 00080 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 00081 // There are two different graphs. The small graph is the graph of the 00082 int i, j, k, l, m; // Loop variables. 00083 int numberOfNodes = lpSolution->nVarCon(); // Number of nodes of the 00084 // complete graph. 00085 int numberOfNonBinaryNodes = 0; // Number of nodes which have 00086 // not a binary value. 00087 vector<int> index(numberOfNodes); // Store the index of each 00088 // node of the new list of 00089 // nodes of the auxiliary 00090 // graph. 00091 vector<int> indexOfNonBinaryNode(numberOfNodes); // This is the translator 00092 // which gives the real index 00093 // of the node of the small 00094 // graph. 00095 int node; // A vertex. 00096 int element; // Another vertex. 00097 int size; // Size of adjazens list: 00098 // complete graph. 00099 int sizeOfList; // size of adjazens list: 00100 // small graph. 00101 int adjazensListSmall[numberOfNodes * (numberOfNodes - 1)]; 00102 int *adjazensPointer; // Pointer to the nodes of the 00103 // adjazens list of the samll 00104 // graph. 00105 int *adjazensList; // Adjazens list of the small 00106 // graph. 00107 long numberOfEdges = 0; // Number of edges in the 00108 // small graph. 00109 double *weight = new double[numberOfNodes * (numberOfNodes - 1)]; 00110 double *solutionValue = lpSolution->zVal(); // Solution of LP. 00111 double *edgeWeight; // Weight of the edges of the 00112 // auxiliary graph. 00113 double eps = master_->machineEps(); // Precision. 00114 00115 00116 // 00117 // First step: get small graph. 00118 // 00119 // Check for each variable: if it has not value 0 and 1, save the index and 00120 // increase counter of the number of non binary nodes. 00121 for (i=0; i<numberOfNodes; i++) { 00122 if ((solutionValue[i] > eps) 00123 && (solutionValue[i] < (1 - eps)) 00124 ) { 00125 index[i] = numberOfNonBinaryNodes; 00126 indexOfNonBinaryNode[numberOfNonBinaryNodes] = i; 00127 numberOfNonBinaryNodes++; 00128 } 00129 else { 00130 index[i] = -1; 00131 } 00132 } 00133 00134 // Add all adjazent nodes but ignore the variables with value 0 or 1. 00135 adjazensPointer = new int[2*numberOfNonBinaryNodes+1]; 00136 adjazensPointer[0] = 0; // All isolated notes will be deleted. 00137 00138 for (i=0; i<numberOfNonBinaryNodes; i++) { 00139 node = indexOfNonBinaryNode[i]; 00140 size = itsGraph->adjacentListSize(node); 00141 sizeOfList = 0; 00142 for (j=0; j<size; j++) { 00143 element = itsGraph->adjacentListElement(node, j); 00144 if (index[element] != -1) { 00145 adjazensListSmall[numberOfEdges] = index[element]; 00146 weight[numberOfEdges++] = 0.5 * (1 - solutionValue[node] - 00147 solutionValue[indexOfNonBinaryNode[index[element]]]); 00148 sizeOfList++; 00149 } 00150 } 00151 if (sizeOfList == 0) { 00152 // Selete isolated nodes. 00153 index.erase(index.begin() + indexOfNonBinaryNode[i]); 00154 indexOfNonBinaryNode.erase(indexOfNonBinaryNode.begin() + i); 00155 numberOfNonBinaryNodes--; 00156 i--; 00157 continue; 00158 } 00159 if (i < (numberOfNonBinaryNodes - 1)) { 00160 adjazensPointer[i+1] = adjazensPointer[i] + sizeOfList; 00161 } 00162 } 00163 00164 // 00165 // Second step: construct auxiliary graph. 00166 // 00167 adjazensList = new int[2*numberOfEdges]; 00168 edgeWeight = new double[2*numberOfEdges]; 00169 00170 // Update adjazensPointer. 00171 for (i=0; i < numberOfNonBinaryNodes; i++) { 00172 adjazensPointer[i + numberOfNonBinaryNodes] = 00173 adjazensPointer[i] + numberOfEdges; 00174 } 00175 adjazensPointer[2*numberOfNonBinaryNodes] = numberOfEdges*2; 00176 00177 // Update adjazensList & calculate new edge weights. 00178 for (i=0; i < numberOfEdges; i++ ) { 00179 adjazensList[i] = numberOfNonBinaryNodes + adjazensListSmall[i]; 00180 adjazensList[i + numberOfEdges] = adjazensListSmall[i]; 00181 00182 edgeWeight[i] = weight[i] + eps * 100; 00183 edgeWeight[i + numberOfEdges] = edgeWeight[i]; 00184 } 00185 00186 // Clean up. 00187 index.clear(); 00188 00189 00190 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 00191 // Construct odd cycles. 00192 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 00193 int predNode[2*numberOfNonBinaryNodes]; // Solution of the shortest path 00194 // algorithm. 00195 int currentNode; // A vertex... 00196 int smallGraphNode; // ...and the corresponding node 00197 // to the small graph 00198 int completeGraphNode; // ...and the corresponding node 00199 // to the complete graph. 00200 int oddCycle[numberOfNonBinaryNodes]; 00201 // Start node of a shortest path. 00202 int start = ((StableSetMaster *)master_)->getRandomNumber( 00203 numberOfNonBinaryNodes); 00204 double shortestPathValue; // Value of a shortest path. 00205 // Minimum violation of the odd cycle inequality to be added. 00206 double tolerance = ((StableSetMaster *)master_)->m_minAbsViolationCycle; 00207 bool inOddCycle[numberOfNonBinaryNodes]; // Markes each node if it is 00208 // allready in a violated odd 00209 // cycle. 00210 int marked[numberOfNonBinaryNodes]; 00211 int marker; 00212 bool found; 00213 double weightOfCycle; 00214 OddCycleConstraint *oddCycleConstr; // Pointer to an odd cycle 00215 // constraint. 00216 00217 // Create ShortestPathCalculator. 00218 ShortestPathCalculator* shortestPath = 00219 new ShortestPathCalculator(2*numberOfNonBinaryNodes, 00220 2*numberOfEdges, 00221 adjazensPointer, 00222 adjazensList, 00223 edgeWeight, 00224 0.5, 00225 eps); 00226 00227 // Calculate for each node of the small graph a shortest path to its 00228 // corresponding copy. But the shortest path is not calculted if it is 00229 // a member of a violated odd cycle inequality which was allready found 00230 // in this separation routine. This is a heuristical approach. 00231 for (i=0; i<numberOfNonBinaryNodes; i++) { 00232 inOddCycle[i] = false; 00233 marked[i] = -1; 00234 } 00235 00236 j = start; 00237 for (i=j; i<j+numberOfNonBinaryNodes; i++) { 00238 start = i % numberOfNonBinaryNodes; 00239 // Calculate a shortest path only if the node is not member of 00240 // violated odd cycle which have allready be found. 00241 if (inOddCycle[start] == true) { 00242 continue; 00243 } 00244 00245 shortestPathValue = shortestPath->calculateShortestPath( 00246 start, start + numberOfNonBinaryNodes, predNode); 00247 00248 // No violated odd cycle inequality found? 00249 if (shortestPathValue > 0.5 - eps) { 00250 continue; 00251 } 00252 00253 // Construct odd cycle. 00254 currentNode = start + numberOfNonBinaryNodes; 00255 size = 0; 00256 weightOfCycle = 0; 00257 while (currentNode != start) { 00258 node = predNode[currentNode]; 00259 currentNode = node; 00260 smallGraphNode = currentNode % numberOfNonBinaryNodes; 00261 // Check if there is an odd cycle part of this cycle. 00262 if (marked[smallGraphNode] != -1) { 00263 weightOfCycle = 0; 00264 marker = marked[smallGraphNode]; 00265 // Odd cycle found. 00266 for (k=0; k<marker; k++) { 00267 marked[oddCycle[k]] = -1; 00268 } 00269 for ( ; k<size; k++) { 00270 node = oddCycle[k]; 00271 oddCycle[k - marker] = node; 00272 completeGraphNode = indexOfNonBinaryNode[node]; 00273 weightOfCycle += solutionValue[completeGraphNode]; 00274 } 00275 // Update size. 00276 size -= marker; 00277 break; // Terminate this while loop. 00278 } 00279 else { 00280 oddCycle[size] = smallGraphNode; 00281 marked[smallGraphNode] = size; 00282 completeGraphNode = indexOfNonBinaryNode[smallGraphNode]; 00283 weightOfCycle += solutionValue[completeGraphNode]; 00284 size++; 00285 } 00286 } 00287 00288 if (weightOfCycle < 0.5*(size-1) + tolerance) { 00289 for(k=0; k<size-1; k++) { 00290 marked[oddCycle[k]] = -1; 00291 } 00292 continue; 00293 } 00294 00295 found = true; 00296 while (found) { 00297 // Check if this cycle has a chord. 00298 for (k=0; k<size-1; k++) { 00299 node = oddCycle[k]; 00300 00301 // Is this node adjacent to the others? 00302 found = false; 00303 l = k+1; 00304 while (l<size && !found && (l+1)%size!=k) { 00305 // Only even differences are possible. 00306 if (!(1 & (l-k))) { 00307 element = oddCycle[l]; 00308 m = adjazensPointer[node]; 00309 00310 while (m<adjazensPointer[node+1] && !found) { 00311 if (adjazensListSmall[m] == element) { 00312 // Chord found. 00313 found = true; 00314 weightOfCycle = 0; 00315 // Construct odd cycle. 00316 for (m=0; m<k; m++) { 00317 marked[oddCycle[m]] = -1; 00318 } 00319 for ( ; m<=l; m++) { 00320 node = oddCycle[m]; 00321 oddCycle[m-k] = node; 00322 completeGraphNode = 00323 indexOfNonBinaryNode[node]; 00324 weightOfCycle += 00325 solutionValue[completeGraphNode]; 00326 } 00327 for ( ; m<size; m++) { 00328 marked[oddCycle[m]] = -1; 00329 } 00330 size = l - k + 1; 00331 break; 00332 00333 }// if 00334 m++; 00335 }// while 00336 if (found) { 00337 break; 00338 } 00339 if (weightOfCycle < 0.5*(size-1) + tolerance) { 00340 break; 00341 } 00342 }//if 00343 l++; 00344 }// while 00345 if (weightOfCycle < 0.5*(size-1) + tolerance) { 00346 break; 00347 } 00348 if (found) { 00349 break; 00350 } 00351 }// for 00352 if (weightOfCycle < 0.5*(size-1) + tolerance) { 00353 break; 00354 } 00355 }// while 00356 00357 00358 // Store this odd cycle to increase it to a maximal clique in the SUB 00359 // problem if it has only 3 nodes. 00360 if (size == 3) { 00361 for(k=0; k<3; k++) { 00362 // Reset marker. 00363 marked[oddCycle[k]] = -1; 00364 // Update flags. 00365 inOddCycle[oddCycle[k]] = true; 00366 // Get node number of complete graph. 00367 completeGraphNode = indexOfNonBinaryNode[oddCycle[k]]; 00368 // Save this clique and increase it in StableSetSub. 00369 clique.push_back(completeGraphNode); 00370 } 00371 } 00372 else { 00373 // If lifting is true, than this odd cycle will be lifted 00374 // to some inequality for the complete graph. Therfore 00375 // the odd cycle inequality may not be valid for the 00376 // reduced graph and we cannot add a odd cycle constraint. 00377 if(lifting) { 00378 // Store the cycle. 00379 int *aCycle = new int[size+1]; 00380 // Store the size of the odd cycle. 00381 aCycle[0] = size+1; 00382 // Convert each element of the small graph to the element 00383 // of the hole graph and store it. 00384 for(k=0; k<size; k++) { 00385 // reset marker 00386 marked[oddCycle[k]] = -1; 00387 // Update flags. 00388 inOddCycle[oddCycle[k]] = true; 00389 completeGraphNode = indexOfNonBinaryNode[oddCycle[k]]; 00390 aCycle[k+1] = completeGraphNode; 00391 00392 } 00393 cycles.push_back(aCycle); 00394 } 00395 else { 00396 // Create new odd cycle constraint and store it with the 00397 // function cutFound(..). In the coresponding sub problem the 00398 // constraints will be added to the pool with the call of the 00399 // function addCons(..). 00400 for(k=0; k<size; k++) { 00401 // Reset marker. 00402 marked[oddCycle[k]] = -1; 00403 inOddCycle[oddCycle[k]] = true; 00404 completeGraphNode = indexOfNonBinaryNode[oddCycle[k]]; 00405 oddCycle[k] = completeGraphNode; 00406 } 00407 oddCycleConstr = new OddCycleConstraint(master_, size, oddCycle,// 00408 itsGraph); 00409 cutFound(oddCycleConstr); 00410 00411 } 00412 } 00413 }// end: for (i=j; i<j+numberOfNonBinaryNodes; i++) { 00414 00415 // Clean up. 00416 // Destroy the object of class ShortestPathCalculator. 00417 delete shortestPath; 00418 delete [] adjazensPointer; 00419 delete [] adjazensList; 00420 delete [] edgeWeight; 00421 delete [] weight; 00422 00423 } // end: void separate()
|