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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : OddCyclesSeparator.cpp
00004 //  Description      : Separate the odd cycle inequalities.
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 15:19:53 2006
00010 //  Last modified by : -
00011 //  Last modified on : -
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
00017 //  ----        ----            ------------------
00018 //
00020 
00021 #include "OddCyclesSeparator.hh"
00022 #include "Graph.hh"
00023 #include "OddCycleConstraint.hh"
00024 #include "ShortestPathCalculator.hh"
00025 #include "StableSetLPSolution.hh"
00026 #include "StableSetMaster.hh"
00027 
00028 
00029 
00030 // -----------------------------------------------------------------------------
00031 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00032 // -----------------------------------------------------------------------------
00033 
00034 
00035 // -----------------------------------------------------------------------------
00036 // C o n s t r u c t o r
00037 // -----------------------------------------------------------------------------
00038 OddCyclesSeparator::OddCyclesSeparator(ABA_MASTER *master,
00039                                        StableSetLPSolution *solution,
00040                                        Graph *theGraph, bool flag):
00041     ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 300),
00042     master_(master),
00043     itsGraph(theGraph),
00044     lpSolution(solution),
00045     lifting(flag)
00046 {
00047 }
00048 
00049 
00050 // -----------------------------------------------------------------------------
00051 // D e s t r u c t o r
00052 // -----------------------------------------------------------------------------
00053 OddCyclesSeparator::~OddCyclesSeparator ()
00054 {
00055     for(int i=cycles.size()-1; i>=0; i--) {
00056         delete [] cycles[i];
00057     }
00058 }
00059 
00060 
00061 // -----------------------------------------------------------------------------
00062 // s e p a r a t e
00063 //
00064 // This function separates odd cycles. Therefore it constucts an auxiliary
00065 // graph. All the nodes which have value 1 are delted before the graph is
00066 // constructed because an violated odd cycle inequality will not include this
00067 // node. After the construction of this graph a shortest path calculator is
00068 // called to produce shortest paths in the new graph with special cost. This
00069 // path can be constructed to a violated odd cycle constraint if the length of
00070 // the path is smaller than 0.5. After a violated odd cycle constraint could be
00071 // found, this function checks the size of the cycle. A 3-cycle will be stored
00072 // and in the sub problem it will be lifted to a max clique. Otherwise the
00073 // corresponding constraint is generated and added to the buffer cutFound().
00074 // -----------------------------------------------------------------------------
00075 void OddCyclesSeparator::separate() {
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()
00424 
00425 
00426 // -----------------------------------------------------------------------------
00427 // g e t S i z e O f C l i q u e
00428 // -----------------------------------------------------------------------------
00429 int OddCyclesSeparator::getSizeOfClique() const {
00430     return clique.size();
00431 }
00432 
00433 
00434 // -----------------------------------------------------------------------------
00435 // g e t C l i q u e E l e m e n t
00436 // -----------------------------------------------------------------------------
00437 int OddCyclesSeparator::getCliqueElement(int i) const {
00438     return clique[i];
00439 }
00440 
00441 
00442 // -----------------------------------------------------------------------------
00443 // g e t N u m b e r O f O d d C y c l e s
00444 // -----------------------------------------------------------------------------
00445 int OddCyclesSeparator::getNumberOfOddCycles() const {
00446     return cycles.size();
00447 }
00448 
00449 
00450 // -----------------------------------------------------------------------------
00451 // g e t O d d C y c l e
00452 // -----------------------------------------------------------------------------
00453 int *OddCyclesSeparator::getOddCycle(int i) {
00454     return cycles[i];
00455 }
00456 
00457 
00458 

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