00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00015
00016
00017
00018
00020
00021
00022 #include "ImprovementHeuristic.hh"
00023 #include "Graph.hh"
00024 #include "StableSetMaster.hh"
00025 #include "StableSetStatistics.hh"
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037 ImprovementHeuristic::ImprovementHeuristic(ABA_MASTER *master, Graph *theGraph,
00038 StableSetStatistics *theStatistics):
00039 master_(master),
00040 itsGraph(theGraph),
00041 itsStatistics(theStatistics)
00042 {
00043 }
00044
00045
00046
00047
00048
00049 ImprovementHeuristic::~ImprovementHeuristic() {
00050 }
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061 int ImprovementHeuristic::improve(double &value) {
00062
00063 clock_t t1 = clock();
00064
00065 int i, j, k;
00066 int cnt;
00067 int cnt2;
00068 int vertex;
00069 int indexOfVertex;
00070 int indexOfNode;
00071 int node;
00072 int index;
00073 int nodeOfPathOne;
00074 int nodeOfPathTwo;
00075 int v11, v12, v13;
00076 int v21, v22, v23;
00077 int beginOne;
00078 int beginTwo;
00079 int stack;
00080 int member;
00081 int status = 0;
00082 double timeLimit = stableSetMaster()->m_timeLimitForImprovementHeuristic;
00083 vector<int> *solution = stableSetMaster()->getSolution();
00084 if (solution->size() <= 2) {
00085 return status;
00086 }
00087
00088
00089
00090
00091 while (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC) {
00092
00093
00094 indexOfVertex = stableSetMaster()->getRandomNumber(solution->size());
00095 vertex = (*solution)[indexOfVertex];
00096 index = stableSetMaster()->getRandomNumber(solution->size());
00097 if (index == indexOfVertex) {
00098 index++;
00099 index = index % solution->size();
00100 }
00101 node = index +1;
00102 node = node % solution->size();
00103 if (node == indexOfVertex) {
00104 node++;
00105 node = node % solution->size();
00106 }
00107 cnt = 0;
00108 v11 = -1;
00109 v12 = -1;
00110 while((cnt < 2) && (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC)) {
00111 if (node == index) {
00112 break;
00113 }
00114
00115 if (calculateDistance(vertex, (*solution)[node], v11, v12, v21,
00116 v22)) {
00117 cnt++;
00118 if (cnt == 1) {
00119 v13 = (*solution)[node];
00120 }
00121 else {
00122 v23 = (*solution)[node];
00123 }
00124 }
00125 node++;
00126 node = node % solution->size();
00127 if (node == indexOfVertex) {
00128 node++;
00129 node = node % solution->size();
00130 }
00131 }
00132
00133
00134
00135
00136 if (cnt == 2) {
00137
00138 cnt2 = 0;
00139
00140 beginOne = 0;
00141 beginTwo = 0;
00142 for (j=0; j<solution->size(); j++) {
00143 stack = (*solution)[j];
00144 if (stack != vertex) {
00145 if(itsGraph->isMemberOfAdjacentList(v11, beginOne, stack)) {
00146 cnt2++;
00147 member = stack;
00148 }
00149 else {
00150 if(itsGraph->isMemberOfAdjacentList(v21, beginTwo,
00151 stack)) {
00152 cnt2++;
00153 member = stack;
00154 }
00155 }
00156 }
00157 if (cnt2 > 1) {
00158 break;
00159 }
00160 }
00161
00162
00163
00164
00165 if (cnt2 < 2) {
00166
00167 solution->erase(solution->begin() + indexOfVertex);
00168 if (cnt2 == 1) {
00169 k = 0;
00170 while ((*solution)[k] != member) {
00171 k++;
00172 }
00173 solution->erase(solution->begin() + k);
00174 }
00175
00176 solution->push_back(v11);
00177 solution->push_back(v21);
00178 sort(solution->begin(), solution->end());
00179 testStableSet(solution);
00180 if (cnt2 == 0) {
00181 itsStatistics->improvementHeuristics();
00182 }
00183 }
00184 }
00185
00186 }
00187
00188 value = 1.0*solution->size();
00189
00190
00191 if (master_->betterPrimal(value)) {
00192
00193 master_->out() << "\nImprovement of heuristic was successful:\n";
00194 master_->out() << "\tNew value:\t" << value << endl;
00195
00196
00197
00198 master_->primalBound(value);
00199
00200
00201 itsStatistics->solutionFound(2);
00202
00203 status = 1;
00204 }
00205
00206
00207 return status;
00208
00209 }
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224 bool ImprovementHeuristic::calculateDistance(int start, int end, int &n11,
00225 int &n12, int &n21, int &n22)
00226 const {
00227
00228 int i, j, k, l;
00229 int startSize = itsGraph->adjacentListSize(start);
00230 int endSize = itsGraph->adjacentListSize(end);
00231 int indexOne = ((StableSetMaster *)master_)->getRandomNumber(startSize);
00232 int indexTwo;
00233 int vertex;
00234 int node;
00235 int index;
00236 vector<int> *solution = ((StableSetMaster*)master_)->getSolution();
00237
00238
00239
00240
00241 for (i=0; i<startSize; i++) {
00242 vertex = itsGraph->adjacentListElement(start, indexOne);
00243 indexTwo = ((StableSetMaster *)master_)->getRandomNumber(endSize);
00244 index = 0;
00245
00246
00247
00248 for (j=0; j<endSize; j++) {
00249 node = itsGraph->adjacentListElement(end, indexTwo);
00250 l = 0;
00251 if(itsGraph->isMemberOfAdjacentList(vertex, index, node)
00252 && (node != n11) && (node != n12)
00253 && (vertex != n11) && (vertex != n12)
00254 && ((n11 == -1) || !itsGraph->isMemberOfAdjacentList(n11, l,
00255 vertex))
00256 ) {
00257
00258 k = 0;
00259 while ((k < (solution->size()-1))
00260 && ((*solution)[k] < vertex)
00261 ) {
00262 k++;
00263 }
00264 if ((*solution)[k] == vertex) {
00265 continue;
00266 }
00267 k = 0;
00268 while ((k < (solution->size()-1))
00269 && ((*solution)[k] < node)
00270 ) {
00271 k++;
00272 }
00273 if ((*solution)[k] == node) {
00274 continue;
00275 }
00276 if (n11 == -1) {
00277 n11 = vertex;
00278 n12 = node;
00279 }
00280 else {
00281 n21 = vertex;
00282 n22 = node;
00283 }
00284
00285 return true;
00286 }
00287 indexTwo++;
00288 indexTwo = indexTwo % endSize;
00289 if (indexTwo == 0) {
00290 index = 0;
00291 }
00292 }
00293 indexOne++;
00294 indexOne = indexOne % startSize;
00295 }
00296
00297 return false;
00298 }
00299
00300
00301
00302
00303
00304 void ImprovementHeuristic::testStableSet(vector<int> *stableSet) {
00305
00306 int i, j, l;
00307
00308 for (i=1; i<stableSet->size(); i++) {
00309 for (j=(i-1); j>=0; j--) {
00310 l = 0;
00311 if (itsGraph->isMemberOfAdjacentList((*stableSet)[i], l,
00312 (*stableSet)[j])) {
00313 master_->err() << "ImprovementHeuristic::testStableSet:\t";
00314 master_->err() << "The constructed vector is no stable set!\n";
00315 master_->err() << "Solution:\t";
00316 for (l=0; l<stableSet->size(); l++) {
00317 master_->err() << (*stableSet)[l] << " ";
00318 }
00319 master_->err() << endl;
00320 exit(master_->Fatal);
00321 }
00322 }
00323 }
00324 }
00325
00326
00327
00328
00329
00330
00331
00332
00333 StableSetMaster *ImprovementHeuristic::stableSetMaster() {
00334 return ((StableSetMaster *)master_);
00335 }
00336
00337
00338
00339
00340
00341
00342
00343