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