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

Go to the documentation of this file.
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 

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