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