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

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

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