Open
Graph Drawing
Framework

 v.2012.05
 

MaxCPlanar_Master.h
Go to the documentation of this file.
00001 /*
00002  * $Revision: 2299 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
00007  ***************************************************************/
00008  
00047 #ifndef OGDF_MAX_CPLANAR_MASTER_H
00048 #define OGDF_MAX_CPLANAR_MASTER_H
00049 
00050 //#include <ogdf/timer.h>
00051 #include <ogdf/basic/GraphCopy.h>
00052 #include <ogdf/internal/cluster/Cluster_EdgeVar.h>
00053 #include <ogdf/internal/cluster/basics.h>
00054 #include <ogdf/basic/Logger.h>
00055 #include <ogdf/basic/ArrayBuffer.h>
00056 
00057 #include <abacus/string.h>
00058 
00059 namespace ogdf {
00060 
00061 
00062 
00063 class Master : public ABA_MASTER {
00064         
00065     friend class Sub;
00066     
00067     // Pointers to the given Clustergraph and underlying Graph are stored.
00068     const ClusterGraph *m_C;
00069     const Graph *m_G;
00070         
00071     
00072     // Each time the primal bound is improved, the integer solution induced Graph is built.
00073     // \a m_solutionGraph is a pointer to the currently best solution induced Graph.
00074     GraphCopy *m_solutionGraph;
00075     
00076     List<nodePair> m_allOneEdges;         //<! Contains all nodePairs whose variable is set to 1.0
00077     List<nodePair> m_originalOneEdges;    //<! Contains original nodePairs whose variable is set to 1.0
00078     List<nodePair> m_connectionOneEdges;  //<! Contains connection nodePairs whose variable is set to 1.0
00079     List<edge> m_deletedOriginalEdges;    //<! Contains original edges whose variable is set to 0.0
00080     
00081 public:
00082     
00083     // Construction and default values
00084     Master(
00085         const ClusterGraph &C,
00086         int heuristicLevel=1,
00087         int heuristicRuns=2,
00088         double heuristicOEdgeBound=0.3,
00089         int heuristicNPermLists=5,
00090         int kuratowskiIterations=3,
00091         int subdivisions=10,
00092         int kSupportGraphs=3,
00093         double kuratowskiHigh=0.7,
00094         double kuratowskiLow=0.3,
00095         bool perturbation=false,
00096         double branchingGap=0.4,
00097         const char *time="00:20:00", //maximum computation time
00098         bool dopricing = true,
00099         bool checkCPlanar = false,   //just check c-planarity
00100         int numAddVariables = 15,
00101         double strongConstraintViolation = 0.3,
00102         double strongVariableViolation = 0.3,
00103         ABA_MASTER::OUTLEVEL ol=Silent);
00104         
00105     // Destruction
00106     virtual ~Master();
00107         
00108     // Initialisation of the first Subproblem
00109     virtual ABA_SUB *firstSub();
00110     
00111     // Returns the objective function coefficient of C-edges
00112     double epsilon() const {return m_epsilon;}
00113     
00114     // Returns the number of variables
00115     int nMaxVars() const {return m_nMaxVars;}
00116         
00117     // Returns a pointer to the underlying Graph
00118     const Graph *getGraph() const {return m_G;}
00119         
00120     // Returns a pointer to the given Clustergraph.
00121     const ClusterGraph *getClusterGraph() const {return m_C;}
00122         
00123     // Updates the "best" Subgraph \a m_solutionGraph found so far and fills edge lists with
00124     // corresponding edges (nodePairs). 
00125     void updateBestSubGraph(List<nodePair> &original, List<nodePair> &connection, List<edge> &deleted);
00126     
00127     // Returns the optimal solution induced Clustergraph
00128     Graph *solutionInducedGraph() {return (Graph*)m_solutionGraph;}
00129     
00130     // Returns nodePairs of original, connection, deleted or all optimal solution edges in list \a edges.
00131     void getAllOptimalSolutionEdges(List<nodePair> &edges) const;
00132     void getOriginalOptimalSolutionEdges(List<nodePair> &edges) const;
00133     void getConnectionOptimalSolutionEdges(List<nodePair> &egdes) const;
00134     void getDeletedEdges(List<edge> &edges) const;
00135         
00136     // Get parameters
00137     const int getKIterations() const {return m_nKuratowskiIterations;}
00138     const int getNSubdivisions() const {return m_nSubdivisions;}
00139     const int getNKuratowskiSupportGraphs() const {return m_nKuratowskiSupportGraphs;}
00140     const int getHeuristicLevel() const {return m_heuristicLevel;}
00141     const int getHeuristicRuns() const {return m_nHeuristicRuns;}
00142     const double getKBoundHigh() const {return m_kuratowskiBoundHigh;}
00143     const double getKBoundLow() const {return m_kuratowskiBoundLow;}
00144     const bool perturbation() const {return m_usePerturbation;}
00145     const double branchingOEdgeSelectGap() const {return m_branchingGap;}
00146     const double getHeuristicFractionalBound() const {return m_heuristicFractionalBound;}
00147     const int numberOfHeuristicPermutationLists() const {return m_nHeuristicPermutationLists;}
00148     const bool getMPHeuristic() const {return m_mpHeuristic;}
00149     const bool getCheckCPlanar() const {return m_checkCPlanar;}
00150     const int getNumAddVariables() const {return m_numAddVariables;}
00151     const double getStrongConstraintViolation() const {return m_strongConstraintViolation;}
00152     const double getStrongVariableViolation() const {return m_strongVariableViolation;}
00153     
00154     // Read global constraint counter, i.e. the number of added constraints of specific type.
00155     const int addedKConstraints() const {return m_nKConsAdded;}
00156     const int addedCConstraints() const {return m_nCConsAdded;}
00157     
00158     
00159     // Set parameters
00160     void setKIterations(int n) {m_nKuratowskiIterations = n;}
00161     void setNSubdivisions(int n) {m_nSubdivisions = n;}
00162     void setNKuratowskiSupportGraphs(int n) {m_nKuratowskiSupportGraphs = n;}
00163     void setNHeuristicRuns(int n) {m_nHeuristicRuns = n;}
00164     void setKBoundHigh(double n) {m_kuratowskiBoundHigh = ((n>0.0 && n<1.0) ? n : 0.8);}
00165     void setKBoundLow(double n) {m_kuratowskiBoundLow = ((n>0.0 && n<1.0) ? n : 0.2);}
00166     void heuristicLevel(int level) {m_heuristicLevel = level;}
00167     void setHeuristicRuns(int n) {m_nHeuristicRuns = n;}
00168     void setPertubation(bool b) {m_usePerturbation = b;}
00169     void setHeuristicFractionalBound(double b) {m_heuristicFractionalBound = b;}
00170     void setHeuristicPermutationLists(int n) {m_nHeuristicPermutationLists = n;}
00171     void setMPHeuristic(bool b) {m_mpHeuristic = b;}
00172     void setNumAddVariables(int i) {m_numAddVariables=i;}
00173     void setStrongConstraintViolation(double d) { m_strongConstraintViolation=d;}
00174     void setStrongVariableViolation(double d) { m_strongVariableViolation=d;}
00175     
00177     void setPortaFile(bool b) {m_porta = b;}
00178     
00179     // Updating global constraint counter
00180     void updateAddedCCons(int n) {m_nCConsAdded += n;}
00181     void updateAddedKCons(int n) {m_nKConsAdded += n;}
00182     
00183     // Returns global primal and dual bounds.
00184     double getPrimalBound() {return globalPrimalBound;}
00185     double getDualBound() {return globalDualBound;}
00186     
00187     // Cut pools for connectivity and planarity
00189     ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *getCutConnPool() {return m_cutConnPool;}
00191     ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *getCutKuraPool() {return m_cutKuraPool;}
00192     
00195     bool &useDefaultCutPool() { return m_useDefaultCutPool;} 
00196 
00197 #ifdef OGDF_DEBUG
00198     bool m_solByHeuristic; //solution computed by heuristic or ILP
00199         // Simple output function to print the given graph to the console.
00200     // Used for debugging only.
00201     void printGraph(const Graph &G);
00202 #endif
00203 
00206     const char* getStdConstraintsFileName()
00207     {
00208         return "StdConstraints.txt";
00209     }
00210     
00211     int getNumInactiveVars() { return m_inactiveVariables.size();}
00212 
00213 protected:
00214     
00215     // Initializes constraints and variables and an initial dual bound.
00216     virtual void initializeOptimization();
00217     
00218     // Function that is invoked at the end of the optimization
00219     virtual void terminateOptimization();
00220         
00221     double heuristicInitialLowerBound();
00222     
00223 private:
00224         
00225     // Computes a dual bound for the optimal solution.
00226     // Tries to find as many edge-disjoint Kuratowski subdivisions as possible.
00227     // If k edge-disjoint groups of subdivisions are found, the upper bound can be
00228     // initialized with number of edges in underlying graph minus k.
00229     double heuristicInitialUpperBound();
00230     
00231     // Is invoked by heuristicInitialUpperBound()
00232     void clusterConnection(cluster c, GraphCopy &GC, double &upperBound);
00233     
00234     // Computes the graphtheoretical distances of edges incident to node \a u.
00235     void nodeDistances(node u, NodeArray<NodeArray<int> > &dist);
00236         
00237     
00238     // Parameters
00239     int m_nKuratowskiSupportGraphs;     // Maximal number of times the Kuratowski support graph is computed
00240     int m_nKuratowskiIterations;        // Maximal number of times BoyerMyrvold is invoked
00241     int m_nSubdivisions;                // Maximal number of extracted Kuratowski subdivisions
00242     int m_nMaxVars;                     // Max Number of variables
00243     int m_heuristicLevel;               // Indicates if primal heuristic shall be used or not
00244     int m_nHeuristicRuns;               // Counts how often the primal heuristic has been called
00245     
00246     bool m_usePerturbation;             // Indicates whether C-variables should be perturbated or not
00247     double m_branchingGap;              // Modifies the branching behaviour
00248     double m_heuristicFractionalBound;  
00249     int m_nHeuristicPermutationLists;   // The number of permutation lists used in the primal heuristic
00250     bool m_mpHeuristic;                 
00251                                         // should be used to derive lower bound if only root cluster exists 
00252     
00253     double m_kuratowskiBoundHigh;       // Upper bound for deterministic edge addition in computation of the Supportgraph
00254     double m_kuratowskiBoundLow;        // Lower bound for deterministic edge deletion in computation of the Supportgraph
00255     
00256     int m_numAddVariables;              // how many variables should i add maximally per pricing round?
00257     double m_strongConstraintViolation; // when do i consider a constraint strongly violated -> separate in first stage
00258     double m_strongVariableViolation;   // when do i consider a variable strongly violated (red.cost) -> separate in first stage
00259     
00260     ABA_MASTER::OUTLEVEL m_out;         // Determines the output level of ABACUS
00261     ABA_STRING *m_maxCpuTime;           // Time threshold for optimization
00262     
00263 
00264     // The basic objective function coefficient for connection edges.
00265     double m_epsilon;
00266     // If pertubation is used, this variable stores the largest occuring coeff,
00267     // i.e. the one closest to 0. Otherwise it corresponds to \a m_epsilon 
00268     double m_largestConnectionCoeff;
00269     
00270     // Counters for the number of added constraints
00271     int m_nCConsAdded;
00272     int m_nKConsAdded;
00273     int m_solvesLP;
00274     int m_varsInit;
00275     int m_varsAdded;
00276     int m_varsPotential;
00277     int m_varsMax;
00278     int m_varsCut;
00279     int m_varsKura;
00280     int m_varsPrice;
00281     int m_varsBranch;
00282     int m_activeRepairs;
00283     ArrayBuffer<int> m_repairStat;
00284     inline void clearActiveRepairs() {
00285         if(m_activeRepairs) {
00286             m_repairStat.push(m_activeRepairs);
00287             m_activeRepairs = 0; 
00288         }
00289     }
00290     
00291     double globalPrimalBound;
00292     double globalDualBound;
00293     
00294     inline double getDoubleTime(const ABA_TIMER* act) {
00295         long tempo = act->centiSeconds()+100*act->seconds()+6000*act->minutes()+360000*act->hours();
00296         return  ((double) tempo)/ 100.0;
00297     }
00298     
00299     //number of calls of the fast max planar subgraph heuristic
00300     const int m_fastHeuristicRuns;
00301     
00303     ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE > *m_cutConnPool; 
00304     ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE > *m_cutKuraPool; 
00305     
00308     bool m_useDefaultCutPool;
00309     
00313     bool m_checkCPlanar;  
00314     
00316     double m_delta;
00317     double m_deltaCount;    
00318     double nextConnectCoeff() { return (m_checkCPlanar ? -1 : -m_epsilon) + m_deltaCount--*m_delta; }; // TODO-TESTING
00319     EdgeVar* createVariable(ListIterator<nodePair>& it) {
00320         ++m_varsAdded;
00321         EdgeVar* v = new EdgeVar(this, nextConnectCoeff(), EdgeVar::CONNECT, (*it).v1, (*it).v2);
00322         v->printMe(Logger::slout()); 
00323         m_inactiveVariables.del(it);
00324         return v;
00325     }
00326     List<nodePair> m_inactiveVariables;
00327     void generateVariablesForFeasibility(const List<ChunkConnection*>& ccons, List<EdgeVar*>& connectVars);
00328     
00329     bool goodVar(node a, node b);
00330     
00332     bool m_porta;
00335     void getCoefficients(ABA_CONSTRAINT* con,  const List<EdgeVar *> & orig, 
00336         const List<EdgeVar* > & connect, List<double> & coeffs);
00337 };
00338 
00339 }//end namespace
00340 
00341 #endif