00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00015
00016
00017
00018
00020
00021
00022 #include "LowerBoundHeuristic.hh"
00023 #include "Graph.hh"
00024 #include "StableSetMaster.hh"
00025 #include "StableSetStatistics.hh"
00026
00027
00028
00029
00030
00031
00032 struct NodesAndWeights {
00033 int inode;
00034 double wweight;
00035 };
00036
00037
00038
00039
00040
00041
00042 bool operator<(const NodesAndWeights &a, const NodesAndWeights &b) {
00043 return a.wweight > b.wweight;
00044 }
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056 LowerBoundHeuristic::LowerBoundHeuristic(ABA_MASTER *master, Graph *theGraph,
00057 StableSetStatistics *theStatistics):
00058 master_(master),
00059 itsGraph(theGraph),
00060 itsStatistics(theStatistics)
00061 {
00062 }
00063
00064
00065
00066
00067
00068 LowerBoundHeuristic::~LowerBoundHeuristic() {
00069 }
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089 int LowerBoundHeuristic::computeSolution(double &value, double *xVal_, int level) {
00090
00091 int i, j, a;
00092 int size;
00093 int numberOfNodes = itsGraph->numberOfNodes();
00094 int stack;
00095 int node;
00096 int index;
00097 int max;
00098 double eps = 0.000001;
00099 vector<NodesAndWeights> fractionalValue;
00100 double weight = 0;
00101 int integerSolution[numberOfNodes];
00102 int status = 0;
00103
00104
00105
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
00116 for (i=0; i<numberOfNodes; i++) {
00117 integerSolution[i] = -1;
00118 }
00119
00120
00121
00122
00123 for (i=0; i<numberOfNodes; i++ ) {
00124 if ((xVal_[i] < eps) && (xVal_[i] > -eps)) {
00125
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
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
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
00156
00157 sort(fractionalValue.begin(), fractionalValue.end());
00158
00159
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 }
00197
00198
00199 if (master_->primalBound() <= weight) {
00200 vector<int> *solution = ((StableSetMaster*)master_)->getSolution();
00201 solution->clear();
00202
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
00215
00216 value = weight;
00217 master_->primalBound(value);
00218
00219
00220 itsStatistics->roundingHeuristics();
00221 itsStatistics->solutionFound(1);
00222
00223 status = 1;
00224 }
00225 }
00226 }
00227
00228 return status;
00229
00230 }
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242 void LowerBoundHeuristic::testStableSet(vector<int> *stableSet) {
00243
00244 int i, j, l;
00245
00246 for (i=1; i<stableSet->size(); i++) {
00247 for (j=(i-1); j>=0; j--) {
00248 l = 0;
00249 if (itsGraph->isMemberOfAdjacentList((*stableSet)[i], l,
00250 (*stableSet)[j])) {
00251 master_->err() << "LowerBoundHeuristic::testStableSet:\t";
00252 master_->err() << "The constructed svector is no stable set!\n";
00253 master_->err() << "Solution:\t";
00254 for (l=0; l<stableSet->size(); l++) {
00255 master_->err() << (*stableSet)[l] << " ";
00256 }
00257 master_->err() << endl;
00258 exit(master_->Fatal);
00259 }
00260 }
00261 }
00262 }
00263
00264