#include <LowerBoundHeuristic.hh>
Public Member Functions | |
LowerBoundHeuristic (ABA_MASTER *master, Graph *theGraph, StableSetStatistics *theStatistics) | |
~LowerBoundHeuristic () | |
int | computeSolution (double &value, double *xVal_, int level) |
Definition at line 38 of file LowerBoundHeuristic.hh.
|
Constructor.
Definition at line 56 of file LowerBoundHeuristic.cpp. 00057 : 00058 master_(master), 00059 itsGraph(theGraph), 00060 itsStatistics(theStatistics) 00061 { 00062 }
|
|
Destructor. Definition at line 68 of file LowerBoundHeuristic.cpp.
|
|
Heuristic to compute a Stable Set.
Definition at line 89 of file LowerBoundHeuristic.cpp. References Graph::numberOfNodes(). Referenced by StableSetSub::improve(). 00089 { 00090 00091 int i, j, a; // Loop counter. 00092 int size; // Loop variable. 00093 int numberOfNodes = itsGraph->numberOfNodes(); // Problem size. 00094 int stack; // Storage. 00095 int node; // A node. 00096 int index; 00097 int max; 00098 double eps = 0.000001; // Machine precision. 00099 vector<NodesAndWeights> fractionalValue; // Save all fractional variables. 00100 double weight = 0; 00101 int integerSolution[numberOfNodes]; 00102 int status = 0; 00103 00104 // 00105 // Parameter 00106 // 00107 const int ITERATION_NUMBER = level==1 ? 15 : 2; 00108 const int RANDOM_NUMBER = 100; 00109 const double ADD = 0.001; 00110 00111 for (a=0; a<ITERATION_NUMBER; a++) { 00112 00113 weight = 0; 00114 00115 // Initialize the solution array. 00116 for (i=0; i<numberOfNodes; i++) { 00117 integerSolution[i] = -1; 00118 } 00119 00120 // Fix all binary variables and if the value is 1 fix all adjazent nodes 00121 // to value 0. If a variable is not binary store it together with its 00122 // weight in the vector fractionalValue. 00123 for (i=0; i<numberOfNodes; i++ ) { 00124 if ((xVal_[i] < eps) && (xVal_[i] > -eps)) { 00125 // the value is zero 00126 integerSolution[i] = 0; 00127 } 00128 else { 00129 if ((xVal_[i] > 1 - eps) && (xVal_[i] < 1 + eps)) { 00130 if (integerSolution[i] == 0) { 00131 continue; 00132 } 00133 // Its value is one: fix all adjazent nodes. 00134 integerSolution[i] = 1; 00135 weight += itsGraph->weighted() ? itsGraph->weight(i) : 1; 00136 for (j=0; j<itsGraph->adjacentListSize(i); j++ ) { 00137 stack = itsGraph->adjacentListElement(i, j); 00138 integerSolution[stack] = 0; 00139 } 00140 } 00141 else { 00142 // A fractional variable. 00143 NodesAndWeights a; 00144 a.inode = i; 00145 a.wweight = itsGraph->weighted() 00146 ? itsGraph->weight(i)* xVal_[i] 00147 : xVal_[i]; 00148 a.wweight += ADD * // 00149 ((StableSetMaster *)master_)->getRandomNumber(RANDOM_NUMBER); 00150 fractionalValue.push_back(a); 00151 } 00152 } 00153 } 00154 00155 // Sort the fractional variables: 00156 // the value with the highest weight is the last in this vector. 00157 sort(fractionalValue.begin(), fractionalValue.end()); 00158 00159 // Fix all variables untill this vector is empty. 00160 while (!fractionalValue.empty()) { 00161 size = fractionalValue.size(); 00162 max = 512; 00163 stack = ((StableSetMaster *)master_)->getRandomNumber(1024); 00164 00165 index = size -1; 00166 while (stack < max) { 00167 max = max / 2; 00168 if (index == 0) { 00169 break; 00170 } 00171 index--; 00172 } 00173 stack = fractionalValue[index].inode; 00174 00175 if (integerSolution[stack] == -1) { 00176 integerSolution[stack] = 1; 00177 weight += itsGraph->weighted() ? itsGraph->weight(i) : 1; 00178 00179 size = itsGraph->adjacentListSize(stack); 00180 for (i=0; i<size; i++) { 00181 node = itsGraph->adjacentListElement(stack, i); 00182 00183 if(integerSolution[node] == 1) { 00184 master_->err() << "StableSetSUB::lowerBoundHeuristic: "; 00185 master_->err() << "Setting of variable " << node; 00186 master_->err() << " to value 0 failed." << endl; 00187 exit(master_->Fatal); 00188 } 00189 integerSolution[node] = 0; 00190 } 00191 fractionalValue.erase(fractionalValue.begin() + index); 00192 } 00193 else { 00194 fractionalValue.erase(fractionalValue.begin() + index); 00195 } 00196 }// while 00197 00198 // Update. 00199 if (master_->primalBound() <= weight) { 00200 vector<int> *solution = ((StableSetMaster*)master_)->getSolution(); 00201 solution->clear(); 00202 // Update solution. 00203 for (i=0; i<numberOfNodes; i++) { 00204 if (integerSolution[i] == 1) { 00205 solution->push_back(i); 00206 } 00207 } 00208 testStableSet(solution); 00209 if (master_->primalBound() < weight) { 00210 master_->out() << "\nHeuristic found better feasible "; 00211 master_->out() << "solution with value " << weight; 00212 master_->out() << "." << endl; 00213 00214 // Update lower bound (best known feasible solution) 00215 // (this is done automatically by ABACUS, too). 00216 value = weight; 00217 master_->primalBound(value); 00218 00219 // Update statistics. 00220 itsStatistics->roundingHeuristics(); 00221 itsStatistics->solutionFound(1); 00222 00223 status = 1; 00224 } 00225 }// if 00226 }// for 00227 00228 return status; 00229 00230 }// end: void lowerBoundHeuristic(..)
|