EdgeProjection Class Reference

#include <EdgeProjection.hh>

List of all members.

Public Member Functions

 EdgeProjection (vector< vector< int > > *adjacentList)
 ~EdgeProjection ()
int separate (double *lpValue)
int computeLargeInequality (double *lpValue, StableSetMaster *theMaster)
vector< vector< int > * > * getLHS ()
vector< int > * getRHS ()


Detailed Description

This class provides the edge projection for the stable set problem. After an edge has been selected, its neighborhood is updated to get a strongly projectable edge. The next step is the projection of the graph and the separation of rank inequalities. This is done via maximal cliques. The anti-projection steps make the inequalities valid for the whole graph.

Definition at line 44 of file EdgeProjection.hh.


Constructor & Destructor Documentation

EdgeProjection::EdgeProjection vector< vector< int > > *  adjacentList  ) 
 

Constructor.

Parameters:
*adjacentList Information of the graph.

Definition at line 43 of file EdgeProjection.cpp.

00043                                                           :
00044 currentNode(NULL)
00045 {
00046 
00047     int i, j;   // Loop variables.
00048     int node;   // Store a node.
00049 
00050     // Number of nodes of the graph.
00051     graphSize = graph->size();
00052 
00053     // Allocate memory for the adjacent list size counter.
00054     adjacentListSize = new int[graphSize];
00055 
00056     // Allocate memory for the adjacent matrix.
00057     lowerAdjacentMatrix.resize(graphSize - 1);
00058     for (i=1; i<graphSize; i++) {
00059         lowerAdjacentMatrix[i-1].resize(i,0);
00060     }
00061 
00062     // Copy graph and store each size of the adjacent list.
00063     for (i=0; i<graphSize; i++) {
00064         // Update the size of each adjacent list.
00065         adjacentListSize[i] = (*graph)[i].size();
00066         for (j=0; j<adjacentListSize[i]; j++) {
00067             node = (*graph)[i][j];
00068             // Store this edge in the adjacent matrix.
00069             if (i > node) {
00070                 lowerAdjacentMatrix[i-1][node] = 1;
00071             }
00072         }// for
00073     }// for
00074 
00075 
00076     // Check each edge if it is strong projectable.
00077 //    checkStrongProjectability();
00078 //    cout << "Number of strongly projectable edges: ";
00079 //    cout << projectable.size() << endl;
00080 
00081     // Initialize random counter.
00082     srand(1);
00083     
00084     // Print information of the root of the tree.    
00085     //printRoot();
00086 
00087 }// end constructor

EdgeProjection::~EdgeProjection  ) 
 

Destructor.

Definition at line 93 of file EdgeProjection.cpp.

00093                                 {
00094 
00095     delete []adjacentListSize;
00096 
00097     if (!lhs.empty()) {
00098         // Delete the inequalities.
00099         for (int i=lhs.size()-1; i>=0; i--) {
00100             delete lhs[i];
00101             lhs[i] = NULL;
00102         }
00103         lhs.clear();
00104     }
00105     
00106 }// end destructor


Member Function Documentation

int EdgeProjection::computeLargeInequality double *  lpValue,
StableSetMaster theMaster
 

This function computes one large rank inequality.

Parameters:
*lpValue Pointer to a solution of the current LP.
*theMaster Pointer to the master of the problem.
Returns:
0 Program treminated without error.

1 There was an error during the separation.

Definition at line 253 of file EdgeProjection.cpp.

00254                                                                        {
00255 
00256     int i;  // Loop counter.
00257     int reducedGraphSize = graphSize;
00258     bool condition = true;      // Stop criteria for the projection.
00259     vector<int> theLhs;         // Store the rank inequality (lhs)
00260     int theRhs;                 // Store the rank inequality (rhs)
00261 
00262     //
00263     // Parameter.
00264     //
00265     const static int MAX_SIZE_OF_GRAPH = 45; //(int) graphSize / 5 ;  
00266   
00267     // 
00268     // Clear all stored inequalities.
00269     //
00270     for (i=lhs.size()-1; i>=0; i--) {
00271         delete lhs[i];
00272         lhs[i] = NULL;
00273     }
00274     lhs.clear();
00275     rhs.clear();
00276     slack.clear();
00277    
00278     //
00279     // Project until the graph is small enough to solve a stable set problem
00280     // exact. After one cut has been computed stop the projection.
00281     //    
00282     while (condition) {
00283 
00284         //
00285         // Select a new projectable edge
00286         //
00287         // Includes:
00288         // + check if the edge is projectable
00289         // + store all edges to be deleted that the edge is strongly projectable
00290         // + compute all nodes to be removed
00291         //
00292         bool edgeFound = edgeSelection(lpValue);
00293 
00294         if (!edgeFound) {
00295             break;
00296         }
00297 
00298         //
00299         // Projection: update reduction graph
00300         //  
00301         projection();
00302 
00303         //
00304         // Update size of reduced graph.
00305         //        
00306         reducedGraphSize = 0;
00307         for(i=0; i<graphSize; i++) {
00308             if (adjacentListSize[i] != 0) {
00309                 reducedGraphSize++;
00310             }
00311         }
00312 
00313         //
00314         // Deside whether to start solve stable set or to project again.
00315         //   
00316         if (reducedGraphSize <= MAX_SIZE_OF_GRAPH) {
00317         
00318             //
00319             // Solve the stable set problem for that small graph exactly.
00320             //            
00321             solveStableSet(&theLhs, theRhs, theMaster);
00322 
00323             //
00324             // Lift these inequalities.
00325             //
00326             liftAndStore(&theLhs, theRhs);
00327         
00328             //
00329             // One cut has been computed: stop projection
00330             //
00331             condition = false;
00332         }// if
00333 
00334         //
00335         // Clean up
00336         //
00337         edge[0] = edge[1] = -1;
00338         deleteNodes.clear();
00339         for (i=deleteEdges.size()-1; i>=0; i--) {
00340             delete [] deleteEdges[i];
00341         }
00342         deleteEdges.clear();
00343         theLhs.clear();
00344  
00345     }// while
00346     
00347     //
00348     // Clean up tree.
00349     //
00350     cleanUp();
00351 
00352     // Return status.
00353     return 0;
00354 
00355 }// computeLargeInequality(..)

