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

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : CliqueConstraint.cpp
00004 //  Description      : Constraint class for clique inequalities.
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       : Tue Apr 04 13:45:46 2006
00010 //  Last modified by : -
00011 //  Last modified on : -
00012 //  Update count     : 0
00013 //
00015 //
00016 //  Date        Name            Changes/Extensions
00017 //  ----        ----            ------------------
00018 //
00020 
00021 #include "abacus/row.h"
00022 #include "CliqueConstraint.hh"
00023 #include "Graph.hh"
00024 #include "Node.hh"
00025 
00026 
00027 
00028 // -----------------------------------------------------------------------------
00029 // --------------- M e t h o d s  ( p u b l i c ) ------------------------------
00030 // -----------------------------------------------------------------------------
00031 
00032 
00033 // -----------------------------------------------------------------------------
00034 // C o n s t r u c t o r
00035 //
00036 // This class is derived from the abstract base class ABA_CONSTRAINT.
00037 //
00038 // Because a clique constraint is uniquely determined by its nodes, this
00039 // constructor saves all nodes of the clique. The main part is
00040 // the call of the constructor of class ABA_CONSTRAINT with the following
00041 // arguments:
00042 // 1.) A pointer to the corresponding master of the optimization.
00043 // 2.) A pointer to the subproblem associated with this constraint because the
00044 //     constraints should be only active in this sub problem and its children.
00045 // 3.) This constraint is of kind less (or equal).
00046 // 4.) The ride hand side of this constraint is 1.
00047 // 5.) This constraint can be removed from the active constraint set.
00048 // 6.) This constraint is global valid and not only local.
00049 // 7.) There is no lifting procedure implemented.
00050 // -----------------------------------------------------------------------------
00051 CliqueConstraint::CliqueConstraint(ABA_MASTER *master, vector<int> *clique,
00052                                    Graph *theGraph):
00053     ABA_CONSTRAINT(master, NULL, ABA_CSENSE::Less, 1.0, true, false, false),
00054     nodesOfClique(clique->size()),
00055     itsGraph(theGraph)
00056 {
00057     // Store this inequality that it can be checked.
00058     ofstream fout(theGraph->getFileName(), ios::app);
00059 
00060     // Save the clique inequality.
00061     for (int i=0; i<clique->size(); i++) {
00062         nodesOfClique[i] = (*clique)[i];
00063         fout << "  1 x_" << itsGraph->translateNode(nodesOfClique[i]);
00064     }
00065     fout << "  <  1" << endl;
00066     fout.close();
00067 
00068     // Calculate the key.
00069     calculateHashKey();
00070 }
00071 
00072 
00073 // -----------------------------------------------------------------------------
00074 // D e s t r u c t o r
00075 // -----------------------------------------------------------------------------
00076 CliqueConstraint::~CliqueConstraint() {
00077 }
00078 
00079 
00080 // -----------------------------------------------------------------------------
00081 // g e n R o w
00082 //
00083 // This function redefines the pure virtual function of the base class
00084 // ABA_CONSTRAINT. It returns the constraint in sprase format. 
00085 // -----------------------------------------------------------------------------
00086 int CliqueConstraint::genRow(ABA_ACTIVE<ABA_VARIABLE,ABA_CONSTRAINT> *var, 
00087                              ABA_ROW &row)
00088 {
00089 //    row.realloc(nodesOfClique.size() + 1);
00090 //    row.clear();
00091     
00092     // Store the indices of the nodes of the clique.
00093     for (int i=0; i<nodesOfClique.size(); i++) {
00094         row.insert(nodesOfClique[i],1.0);
00095     }
00096     // The rhs of the clique.
00097     row.rhs(1);
00098     // Sense of the inequality.
00099     row.sense(ABA_CSENSE::Less);
00100     
00101     return row.nnz();
00102 }
00103 
00104 
00105 // -----------------------------------------------------------------------------
00106 // c o e f f
00107 // 
00108 // This function computes the coefficient of the variable var. It redefines the
00109 // pure virtual function of the base class ABA_CONSTRAINT. The coefficient of
00110 // a variable of a clique constraint is 1 if the variable is part of the clique 
00111 // and otherwise its coefficient is 0.
00112 // -----------------------------------------------------------------------------
00113 double CliqueConstraint::coeff(ABA_VARIABLE *var) {
00114 
00115     // Cast ABA_VARIABLE* to NODE*.
00116     Node *node = (Node *) var;
00117     // search for this variable in the clique
00118     for (int i=0; i<nodesOfClique.size(); i++) {
00119         if (node->nodeNumber() == nodesOfClique[i]) {
00120             return 1.0;
00121         }
00122     }
00123     return 0.0;
00124 }
00125 
00126 
00127 // -----------------------------------------------------------------------------
00128 // g e t S i z e
00129 // -----------------------------------------------------------------------------
00130 int CliqueConstraint::getSize() {
00131     return nodesOfClique.size();
00132 }
00133 
00134 
00135 // -----------------------------------------------------------------------------
00136 // i s I n C o n s t r a i n t
00137 //
00138 // This function checks if a node is member of this constraint. It return the
00139 // value true if the node is a memebr and otherwise false.
00140 // This method is used by the function equal(..).
00141 // -----------------------------------------------------------------------------
00142 bool CliqueConstraint::isInConstraint(int node) {
00143 
00144     for(int i=0; i<nodesOfClique.size(); i++) {
00145         if (nodesOfClique[i] == node) {
00146             return true;
00147         }
00148     }
00149 
00150     return false;
00151 }
00152 
00153 
00154 // -----------------------------------------------------------------------------
00155 // e q u a l
00156 //
00157 // This function compares if this constraint is identical with the constraint
00158 // cv in a mathematical sense. This function is required becuase the constraint
00159 // is stored in a pool of the class ABA_NONDUPLPOOL.
00160 // It returns true if the constraints are equal and otherwise false.
00161 // -----------------------------------------------------------------------------
00162 bool CliqueConstraint::equal(ABA_CONVAR *cv) {
00163 
00164     bool isEqual = true;
00165     if (thisHashKey != ((CliqueConstraint *)cv)->hashKey()) {
00166         isEqual = false;
00167     }
00168     if (nodesOfClique.size() != ((CliqueConstraint *)cv)->getSize()) {
00169         isEqual = false;
00170     }
00171 
00172     for(int i=0; i<nodesOfClique.size(); i++) {
00173         if (!((CliqueConstraint *)cv)->isInConstraint(nodesOfClique[i])) {
00174             isEqual = false;
00175         }
00176     }
00177 
00178     return isEqual;
00179 }
00180 
00181 
00182 // -----------------------------------------------------------------------------
00183 // n a m e
00184 //
00185 // This function returns the name of the constraint. It is required if the
00186 // constraint is stored in a pool of class ABA_NONDUPLPOOL.
00187 // -----------------------------------------------------------------------------
00188 const char* CliqueConstraint::name() {
00189     return "CliqueConstraint";
00190 }
00191 
00192 
00193 // -----------------------------------------------------------------------------
00194 // h a s h K e y
00195 //
00196 // This method provides a key for the constraint that can be used to insert it
00197 // into a hash table. In this case it is not required that any two items have
00198 // different keys. This function is required to store the constraint in a pool
00199 // of the class ABA_NIONDUPLPOOL.
00200 // -----------------------------------------------------------------------------
00201 unsigned CliqueConstraint::hashKey() {
00202     return thisHashKey;
00203 }
00204 
00205 
00206 
00207 // -----------------------------------------------------------------------------
00208 // --------------- M e t h o d s  ( p r i v a t e ) ----------------------------
00209 // -----------------------------------------------------------------------------
00210 
00211 
00212 // -----------------------------------------------------------------------------
00213 // c a l c u l a t e H a s h K e y
00214 // -----------------------------------------------------------------------------
00215 void CliqueConstraint::calculateHashKey() {
00216 
00217     thisHashKey = 1;
00218     for (int i=0; i<nodesOfClique.size(); i++) {
00219         thisHashKey *= (nodesOfClique[i] + 1265);
00220         thisHashKey = thisHashKey % 9973;
00221     }
00222 }
00223 

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