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