vector< vector< int > * > * EdgeProjection::getLHS  ) 
 

This function returns the left hand side of all computed inequalities.

Parameters:
void 
Returns:
Pointer to the lhs of the inequalities.

Definition at line 363 of file EdgeProjection.cpp.

00363                                                {
00364 
00365     if (lhs.empty()) {
00366         return NULL;
00367     }
00368     else {
00369         return &lhs;
00370     }
00371 }

vector< int > * EdgeProjection::getRHS  ) 
 

This function returns the right hand side of all computed inequalities.

Parameters:
void 
Returns:
Pointer to the rhs of the inequalities.

Definition at line 379 of file EdgeProjection.cpp.

00379                                     {
00380     return &rhs;
00381 }

int EdgeProjection::separate double *  lpValue  ) 
 

This function handles the hole edge projection.

Parameters:
*lpValue Pointer to a solution of the current LP.
Returns:
0 Program treminated without error.

1 There was an error during the separation.

Definition at line 116 of file EdgeProjection.cpp.

00116                                             {
00117 
00118     int i;          // Loop variable.
00119     int numCut;     // The number of violated cuts found.
00120     int reducedGraphSize = graphSize;
00121     vector< vector<int> > theLhs;  // Store violated inequalities (lhs).
00122     vector<int> theRhs;            // Store violated inequalities (rhs).
00123     bool condition = true;  // Stop criteria for projection.
00124     bool separate  = true;  // Call separation or not.
00125     
00126     //
00127     // Parameter
00128     //
00129     const int ENOUGH_INEQUALITIES = (int) .2 * graphSize;
00130     
00131     // 
00132     // Clear all stored inequalities.
00133     //
00134     for (i=lhs.size()-1; i>=0; i--) {
00135         delete lhs[i];
00136         lhs[i] = NULL;
00137     }
00138     lhs.clear();
00139     rhs.clear();
00140     slack.clear();
00141    
00142 
00143     //
00144     // Do edge projection until the graph is too small or enough cuts have
00145     // have been computed.
00146     //    
00147     while (condition) {
00148 
00149         //
00150         // Select a new projectable edge
00151         //
00152         // Includes:
00153         // + check if the edge is projectable
00154         // + store all edges to be deleted that the edge is strongly projectable
00155         // + compute all nodes to be removed
00156         //
00157         bool edgeFound = edgeSelection(lpValue);
00158 
00159         if (!edgeFound) {
00160             break;
00161         }
00162 
00163         //
00164         // Projection: update reduction graph
00165         //  
00166         projection();
00167 
00168         //
00169         // Update size of reduced graph to check if the graph is too small.
00170         // 
00171         reducedGraphSize = 0;
00172         for (i=0; i<graphSize; i++) {
00173             if (adjacentListSize[i] != 0) {
00174                 reducedGraphSize++;
00175             }
00176         }
00177         if (reducedGraphSize <= 5) {
00178             separate = false;
00179             condition = false;
00180         }
00181 
00182         //
00183         // Deside whether to start separation rountines or to project again.
00184         //   
00185         if (separate) {
00186             
00187             //
00188             // Call separation routines on the reduced graph.
00189             // theLhs and theRhs will store the information of the inequalities.
00190             //
00191             numCut = separation(lpValue, &theLhs, &theRhs);
00192 
00193             //
00194             // Check if a violated inequality has been found.
00195             //
00196             if (numCut) {
00197                 //
00198                 // Lift these inequalities.
00199                 //
00200                 lifting(&theLhs, &theRhs);
00201 
00202                 //
00203                 // Store these inequalities.
00204                 //
00205                 storeInequalities(&theLhs, &theRhs, lpValue);
00206         
00207                 //
00208                 // Check if enough inequalities have been computed.
00209                 //
00210                 if (lhs.size() >= ENOUGH_INEQUALITIES) {
00211                     condition = false;
00212                 }
00213             }
00214         }// if
00215 
00216         //
00217         // Clean up
00218         //
00219         edge[0] = edge[1] = -1;
00220         deleteNodes.clear();
00221         for (i=deleteEdges.size()-1; i>=0; i--) {
00222             delete [] deleteEdges[i];
00223         }
00224         deleteEdges.clear();
00225         theLhs.clear();
00226         theRhs.clear();
00227 
00228     }// while
00229     
00230     //
00231     // Select only the best inequalities.
00232     //
00233 //    cleanUpInequalities(lpValue);
00234     
00235     //
00236     // Clean up tree.
00237     //
00238     cleanUp();
00239 
00240     // Return: no error.
00241     return 0;
00242 
00243 }// 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