OddCyclesSeparator Class Reference

#include <OddCyclesSeparator.hh>

List of all members.

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)


Detailed Description

This class provides an exact separation procedure for odd cycle constraints.

Definition at line 38 of file OddCyclesSeparator.hh.


Constructor & Destructor Documentation

OddCyclesSeparator::OddCyclesSeparator ABA_MASTER *  master,
StableSetLPSolution solution,
Graph theGraph,
bool  flag
 

Constructor.

Parameters:
*master Pointer to the master of the problem.
*solution A pointer to the current LP-Solution to be separated.
*theGraph Pointer to the graph storing all information about the problem instance.
flag If its value is true the odd cycles will be lifted.

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 }

OddCyclesSeparator::~OddCyclesSeparator  ) 
 

Destructor.

Definition at line 53 of file OddCyclesSeparator.cpp.

00054 {
00055     for(int i=cycles.size()-1; i>=0; i--) {
00056         delete [] cycles[i];
00057     }
00058 }


Member Function Documentation

int OddCyclesSeparator::getCliqueElement int  i  )  const
 

Get the i-th element of the vector clique.

Parameters:
void 
Returns:
i-th element of vector clique.

Definition at line 437 of file OddCyclesSeparator.cpp.

00437                                                     {
00438     return clique[i];
00439 }

int OddCyclesSeparator::getNumberOfOddCycles  )  const
 

Get the number of odd cycle inequalities found by this separation.

Parameters:
void 
Returns:
Size of vector cycles.

Definition at line 445 of file OddCyclesSeparator.cpp.

00445                                                    {
00446     return cycles.size();
00447 }

int * OddCyclesSeparator::getOddCycle int  i  ) 
 

Get the i-th odd cycle of vector cycle.

Parameters:
void 
Returns:
i-th element of vector cycle.

Definition at line 453 of file OddCyclesSeparator.cpp.

00453                                           {
00454     return cycles[i];
00455 }

int OddCyclesSeparator::getSizeOfClique  )  const
 

Get the size of the vector clique.

Parameters:
void 
Returns:
Size of vector clique.

Definition at line 429 of file OddCyclesSeparator.cpp.

Referenced by StableSetSub::separate().

00429                                               {
00430     return clique.size();
00431 }

void OddCyclesSeparator::separate  )  [virtual]
 

This method provides the separation procedure itself and overrides the pure virtual function of ABA_SEPARATOR.

Parameters:
void 
Returns:
void

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()


The documentation for this class was generated from the following files:
Generated on Fri Apr 28 15:50:00 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO