CliqueHeuristicsSeparator Class Reference

#include <CliqueHeuristicsSeparator.hh>

List of all members.

Public Member Functions

 CliqueHeuristicsSeparator (StableSetLPSolution *solution, Graph *theGraph)
 ~CliqueHeuristicsSeparator ()
virtual void separate ()


Detailed Description

This class provides an heuristic separation procedure for maximAL clique constraints.

Definition at line 34 of file CliqueHeuristicsSeparator.hh.


Constructor & Destructor Documentation

CliqueHeuristicsSeparator::CliqueHeuristicsSeparator StableSetLPSolution solution,
Graph theGraph
 

Constructor.

Parameters:
*solution Pointer to the current LP-solution to be separated.
*theGraph Pointer to the graph of the problem instance.

Definition at line 33 of file CliqueHeuristicsSeparator.cpp.

00035                                                        :
00036     ABA_SEPARATOR<ABA_CONSTRAINT, ABA_VARIABLE> (solution, true, 300),
00037     itsGraph(theGraph),
00038     lpSolution(solution)
00039 {
00040 }

CliqueHeuristicsSeparator::~CliqueHeuristicsSeparator  ) 
 

Destructor.

Definition at line 46 of file CliqueHeuristicsSeparator.cpp.

00047 {
00048 }


Member Function Documentation

void CliqueHeuristicsSeparator::separate  )  [virtual]
 

This method provides the separation procedure itself and overrides the pure virtual function of ABA_SEPARATOR.

Parameters:
void 
Returns:
void

Definition at line 58 of file CliqueHeuristicsSeparator.cpp.

References Graph::getAdjacentList(), Graph::isMemberOfAdjacentList(), Graph::numberOfNodes(), and StableSetLPSolution::sub().

Referenced by StableSetSub::separate().

00058                                          {
00059 
00060     int i, j;           // Loop counter.
00061     int index;          // Index to a node.
00062     double value;       // The value of the clique in the current LP-solution.
00063     vector< vector<int> > computedCliques; // Store all computed cliques.
00064     vector<int> clique(2);      // This stores the maximAL clique.
00065     vector<int> adjacentNodes;  // Set of nodes adjacent to the current clique.
00066     int size = itsGraph->numberOfNodes(); // Size of the graph.
00067     int cnt = 0;        // Counter.
00068     bool found;         //
00069     bool newOne;        // Indicate if a clique is new or have been computed
00070                         // earlier.
00071     int theCnt = 0;     // Counter.
00072     int cutCnt = 0;     // Counter for the generated cuts.
00073     int begin = 0;      // Index to check in adjacent list.
00074     double *solution = lpSolution->zVal();  // Current LP-solution.
00075     CliqueConstraint *cliqueConstr;         // Pointer to a clique sontraint
00076                                             // To store each computed clique in
00077                                             // Buffer cutfound().
00078     int level = lpSolution->sub()->level();
00079 
00080 
00081     //
00082     // Parameter.
00083     //
00084     static const int    MAX_ITER_SEP  = level==1 ? size * 1.5 : size / 3;
00085     static const int    MAX_STEP      = level==1 ? size / 4 : (int)( 5 + 0.01 * size );
00086     static const int    MAX_CUTS      = level==1 ? size : size / 5;
00087     static const double MIN_VIOLATION = 0.0001;
00088 
00089 
00090     //
00091     // Construct maximAL cliques.
00092     //
00093     while ( ((cnt < MAX_ITER_SEP) || theCnt < MAX_STEP)
00094             && (cutCnt < MAX_CUTS) ) {
00095 
00096         //
00097         // Select edge to start from.
00098         //
00099         found = false;
00100         while (!found) {
00101             clique[0] = getRandomNumber(size);
00102             clique[1] = getRandomNumber(size);
00103             if (clique[0] != clique[1]) {
00104                 if (clique[0] > clique[1]) {
00105                     begin = 0;
00106                     if (itsGraph->isMemberOfAdjacentList(clique[0], begin,
00107                                                          clique[1])) {
00108                         found = true;
00109                     }
00110                 }// if
00111             }
00112         }// while
00113 
00114         //
00115         // Get list of adjacent nodes to this edge.
00116         //
00117         adjacentNodes = (*itsGraph->getAdjacentList(clique[0]));
00118         for (i=adjacentNodes.size()-1; i>=0; i--) {
00119             if (clique.back() == adjacentNodes[i]) {
00120                 adjacentNodes.erase(adjacentNodes.begin()+i);
00121                 continue;
00122             }
00123             begin = 0;
00124             if (!itsGraph->isMemberOfAdjacentList(clique.back(), begin,
00125                                                   adjacentNodes[i])) {
00126                     adjacentNodes.erase(adjacentNodes.begin()+i);
00127             }
00128         }// for
00129 
00130 
00131         //
00132         // Construct a maximAL clique containing this egde.
00133         //
00134         while(!adjacentNodes.empty()) {
00135             index = getRandomNumber(adjacentNodes.size());
00136             clique.push_back(adjacentNodes[index]);
00137             adjacentNodes.erase(adjacentNodes.begin() + index);
00138             // Update adjacent nodes.
00139             for (i=adjacentNodes.size()-1; i>=0; i--) {
00140                 begin = 0;
00141                 if (!itsGraph->isMemberOfAdjacentList(clique.back(), begin,
00142                                                       adjacentNodes[i])) {
00143                     adjacentNodes.erase(adjacentNodes.begin()+i);
00144                 }
00145             }
00146         }// while
00147 
00148 
00149         //
00150         // Check if this inequality is violated.
00151         //
00152         theCnt++;
00153         value = 0;
00154         for (i=0; i<clique.size(); i++) {
00155             value += solution[clique[i]];
00156         }
00157         if (value > 1 + MIN_VIOLATION) {
00158             // Store this inequality if it is a new one.
00159             sort(clique.begin(), clique.end());
00160 
00161             newOne = true;
00162             for (i=0; i<computedCliques.size(); i++) {
00163                 if (computedCliques[i].size() != clique.size()) {
00164                     continue;
00165                 }
00166                 j=0;
00167                 while (j<computedCliques[i].size()) {
00168                     if (clique[j] != computedCliques[i][j]) {
00169                         break;
00170                     }
00171                     j++;
00172                 }
00173                 if (j == computedCliques[i].size()) {
00174                     newOne = false;
00175                     break;
00176                 }
00177             }
00178 
00179             if (newOne) {
00180                 computedCliques.push_back(clique);
00181 
00182                 cliqueConstr = new CliqueConstraint(master_, &clique, itsGraph);
00183                 cutFound(cliqueConstr);
00184 
00185                 theCnt = 0;
00186                 cutCnt++;
00187 
00188             }
00189 
00190         }// if
00191 
00192         // Clean up.
00193         clique.clear();
00194         adjacentNodes.clear();
00195         clique.resize(2);
00196         cnt++;
00197 
00198     }// while
00199 
00200 } // end: separate()


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