C:/Programme/home/Administrator/CD/stableSetCode/StableSetMaster.hh

Go to the documentation of this file.
00001 
00002 //
00003 //  Module           : StableSetMaster.hh
00004 //  Description      : Master of the stable set problem. Root of the Branch
00005 //                     and Cut tree.
00006 //  Author           : Steffen Rebennack
00007 //  Email            : srebenac@ix.urz.uni-heidelberg.de;
00008 //                     steffen.rebennack@web.de
00009 //  Copyright        : (C) 2006 by the University of Heidelberg
00010 //  Created on       : Thu Apr 06 10:44:03 2006
00011 //  Last modified by : -
00012 //  Last modified on : -
00013 //  Update count     : 0
00014 //
00016 //
00017 //  Date        Name            Changes/Extensions
00018 //  ----        ----            ------------------
00019 //
00021 
00022 
00023 #ifndef STABLE_SET_MASTER_HH
00024 #define STABLE_SET_MASTER_HH
00025 
00026 #include "abacus/master.h"
00027 #include <vector>
00028 
00029 using namespace std;
00030 
00031 
00032 class Clique;
00033 class EdgeProjection;
00034 class Graph;
00035 class StableSetStatistics;
00036 
00037 
00038 
00046 class StableSetMaster: public ABA_MASTER {
00047 
00048 public:
00049 
00050     // -------------------------------------------------------------------------
00051     // ------------- M e t h o d s  ( p u b l i c ) ----------------------------
00052     // -------------------------------------------------------------------------
00053 
00064     StableSetMaster(const char *problemName, const char *theInequalitiesFileName,
00065                     const char *theSmallGraphName);
00066 
00070     virtual ~StableSetMaster();
00071     
00078     virtual ABA_SUB *firstSub();
00079 
00086     ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *cycleCutPool();
00087 
00094     ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *cliqueCutPool();
00095 
00102     ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *rankCutPool();
00103 
00110     ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *generalCutPool();
00111 
00118     vector<int> *getSolution();
00119 
00126     void pushFixedNode(int node);
00127 
00134     void sortFixedNodes();
00135 
00143     int fixedNodesToOne() const;
00144 
00151     void printTime();
00152 
00159     void startTimer();
00160 
00167     void stopTimer();
00168 
00175     char *getSmallGraphName(); 
00176 
00183     int getRandomNumber(int bound) const;
00184 
00191     virtual void output();
00192 
00193 
00194     // -------------------------------------------------------------------------
00195     // -------------- V a r i a b l e s  ( p u b l i c ) -----------------------
00196     // -------------------------------------------------------------------------
00197 
00202     double m_timeLimitForImprovementHeuristic; 
00203 
00208     double m_timeLimitForMaxCliqueSep;
00209 
00214     double m_minAbsViolationCycle;
00215 
00220     double m_minAbsViolationClique;
00221 
00226     bool m_PoolSeparation;
00227 
00232     bool m_oddCycleSeparation;
00233 
00238     bool m_CliqueHeuristicsSeparation;
00239 
00244     bool m_EdgeProjection;
00245 
00250     bool m_ModKCutsSeparation;
00251 
00256     bool m_LocalCutSeparation;
00257 
00262     bool m_maxCliqueSeparation;
00263 
00268     bool m_showBestStableSet;
00269 
00270 
00271 private:
00272 
00273     // -------------------------------------------------------------------------
00274     // ------------- M e t h o d s  ( p r i v a t e ) --------------------------
00275     // -------------------------------------------------------------------------
00276 
00284     void readStableSetInputData(const char *fileName,
00285                                 char *inequalitiesFileName);
00286 
00295     virtual void initializeOptimization();
00296 
00303     virtual void initializeParameters();
00304 
00305 
00306     // -------------------------------------------------------------------------
00307     // ------------- V a r i a b l e s  ( p r i v a t e ) ----------------------
00308     // -------------------------------------------------------------------------
00309 
00313     Graph *itsGraph;
00314 
00318     Clique *maxCliques;
00319 
00323     EdgeProjection *theProjection;
00324 
00328     StableSetStatistics *theStatistics;
00329 
00333     vector<int> fixedInStableSet;
00334 
00338     vector<int> bestSolution;
00339   
00343     char smallGraphName[256];
00344   
00348     ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *cycleCutPool_;
00349 
00353     ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *cliqueCutPool_;
00354 
00358     ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *rankCutPool_;
00359 
00363     ABA_NONDUPLPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *generalCutPool_;
00364 
00368     ABA_CPUTIMER *myCPUTimer;
00369 
00370 };// end: class StableSetMaster
00371 
00372 #endif
00373 
00374 

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