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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : CliqueHeuristicsSeparator.cpp
00004 //  Description      : Separate the clique inequalities with heuristics.
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       : Tue Apr 04 14:16: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 
00022 #include "CliqueHeuristicsSeparator.hh"
00023 #include "CliqueConstraint.hh"
00024 #include "Graph.hh"
00025 #include "StableSetMaster.hh"
00026 #include "StableSetLPSolution.hh"
00027 
00028 
00029 
00030 // -----------------------------------------------------------------------------
00031 // C o n s t r u c t o r
00032 // -----------------------------------------------------------------------------
00033 CliqueHeuristicsSeparator::CliqueHeuristicsSeparator(
00034                                        StableSetLPSolution *solution,
00035                                        Graph *theGraph):
00036     ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 300),
00037     itsGraph(theGraph),
00038     lpSolution(solution)
00039 {
00040 }
00041 
00042 
00043 // -----------------------------------------------------------------------------
00044 // D e s t r u c t o r
00045 // -----------------------------------------------------------------------------
00046 CliqueHeuristicsSeparator::~CliqueHeuristicsSeparator ()
00047 {
00048 }
00049 
00050 
00051 // -----------------------------------------------------------------------------
00052 // s e p a r a t e
00053 //
00054 // Construct randomly maximAL cliques. Start with an edge and lift ist to a
00055 // maximAL clique. The procedure is stopped until the maximal iteration number
00056 // is reached or enough inequalities have been computed.
00057 // -----------------------------------------------------------------------------
00058 void CliqueHeuristicsSeparator::separate() {
00059 
00060     int i, j;           // Loop counter.
00061     int index;          // Index to a node.
00062     double value;       // The value of the clique in the current LP-solution.
00063     vector< vector<int> > computedCliques; // Store all computed cliques.
00064     vector<int> clique(2);      // This stores the maximAL clique.
00065     vector<int> adjacentNodes;  // Set of nodes adjacent to the current clique.
00066     int size = itsGraph->numberOfNodes(); // Size of the graph.
00067     int cnt = 0;        // Counter.
00068     bool found;         //
00069     bool newOne;        // Indicate if a clique is new or have been computed
00070                         // earlier.
00071     int theCnt = 0;     // Counter.
00072     int cutCnt = 0;     // Counter for the generated cuts.
00073     int begin = 0;      // Index to check in adjacent list.
00074     double *solution = lpSolution->zVal();  // Current LP-solution.
00075     CliqueConstraint *cliqueConstr;         // Pointer to a clique sontraint
00076                                             // To store each computed clique in
00077                                             // Buffer cutfound().
00078     int level = lpSolution->sub()->level();
00079 
00080 
00081     //
00082     // Parameter.
00083     //
00084     static const int    MAX_ITER_SEP  = level==1 ? size * 1.5 : size / 3;
00085     static const int    MAX_STEP      = level==1 ? size / 4 : (int)( 5 + 0.01 * size );
00086     static const int    MAX_CUTS      = level==1 ? size : size / 5;
00087     static const double MIN_VIOLATION = 0.0001;
00088 
00089 
00090     //
00091     // Construct maximAL cliques.
00092     //
00093     while ( ((cnt < MAX_ITER_SEP) || theCnt < MAX_STEP)
00094             && (cutCnt < MAX_CUTS) ) {
00095 
00096         //
00097         // Select edge to start from.
00098         //
00099         found = false;
00100         while (!found) {
00101             clique[0] = getRandomNumber(size);
00102             clique[1] = getRandomNumber(size);
00103             if (clique[0] != clique[1]) {
00104                 if (clique[0] > clique[1]) {
00105                     begin = 0;
00106                     if (itsGraph->isMemberOfAdjacentList(clique[0], begin,
00107                                                          clique[1])) {
00108                         found = true;
00109                     }
00110                 }// if
00111             }
00112         }// while
00113 
00114         //
00115         // Get list of adjacent nodes to this edge.
00116         //
00117         adjacentNodes = (*itsGraph->getAdjacentList(clique[0]));
00118         for (i=adjacentNodes.size()-1; i>=0; i--) {
00119             if (clique.back() == adjacentNodes[i]) {
00120                 adjacentNodes.erase(adjacentNodes.begin()+i);
00121                 continue;
00122             }
00123             begin = 0;
00124             if (!itsGraph->isMemberOfAdjacentList(clique.back(), begin,
00125                                                   adjacentNodes[i])) {
00126                     adjacentNodes.erase(adjacentNodes.begin()+i);
00127             }
00128         }// for
00129 
00130 
00131         //
00132         // Construct a maximAL clique containing this egde.
00133         //
00134         while(!adjacentNodes.empty()) {
00135             index = getRandomNumber(adjacentNodes.size());
00136             clique.push_back(adjacentNodes[index]);
00137             adjacentNodes.erase(adjacentNodes.begin() + index);
00138             // Update adjacent nodes.
00139             for (i=adjacentNodes.size()-1; i>=0; i--) {
00140                 begin = 0;
00141                 if (!itsGraph->isMemberOfAdjacentList(clique.back(), begin,
00142                                                       adjacentNodes[i])) {
00143                     adjacentNodes.erase(adjacentNodes.begin()+i);
00144                 }
00145             }
00146         }// while
00147 
00148 
00149         //
00150         // Check if this inequality is violated.
00151         //
00152         theCnt++;
00153         value = 0;
00154         for (i=0; i<clique.size(); i++) {
00155             value += solution[clique[i]];
00156         }
00157         if (value > 1 + MIN_VIOLATION) {
00158             // Store this inequality if it is a new one.
00159             sort(clique.begin(), clique.end());
00160 
00161             newOne = true;
00162             for (i=0; i<computedCliques.size(); i++) {
00163                 if (computedCliques[i].size() != clique.size()) {
00164                     continue;
00165                 }
00166                 j=0;
00167                 while (j<computedCliques[i].size()) {
00168                     if (clique[j] != computedCliques[i][j]) {
00169                         break;
00170                     }
00171                     j++;
00172                 }
00173                 if (j == computedCliques[i].size()) {
00174                     newOne = false;
00175                     break;
00176                 }
00177             }
00178 
00179             if (newOne) {
00180                 computedCliques.push_back(clique);
00181 
00182                 cliqueConstr = new CliqueConstraint(master_, &clique, itsGraph);
00183                 cutFound(cliqueConstr);
00184 
00185                 theCnt = 0;
00186                 cutCnt++;
00187 
00188             }
00189 
00190         }// if
00191 
00192         // Clean up.
00193         clique.clear();
00194         adjacentNodes.clear();
00195         clique.resize(2);
00196         cnt++;
00197 
00198     }// while
00199 
00200 } // end: separate()
00201 
00202 
00203 // -----------------------------------------------------------------------------
00204 // g e t R a n d o m N u m b e r
00205 // -----------------------------------------------------------------------------
00206 int CliqueHeuristicsSeparator::getRandomNumber(int bound) const {
00207     int    aNumber = rand();
00208     double d       = (double(aNumber)/RAND_MAX);
00209 
00210     return (int)(d*bound);
00211 }
00212 
00213 
00214 

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