ImprovementHeuristic Class Reference

#include <ImprovementHeuristic.hh>

List of all members.

Public Member Functions

 ImprovementHeuristic (ABA_MASTER *master, Graph *theGraph, StableSetStatistics *theStatistics)
 ~ImprovementHeuristic ()
int improve (double &value)


Detailed Description

This class provides a heuristic to improve a stable set from a current stable set.

Definition at line 38 of file ImprovementHeuristic.hh.


Constructor & Destructor Documentation

ImprovementHeuristic::ImprovementHeuristic 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 37 of file ImprovementHeuristic.cpp.

00038                                                                               :
00039     master_(master),
00040     itsGraph(theGraph),
00041     itsStatistics(theStatistics)
00042 {
00043 }

ImprovementHeuristic::~ImprovementHeuristic  ) 
 

Destructor.

Definition at line 49 of file ImprovementHeuristic.cpp.

00049                                             {
00050 }


Member Function Documentation

int ImprovementHeuristic::improve double &  value  ) 
 

Try to improve a stable set.

Parameters:
&value Reference to the size of the best stable set found so far.
Returns:
1 The stable set could be improved.

0 There was no improvement.

Definition at line 61 of file ImprovementHeuristic.cpp.

References StableSetMaster::getSolution(), and StableSetMaster::m_timeLimitForImprovementHeuristic.

00061                                                {
00062 
00063     clock_t t1 = clock();       // Get current time.
00064 
00065     int i, j, k;        // Loop counter.
00066     int cnt;            // Counter.
00067     int cnt2;
00068     int vertex;         // A node.
00069     int indexOfVertex;  // Index of node vertex.
00070     int indexOfNode;
00071     int node;
00072     int index;
00073     int nodeOfPathOne;
00074     int nodeOfPathTwo;
00075     int v11, v12, v13;  // Three nodes of a path.
00076     int v21, v22, v23;  // Three nodes of a path.
00077     int beginOne;
00078     int beginTwo;
00079     int stack;
00080     int member;
00081     int status = 0;     // Return value;
00082     double timeLimit = stableSetMaster()->m_timeLimitForImprovementHeuristic;
00083     vector<int> *solution = stableSetMaster()->getSolution();
00084     if (solution->size() <= 2) {
00085         return status;
00086     }
00087 
00088     //
00089     // Improve until time limit is reached.
00090     //
00091     while (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC) {
00092 
00093         // Choose randomly two nodes to start from.
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             // Find path from 'vertex' to '(*solution)[node]' with length 3.
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         // Two paths have been computed. Try to improve the stable set.
00135         //
00136         if (cnt == 2) {
00137 
00138             cnt2 = 0;
00139             // Solution is allways sorted!
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             // If cnt = 0 the new stable set will have a greater size.
00164             //
00165             if (cnt2 < 2) {
00166                 // Update solution.
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     // Update bounds.
00191     if (master_->betterPrimal(value)) {
00192         // Heuristic found better solution.
00193         master_->out() << "\nImprovement of heuristic was successful:\n";
00194         master_->out() << "\tNew value:\t" << value << endl;
00195         
00196         // Update lower bound (best known feasible solution)
00197         // (this is done automatically by ABACUS, too).
00198         master_->primalBound(value);
00199    
00200         // Update statistics.
00201         itsStatistics->solutionFound(2);
00202 
00203         status = 1;
00204     }
00205 
00206     // Return with status.
00207     return status;
00208 
00209 }// int improve(..)


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