C:/Programme/home/Administrator/CD/stableSetCode/LowerBoundHeuristic.cpp

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : LowerBoundHeuristic.cpp
00004 //  Description      : Rounding heuristic for the maximum stable set problem.
00005 //  Author           : Steffen Rebennack
00006 //  Email            : srebenac@ix.urz.uni-heidelberg.de;
00007 //                     steffen.rebennack@web.de
00008 //  Copyright        : (C) 2006 by the University of Heidelberg
00009 //  Created on       : Wed Apr 05 14:44:10 2006
00010 //  Last modified by : -
00011 //  Last modified on : -
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
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 // The struct NodesAndWeights stores an index of a node and a weight.
00031 //
00032 struct NodesAndWeights {
00033     int    inode;         // index of node
00034     double wweight;       // weighted weight of node
00035 };// struct NodesAndWeights
00036 
00037 
00038 //
00039 // This operator is used by the sort function in lowerBoundHeuristic to get
00040 // a sorted vector of variables with increasing weight.
00041 //
00042 bool operator<(const NodesAndWeights &a, const NodesAndWeights &b) {
00043         return a.wweight > b.wweight;
00044 }
00045 
00046 
00047 
00048 // -----------------------------------------------------------------------------
00049 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00050 // -----------------------------------------------------------------------------
00051 
00052 
00053 // -----------------------------------------------------------------------------
00054 // C o n s t r u c t o r
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 // D e s t r u c t o r
00067 // -----------------------------------------------------------------------------
00068 LowerBoundHeuristic::~LowerBoundHeuristic() {
00069 }
00070 
00071 
00072 // -----------------------------------------------------------------------------
00073 // c o m p u t e S o l u t i o n
00074 //
00075 // The function findSolution() is a heuristic to compute a Stable Set
00076 // from a given solution vector of a fractional LP solution. It uses the
00077 // structure NodesAndWeights with its special order.
00078 //
00079 // The heuristic works in the following way:
00080 // - First fix all variables which have binary values.
00081 // - Sort all variables which are not binary by the solution value multiplied
00082 //   with its weight (if there are no weights than the weight is set to 1).
00083 // - Fix the variable with the highest value to 1 and fix all its adjazent
00084 //   nodes to 0. Do this last step untill all variables are binary.
00085 //
00086 // The heuristic stores the solution in the arry integerSolution and value is
00087 // the corresponding weight of the STable Set
00088 // -----------------------------------------------------------------------------
00089 int LowerBoundHeuristic::computeSolution(double &value, double *xVal_, int level) {
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(..)
00231 
00232 
00233 
00234 // -----------------------------------------------------------------------------
00235 // -------------- M e t h o d s  ( p r i v a t e ) -----------------------------
00236 // -----------------------------------------------------------------------------
00237 
00238 
00239 // -----------------------------------------------------------------------------
00240 // t e s t S t a b l e S e t
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             }// if
00260         }
00261     }// for
00262 }
00263 
00264 

Generated on Fri Apr 28 15:49:59 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO