LowerBoundHeuristic Class Reference

#include <LowerBoundHeuristic.hh>

List of all members.

Public Member Functions

 LowerBoundHeuristic (ABA_MASTER *master, Graph *theGraph, StableSetStatistics *theStatistics)
 ~LowerBoundHeuristic ()
int computeSolution (double &value, double *xVal_, int level)


Detailed Description

This class provides a heuristic to compute a stable set from a fractional LP solution.

Definition at line 38 of file LowerBoundHeuristic.hh.


Constructor & Destructor Documentation

LowerBoundHeuristic::LowerBoundHeuristic ABA_MASTER *  master,
Graph theGraph,
StableSetStatistics theStatistics
 

Constructor.

Parameters:
*master Pointer to the master of the problem.
*theGraph Pointer to the graph storing all information about the problem instance.
*theStatistics Pointer to an object managing the statistics.

Definition at line 56 of file LowerBoundHeuristic.cpp.

00057                                                                             :
00058     master_(master),
00059     itsGraph(theGraph),
00060     itsStatistics(theStatistics)
00061 {
00062 }

LowerBoundHeuristic::~LowerBoundHeuristic  ) 
 

Destructor.

Definition at line 68 of file LowerBoundHeuristic.cpp.

00068                                           {
00069 }


Member Function Documentation

int LowerBoundHeuristic::computeSolution double &  value,
double *  xVal_,
int  level
 

Heuristic to compute a Stable Set.

Parameters:
&value Reference to the weight of the best stable set found so far.
*xVal_ Pointer to the current LP solution value.
level Level of the subprobelm in the tree. return 1 A stable set with higher weight was computed. return 0 There was no better stable set found.

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(..)


The documentation for this class was generated from the following files:
Generated on Fri Apr 28 15:50:00 2006 for Branch and Cut algorithm for the Maximum Stable Set Problem by  doxygen 1.4.6-NO