00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00015
00016
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
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
00045
00046 CliqueHeuristicsSeparator::~CliqueHeuristicsSeparator ()
00047 {
00048 }
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058 void CliqueHeuristicsSeparator::separate() {
00059
00060 int i, j;
00061 int index;
00062 double value;
00063 vector< vector<int> > computedCliques;
00064 vector<int> clique(2);
00065 vector<int> adjacentNodes;
00066 int size = itsGraph->numberOfNodes();
00067 int cnt = 0;
00068 bool found;
00069 bool newOne;
00070
00071 int theCnt = 0;
00072 int cutCnt = 0;
00073 int begin = 0;
00074 double *solution = lpSolution->zVal();
00075 CliqueConstraint *cliqueConstr;
00076
00077
00078 int level = lpSolution->sub()->level();
00079
00080
00081
00082
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
00092
00093 while ( ((cnt < MAX_ITER_SEP) || theCnt < MAX_STEP)
00094 && (cutCnt < MAX_CUTS) ) {
00095
00096
00097
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 }
00111 }
00112 }
00113
00114
00115
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 }
00129
00130
00131
00132
00133
00134 while(!adjacentNodes.empty()) {
00135 index = getRandomNumber(adjacentNodes.size());
00136 clique.push_back(adjacentNodes[index]);
00137 adjacentNodes.erase(adjacentNodes.begin() + index);
00138
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 }
00147
00148
00149
00150
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
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 }
00191
00192
00193 clique.clear();
00194 adjacentNodes.clear();
00195 clique.resize(2);
00196 cnt++;
00197
00198 }
00199
00200 }
00201
00202
00203
00204
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