#include <CliqueHeuristicsSeparator.hh>
Public Member Functions | |
CliqueHeuristicsSeparator (StableSetLPSolution *solution, Graph *theGraph) | |
~CliqueHeuristicsSeparator () | |
virtual void | separate () |
Definition at line 34 of file CliqueHeuristicsSeparator.hh.
|
Constructor.
Definition at line 33 of file CliqueHeuristicsSeparator.cpp. 00035 : 00036 ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 300), 00037 itsGraph(theGraph), 00038 lpSolution(solution) 00039 { 00040 }
|
|
Destructor. Definition at line 46 of file CliqueHeuristicsSeparator.cpp.
|
|
This method provides the separation procedure itself and overrides the pure virtual function of ABA_SEPARATOR.
Definition at line 58 of file CliqueHeuristicsSeparator.cpp. References Graph::getAdjacentList(), Graph::isMemberOfAdjacentList(), Graph::numberOfNodes(), and StableSetLPSolution::sub(). Referenced by StableSetSub::separate(). 00058 { 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()
|