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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : Preprocessing.cpp
00004 //  Description      : Preprocessing 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       : 
00010 //  Last modified by : -
00011 //  Last modified on : -
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
00017 //  ----        ----            ------------------
00018 //
00020 
00021 #include "Preprocessing.hh"
00022 #include "abacus/row.h"
00023 #include "Graph.hh"
00024 #include "StableSetMaster.hh"
00025 #include "StableSetStatistics.hh"
00026 
00027 
00028 #include "abacus/array.h"
00029 #include "abacus/cplexif.h"
00030 
00031 
00032 // -----------------------------------------------------------------------------
00033 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00034 // -----------------------------------------------------------------------------
00035 
00036 // -----------------------------------------------------------------------------
00037 // C o n s t r u c t o r
00038 //
00039 // -----------------------------------------------------------------------------
00040 Preprocessing::Preprocessing(StableSetMaster *theMaster, Graph *theGraph,
00041                              StableSetStatistics *theStatistics):
00042     itsMaster(theMaster),
00043     itsGraph(theGraph),
00044     itsStatistics(theStatistics)
00045 {
00046 }
00047 
00048 
00049 // -----------------------------------------------------------------------------
00050 // D e s t r u c t o r
00051 // -----------------------------------------------------------------------------
00052 Preprocessing::~Preprocessing() {
00053 }
00054 
00055 
00056 // -----------------------------------------------------------------------------
00057 // p r e p r o c e s s i n g 
00058 //
00059 // Fox nodes according cliques or integer LP values.
00060 // -----------------------------------------------------------------------------
00061 void Preprocessing::preprocessing() {
00062 
00063     bool   fixed = true; // Indicate if a fixing could be done. 
00064     double *sol;         // Pointer to LP-solution.
00065 
00066     //
00067     // Fix nodes until no fixing could be done.
00068     //
00069     while (fixed) {
00070 
00071         //
00072         // Call clique fixing.
00073         //
00074         fixed = fixVariablesClique();
00075 
00076         //
00077         // Fixing according to LP.
00078         //
00079         if (itsGraph->numberOfNodes()) {
00080             sol = solveLP();
00081             fixed = fixVariablesEdgeLP(sol) || fixed;
00082             if (!itsGraph->numberOfNodes()) {
00083                 fixed = false;            
00084             }
00085 
00086             delete [] sol;
00087         }
00088     }// while
00089 
00090     if (itsGraph->numberOfNodes() == 0) {
00091         // Solution was found during preprocessing.
00092         itsStatistics->solutionFound(3);
00093     }
00094 
00095     itsMaster->sortFixedNodes();
00096 
00097 }// end: void preprocessing()
00098 
00099 
00100 
00101 // -----------------------------------------------------------------------------
00102 // --------------- M e t h o d s  ( p r i v a t e ) ----------------------------
00103 // -----------------------------------------------------------------------------
00104 
00105 
00106 // -----------------------------------------------------------------------------
00107 // f i x V a r i a b l e s C l i q u e
00108 //
00109 // Fix all variables which neighborhodd buils a clique.
00110 // -----------------------------------------------------------------------------
00111 bool Preprocessing::fixVariablesClique() {
00112 
00113     int  i, j, k;          // Loop counter.
00114     bool fixed = false;    // True if a fixing could be done.
00115     bool isClique;         // Indicate if this clique can be fixed or not.
00116     int numberOfNodes = itsGraph->numberOfNodes(); 
00117     int node;              // A node
00118     int size;              // A size.
00119     vector<int> nodesToCheck(numberOfNodes); // Vector storing all nodes which
00120                                              // have to be checked.
00121     vector<int> fixNodes;  // 
00122 
00123     // At the beginning check each node.
00124     for (i=0; i<itsGraph->numberOfNodes(); i++) {
00125         nodesToCheck[i] = i;
00126     }
00127 
00128     //
00129     // Try to fix a node until all nodes have been checked 
00130     // and no more fixing could be done.
00131     //
00132     while (nodesToCheck.size() != 0) {
00133         
00134         // Get node to check next. 
00135         node = nodesToCheck.back();
00136         nodesToCheck.pop_back();
00137 
00138         // Size of the adjacent list of this node.
00139         size = itsGraph->adjacentListSize(node);
00140 
00141         isClique = true;
00142 
00143         // Check whether all the neighbours of this node build a clique or not.
00144         for (i=0; i<size; i++) {
00145 
00146             // The weight of that node has to be greater than the weight of each
00147             // member of the clique. 
00148             if (itsGraph->weighted() 
00149                 && (itsGraph->weight(node) //
00150                     < itsGraph->weight(itsGraph->adjacentListElement(node,i)))){
00151                 isClique = false;
00152                 break;
00153             }
00154 
00155             //
00156             // Check if ALL its neighbors build a clique.
00157             //  
00158             for (j=i+1; j<size; j++) {
00159                 k = 0;
00160                 if (!itsGraph->isMemberOfAdjacentList( //
00161                         itsGraph->adjacentListElement(node,i),//
00162                         k, itsGraph->adjacentListElement(node,j))
00163                    ) {
00164                     i = size;
00165                     isClique = false;
00166                     break;
00167                 }
00168             }// for
00169         }// for
00170 
00171 
00172         //
00173         // If all the neighbours of node 'node' build a clique we can fix it
00174         // in the following cases:
00175         // - we have the cardinality stable set problem
00176         // - if the problem is weighted and node 'node' has the greates
00177         // weight of all the members of the clique.
00178         //
00179         if (isClique) {
00180 
00181             fixed = true;
00182             fixNodes.resize(size + 1);
00183             fixNodes[0] = node;
00184 
00185             for (i=1; i<size + 1; i++) {
00186                 fixNodes[i] = itsGraph->adjacentListElement(node, i-1);
00187                 // Delete this node from the list of nodes to be checked.
00188                 k = 0;
00189                 while ((k < nodesToCheck.size()) && (nodesToCheck[k] != fixNodes[i])
00190                        ) {
00191                     k++;
00192                 }
00193                 if (nodesToCheck[k] == fixNodes[i]) {
00194                     nodesToCheck.erase(nodesToCheck.begin() + k);
00195                 }
00196 
00197             }
00198             sort(fixNodes.begin(), fixNodes.end());
00199 
00200             // Fix this node to value one.
00201             itsMaster->pushFixedNode(itsGraph->translateNode(node));
00202 
00203             // Delete all the nodes of that clique from the graph
00204             // and update the nodes to be checked.
00205             itsGraph->deleteNodesFromGraph(&fixNodes, &nodesToCheck);
00206         }
00207     }
00208 
00209     // Return status.
00210     return (fixed && (itsGraph->numberOfNodes() != 0));
00211 
00212 }// fixVariablesClique()
00213 
00214 
00215 // -----------------------------------------------------------------------------
00216 // s o l v e L P
00217 //
00218 // Create and solve the initial LP. This linear program constains only the
00219 // edge inequalities and the non-negativity constraints. 
00220 // Cplex is used to determine the optimum which is return as a pointer. 
00221 // -----------------------------------------------------------------------------
00222 double *Preprocessing::solveLP() {
00223 
00224     //
00225     // Create first LP
00226     //
00227 
00228     // The number of constraints of the LP is the number of edges.
00229     int i,j;
00230     int size;
00231     int numberOfConstraints = itsGraph->numberOfEdges();
00232     int numberOfVariables   = itsGraph->numberOfNodes();
00233 
00234     ABA_ROW *constraint;
00235     // Buffer the non zero elements of a constraint.
00236     ABA_BUFFER<int> nonZeroElementsBuf(itsMaster, 2);
00237     // Store the vertices of a constraint...
00238     ABA_ARRAY<int> *nonZeroElements;
00239     // ...and their coefficients.
00240     ABA_ARRAY<double> *coefficients;
00241     // The coefficients of the target function. They are initialized
00242     // with value 1.
00243     ABA_ARRAY<double> objectiveFunctionCoefficient(itsMaster,//
00244                                                    numberOfVariables, 1);
00245     // Lower bound of each variable is 0.
00246     ABA_ARRAY<double> lowerBound(itsMaster, numberOfVariables, 0);
00247     // The upper bound for the variable is 1.
00248     ABA_ARRAY<double> upperBound(itsMaster, numberOfVariables, 1);
00249     // Store all constraints.
00250     // There are number of edges constraints.
00251     ABA_ARRAY<ABA_ROW*> allConstraints(itsMaster, numberOfConstraints);
00252 
00253 
00254     //
00255     // Compute LP
00256     //
00257 
00258     int cnt = 0;
00259     int element;
00260     // Construct all constraints.
00261     for (i=0; i<numberOfVariables; i++) {
00262         size = itsGraph->adjacentListSize(i);
00263         for (j=0; j<size; j++) {
00264             element = itsGraph->adjacentListElement(i,j);
00265             if (element > i) {
00266                 nonZeroElementsBuf.push(i);
00267                 nonZeroElementsBuf.push(element);
00268                 nonZeroElements = new ABA_ARRAY<int>(itsMaster,//
00269                                                      nonZeroElementsBuf);
00270                 coefficients    = new ABA_ARRAY<double>(itsMaster, 2, 1);
00271                 nonZeroElementsBuf.clear();
00272 
00273                 // The new constraint.
00274                 constraint = new ABA_ROW(itsMaster,
00275                                          2,
00276                                          (*nonZeroElements),
00277                                          (*coefficients),
00278                                          ABA_CSENSE::Less,
00279                                          1);
00280                 // Store this constraint.
00281                 allConstraints[cnt] = constraint;
00282                 cnt++;
00283         
00284                 delete nonZeroElements;
00285                 delete coefficients;            
00286 
00287             }// if
00288         }// for
00289     }// for
00290 
00291 
00292     //
00293     // Optimize LP 
00294     //
00295 
00296     ABA_CPLEXIF lp(itsMaster);
00297     lp.initialize(ABA_OPTSENSE::Max,
00298                   numberOfConstraints,
00299                   numberOfConstraints,
00300                   numberOfVariables,
00301                   numberOfVariables,
00302                   objectiveFunctionCoefficient,
00303                   lowerBound,
00304                   upperBound,
00305                   allConstraints);
00306 
00307     // Optimize and check if optimal solution could be computed.
00308     if (!(ABA_LP::Optimal == lp.optimize(ABA_LP::Primal))) {
00309         itsMaster->err() << "ERROR in Preprocessing::solveLP()." << endl;
00310         itsMaster->err() << "LP could not be dolved to optimality." << endl;
00311         exit(itsMaster->Fatal);
00312     }
00313 
00314     double *sol = new double[numberOfVariables];
00315     for (i=0; i<numberOfVariables; i++) {
00316         sol[i] = lp.xVal(i);
00317     }
00318 
00319     // Clean up.
00320     for (i=numberOfConstraints-1; i>=0; i--) {
00321         delete allConstraints[i];
00322         allConstraints[i] = NULL;
00323     }
00324 
00325     return sol;
00326 
00327 }// solveLP
00328 
00329 
00330 
00331 // -----------------------------------------------------------------------------
00332 // f i x V a r i a b l e s F i r s t L P
00333 //
00334 // The LP Relaxation of the stable set polytop with only the trivial- and
00335 // the edge inequalities has a special property. If a variable of the optimal
00336 // solution has value 1 it can be fixed. The function fixVariablesFirstLP()
00337 // uses this attribute and fixes all variables with value 1 and all their
00338 // neighbours to value 0.
00339 // This is independent from the weighted case.
00340 // -----------------------------------------------------------------------------
00341 bool Preprocessing::fixVariablesEdgeLP(double *sol) {
00342 
00343     int  i, j, k;         // Loop variables.
00344     int  numberOfNodes = itsGraph->numberOfNodes(); // Problem size.
00345     bool fixed = false;   // Indicate if a node could be fixed or not.
00346     int  node;
00347     bool isElement;
00348 
00349 
00350     vector<int> fixOne;   // Fix the values of the nodes in this array to one.
00351     vector<int> fixZero;  // Fix the values of the nodes in this array to zero.
00352 
00353     //
00354     // Get all variables wich have value 1 and save them in the vector fixOne.
00355     // If a variables with value 1 is found, save all its neighbours in
00356     // vector fixZero.
00357     //
00358     for (i=0; i<numberOfNodes; i++) {
00359         if ((sol[i] < (1 + itsMaster->machineEps()))
00360              && (sol[i] > (1 - itsMaster->machineEps()))
00361            ) {
00362             fixOne.push_back(i);
00363             // Check the neighbourhood.
00364             for (j=0; j<itsGraph->adjacentListSize(i); j++) {
00365                 node = itsGraph->adjacentListElement(i, j);
00366                 // Check if this node is already an element of the vecor.
00367                 isElement = false;
00368                 for (k=0; k<fixZero.size(); k++) {
00369                     if (fixZero[k] == node) {
00370                         isElement = true;
00371                         break;
00372                     }
00373                 }
00374                 if (!isElement) {
00375                     fixZero.push_back(node);
00376                 }
00377             }
00378         }
00379     }
00380 
00381     //
00382     // Fix all variables of the two vectors fixOne and fixZero.
00383     //
00384     if (!fixOne.empty()) {
00385 
00386         // Store all nodes which should be fixed.
00387         vector<int> fixNodes(fixOne.size() + fixZero.size());
00388         int size;               // Size of vector fixOne.
00389 
00390         size = fixOne.size();
00391         for (i=0; i<size; i++) {
00392             fixNodes[i] = fixOne[i];
00393             // Store all nodes which are fixed to value 1.
00394             itsMaster->pushFixedNode(itsGraph->translateNode(fixOne[i]));
00395         }
00396 
00397         for (i=0; i<fixZero.size(); i++) {
00398             fixNodes[size + i] = fixZero[i];
00399         }
00400         sort(fixNodes.begin(), fixNodes.end());
00401 
00402         // Delete all fixed nodes from the graph.
00403         itsGraph->deleteNodesFromGraph(&fixNodes);
00404 
00405         // Update statistics.
00406         itsGraph->fixVariablesFirstLP(fixNodes.size());
00407         fixed = true;
00408     }
00409     
00410     // Return status.
00411     return fixed;
00412 
00413 } // end: bool fixVariablesFirstLP(..)
00414 
00415 
00416 
00417 
00418 
00419 
00420 
00421 
00422 
00423 

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