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