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

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

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