ext/OGDF/ogdf/internal/cluster/MaxCPlanar_Master.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of the master class for the Branch&Cut algorithm
  11  * for the Maximum C-Planar SubGraph problem.
  12  *
  13  * This class is managing the optimization.
  14  * Variables and initial constraints are generated and pools are initialized.
  15  *
  16  * \author Mathias Jansen
  17  *
  18  *
  19  * \par License:
  20  * This file is part of the Open Graph Drawing Framework (OGDF).
  21  *
  22  * \par
  23  * Copyright (C)<br>
  24  * See README.txt in the root directory of the OGDF installation for details.
  25  *
  26  * \par
  27  * This program is free software; you can redistribute it and/or
  28  * modify it under the terms of the GNU General Public License
  29  * Version 2 or 3 as published by the Free Software Foundation;
  30  * see the file LICENSE.txt included in the packaging of this file
  31  * for details.
  32  *
  33  * \par
  34  * This program is distributed in the hope that it will be useful,
  35  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  36  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  37  * GNU General Public License for more details.
  38  *
  39  * \par
  40  * You should have received a copy of the GNU General Public
  41  * License along with this program; if not, write to the Free
  42  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  43  * Boston, MA 02110-1301, USA.
  44  *
  45  * \see  http://www.gnu.org/copyleft/gpl.html
  46  ***************************************************************/
  47
  48 #ifndef OGDF_MAX_CPLANAR_MASTER_H
  49 #define OGDF_MAX_CPLANAR_MASTER_H
  50
  51 //#include <ogdf/timer.h>
  52 #include <ogdf/basic/GraphCopy.h>
  53 #include <ogdf/internal/cluster/Cluster_EdgeVar.h>
  54 #include <ogdf/internal/cluster/basics.h>
  55 #include <ogdf/basic/Logger.h>
  56 #include <ogdf/basic/ArrayBuffer.h>
  57
  58 #include <abacus/string.h>
  59
  60 namespace ogdf {
  61
  62
  63
  64 class Master : public ABA_MASTER {
  65
  66         friend class Sub;
  67
  68         // Pointers to the given Clustergraph and underlying Graph are stored.
  69         const ClusterGraph *m_C;
  70         const Graph *m_G;
  71
  72
  73         // Each time the primal bound is improved, the integer solution induced Graph is built.
  74         // \a m_solutionGraph is a pointer to the currently best solution induced Graph.
  75         GraphCopy *m_solutionGraph;
  76
  77         List<nodePair> m_allOneEdges;             //<! Contains all nodePairs whose variable is set to 1.0
  78         List<nodePair> m_originalOneEdges;        //<! Contains original nodePairs whose variable is set to 1.0
  79         List<nodePair> m_connectionOneEdges;  //<! Contains connection nodePairs whose variable is set to 1.0
  80         List<edge> m_deletedOriginalEdges;        //<! Contains original edges whose variable is set to 0.0
  81
  82 public:
  83
  84         // Construction and default values
  85         Master(
  86                 const ClusterGraph &C,
  87                 int heuristicLevel=1,
  88                 int heuristicRuns=2,
  89                 double heuristicOEdgeBound=0.3,
  90                 int heuristicNPermLists=5,
  91                 int kuratowskiIterations=3,
  92                 int subdivisions=10,
  93                 int kSupportGraphs=3,
  94                 double kuratowskiHigh=0.7,
  95                 double kuratowskiLow=0.3,
  96                 bool perturbation=false,
  97                 double branchingGap=0.4,
  98                 const char *time="00:20:00", //maximum computation time
  99                 bool dopricing = true,
 100                 bool checkCPlanar = false,   //just check c-planarity
 101                 int numAddVariables = 15,
 102                 double strongConstraintViolation = 0.3,
 103                 double strongVariableViolation = 0.3,
 104                 ABA_MASTER::OUTLEVEL ol=Silent);
 105
 106         // Destruction
 107         virtual ~Master();
 108
 109         // Initialisation of the first Subproblem
 110         virtual ABA_SUB *firstSub();
 111
 112         // Returns the objective function coefficient of C-edges
 113         double epsilon() const {return m_epsilon;}
 114
 115         // Returns the number of variables
 116         int nMaxVars() const {return m_nMaxVars;}
 117
 118         // Returns a pointer to the underlying Graph
 119         const Graph *getGraph() const {return m_G;}
 120
 121         // Returns a pointer to the given Clustergraph.
 122         const ClusterGraph *getClusterGraph() const {return m_C;}
 123
 124         // Updates the "best" Subgraph \a m_solutionGraph found so far and fills edge lists with
 125         // corresponding edges (nodePairs).
 126         void updateBestSubGraph(List<nodePair> &original, List<nodePair> &connection, List<edge> &deleted);
 127
 128         // Returns the optimal solution induced Clustergraph
 129         Graph *solutionInducedGraph() {return (Graph*)m_solutionGraph;}
 130
 131         // Returns nodePairs of original, connection, deleted or all optimal solution edges in list \a edges.
 132         void getAllOptimalSolutionEdges(List<nodePair> &edges) const;
 133         void getOriginalOptimalSolutionEdges(List<nodePair> &edges) const;
 134         void getConnectionOptimalSolutionEdges(List<nodePair> &egdes) const;
 135         void getDeletedEdges(List<edge> &edges) const;
 136
 137         // Get parameters
 138         const int getKIterations() const {return m_nKuratowskiIterations;}
 139         const int getNSubdivisions() const {return m_nSubdivisions;}
 140         const int getNKuratowskiSupportGraphs() const {return m_nKuratowskiSupportGraphs;}
 141         const int getHeuristicLevel() const {return m_heuristicLevel;}
 142         const int getHeuristicRuns() const {return m_nHeuristicRuns;}
 143         const double getKBoundHigh() const {return m_kuratowskiBoundHigh;}
 144         const double getKBoundLow() const {return m_kuratowskiBoundLow;}
 145         const bool perturbation() const {return m_usePerturbation;}
 146         const double branchingOEdgeSelectGap() const {return m_branchingGap;}
 147         const double getHeuristicFractionalBound() const {return m_heuristicFractionalBound;}
 148         const int numberOfHeuristicPermutationLists() const {return m_nHeuristicPermutationLists;}
 149         const bool getMPHeuristic() const {return m_mpHeuristic;}
 150         const bool getCheckCPlanar() const {return m_checkCPlanar;}
 151         const int getNumAddVariables() const {return m_numAddVariables;}
 152         const double getStrongConstraintViolation() const {return m_strongConstraintViolation;}
 153         const double getStrongVariableViolation() const {return m_strongVariableViolation;}
 154
 155         // Read global constraint counter, i.e. the number of added constraints of specific type.
 156         const int addedKConstraints() const {return m_nKConsAdded;}
 157         const int addedCConstraints() const {return m_nCConsAdded;}
 158
 159
 160         // Set parameters
 161         void setKIterations(int n) {m_nKuratowskiIterations = n;}
 162         void setNSubdivisions(int n) {m_nSubdivisions = n;}
 163         void setNKuratowskiSupportGraphs(int n) {m_nKuratowskiSupportGraphs = n;}
 164         void setNHeuristicRuns(int n) {m_nHeuristicRuns = n;}
 165         void setKBoundHigh(double n) {m_kuratowskiBoundHigh = ((n>0.0 && n<1.0) ? n : 0.8);}
 166         void setKBoundLow(double n) {m_kuratowskiBoundLow = ((n>0.0 && n<1.0) ? n : 0.2);}
 167         void heuristicLevel(int level) {m_heuristicLevel = level;}
 168         void setHeuristicRuns(int n) {m_nHeuristicRuns = n;}
 169         void setPertubation(bool b) {m_usePerturbation = b;}
 170         void setHeuristicFractionalBound(double b) {m_heuristicFractionalBound = b;}
 171         void setHeuristicPermutationLists(int n) {m_nHeuristicPermutationLists = n;}
 172         void setMPHeuristic(bool b) {m_mpHeuristic = b;}//!< Switches use of lower bound heuristic
 173         void setNumAddVariables(int i) {m_numAddVariables=i;}
 174         void setStrongConstraintViolation(double d) { m_strongConstraintViolation=d;}
 175         void setStrongVariableViolation(double d) { m_strongVariableViolation=d;}
 176
 177         //! If set to true, PORTA output is written in a file
 178         void setPortaFile(bool b) {m_porta = b;}
 179
 180         // Updating global constraint counter
 181         void updateAddedCCons(int n) {m_nCConsAdded += n;}
 182         void updateAddedKCons(int n) {m_nKConsAdded += n;}
 183
 184         // Returns global primal and dual bounds.
 185         double getPrimalBound() {return globalPrimalBound;}
 186         double getDualBound() {return globalDualBound;}
 187
 188         // Cut pools for connectivity and planarity
 189         //! Returns cut pool for connectivity
 190         ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *getCutConnPool() {return m_cutConnPool;}
 191         //! Returns cut pool for planarity
 192         ABA_STANDARDPOOL<ABA_CONSTRAINT, ABA_VARIABLE> *getCutKuraPool() {return m_cutKuraPool;}
 193
 194         //! Returns true if default cut pool is used. Otherwise, separate
 195         //! connectivity and Kuratowski pools are generated and used.
 196         bool &useDefaultCutPool() { return m_useDefaultCutPool;}
 197
 198 #ifdef OGDF_DEBUG
 199         bool m_solByHeuristic; //solution computed by heuristic or ILP
 200                 // Simple output function to print the given graph to the console.
 201         // Used for debugging only.
 202         void printGraph(const Graph &G);
 203 #endif
 204
 205         //! The name of the file that contains the standard, i.e., non-cut,
 206         //! constraints (may be deleted by ABACUS and shouldn't be stored twice)
 207         const char* getStdConstraintsFileName()
 208         {
 209                 return "StdConstraints.txt";
 210         }
 211
 212         int getNumInactiveVars() { return m_inactiveVariables.size();}
 213
 214 protected:
 215
 216         // Initializes constraints and variables and an initial dual bound.
 217         virtual void initializeOptimization();
 218
 219         // Function that is invoked at the end of the optimization
 220         virtual void terminateOptimization();
 221
 222         double heuristicInitialLowerBound();
 223
 224 private:
 225
 226         // Computes a dual bound for the optimal solution.
 227         // Tries to find as many edge-disjoint Kuratowski subdivisions as possible.
 228         // If k edge-disjoint groups of subdivisions are found, the upper bound can be
 229         // initialized with number of edges in underlying graph minus k.
 230         double heuristicInitialUpperBound();
 231
 232         // Is invoked by heuristicInitialUpperBound()
 233         void clusterConnection(cluster c, GraphCopy &GC, double &upperBound);
 234
 235         // Computes the graphtheoretical distances of edges incident to node \a u.
 236     void nodeDistances(node u, NodeArray<NodeArray<int> > &dist);
 237
 238
 239         // Parameters
 240         int m_nKuratowskiSupportGraphs;         // Maximal number of times the Kuratowski support graph is computed
 241         int m_nKuratowskiIterations;            // Maximal number of times BoyerMyrvold is invoked
 242         int m_nSubdivisions;                            // Maximal number of extracted Kuratowski subdivisions
 243         int m_nMaxVars;                                         // Max Number of variables
 244         int m_heuristicLevel;                           // Indicates if primal heuristic shall be used or not
 245         int m_nHeuristicRuns;                           // Counts how often the primal heuristic has been called
 246
 247         bool m_usePerturbation;                         // Indicates whether C-variables should be perturbated or not
 248         double m_branchingGap;                          // Modifies the branching behaviour
 249         double m_heuristicFractionalBound;
 250         int m_nHeuristicPermutationLists;       // The number of permutation lists used in the primal heuristic
 251         bool m_mpHeuristic;                 //!< Indicates if simple max planar subgraph heuristic
 252                                                                                 // should be used to derive lower bound if only root cluster exists
 253
 254         double m_kuratowskiBoundHigh;           // Upper bound for deterministic edge addition in computation of the Supportgraph
 255         double m_kuratowskiBoundLow;            // Lower bound for deterministic edge deletion in computation of the Supportgraph
 256
 257         int m_numAddVariables;                          // how many variables should i add maximally per pricing round?
 258         double m_strongConstraintViolation; // when do i consider a constraint strongly violated -> separate in first stage
 259         double m_strongVariableViolation;   // when do i consider a variable strongly violated (red.cost) -> separate in first stage
 260
 261         ABA_MASTER::OUTLEVEL m_out;             // Determines the output level of ABACUS
 262         ABA_STRING *m_maxCpuTime;                       // Time threshold for optimization
 263
 264
 265         // The basic objective function coefficient for connection edges.
 266         double m_epsilon;
 267         // If pertubation is used, this variable stores the largest occuring coeff,
 268         // i.e. the one closest to 0. Otherwise it corresponds to \a m_epsilon
 269         double m_largestConnectionCoeff;
 270
 271         // Counters for the number of added constraints
 272         int m_nCConsAdded;
 273         int m_nKConsAdded;
 274         int m_solvesLP;
 275         int m_varsInit;
 276         int m_varsAdded;
 277         int m_varsPotential;
 278         int m_varsMax;
 279         int m_varsCut;
 280         int m_varsKura;
 281         int m_varsPrice;
 282         int m_varsBranch;
 283         int m_activeRepairs;
 284         ArrayBuffer<int> m_repairStat;
 285         inline void clearActiveRepairs() {
 286                 if(m_activeRepairs) {
 287                         m_repairStat.push(m_activeRepairs);
 288                         m_activeRepairs = 0;
 289                 }
 290         }
 291
 292         double globalPrimalBound;
 293         double globalDualBound;
 294
 295         inline double getDoubleTime(const ABA_TIMER* act) {
 296         long tempo = act->centiSeconds()+100*act->seconds()+6000*act->minutes()+360000*act->hours();
 297         return  ((double) tempo)/ 100.0;
 298         }
 299
 300         //number of calls of the fast max planar subgraph heuristic
 301         const int m_fastHeuristicRuns;
 302
 303         //! Cut pools for connectivity and Kuratowski constraints
 304         ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE > *m_cutConnPool; //!< Connectivity Cuts
 305         ABA_STANDARDPOOL< ABA_CONSTRAINT, ABA_VARIABLE > *m_cutKuraPool; //!< Kuratowski Cuts
 306
 307         //! Defines if the ABACUS default cut pool or the separate Connectivity
 308         //! and Kuratowski constraint pools are used
 309         bool m_useDefaultCutPool;
 310
 311         //! Defines if only clustered planarity is checked, i.e.,
 312         //! all edges of the original graph need to be fixed to be
 313         //! part of the solution
 314         bool m_checkCPlanar;
 315
 316         //!
 317         double m_delta;
 318         double m_deltaCount;
 319         double nextConnectCoeff() { return (m_checkCPlanar ? -1 : -m_epsilon) + m_deltaCount--*m_delta; } // TODO-TESTING
 320         EdgeVar* createVariable(ListIterator<nodePair>& it) {
 321                 ++m_varsAdded;
 322                 EdgeVar* v = new EdgeVar(this, nextConnectCoeff(), EdgeVar::CONNECT, (*it).v1, (*it).v2);
 323                 v->printMe(Logger::slout());
 324                 m_inactiveVariables.del(it);
 325                 return v;
 326         }
 327         List<nodePair> m_inactiveVariables;
 328         void generateVariablesForFeasibility(const List<ChunkConnection*>& ccons, List<EdgeVar*>& connectVars);
 329
 330         bool goodVar(node a, node b);
 331
 332         //! If set to true, PORTA output is written in a file
 333         bool m_porta;
 334         //! writes coefficients of all orig and connect variables in constraint con into
 335         //! emptied list coeffs
 336         void getCoefficients(ABA_CONSTRAINT* con,  const List<EdgeVar *> & orig,
 337                 const List<EdgeVar* > & connect, List<double> & coeffs);
 338 };
 339
 340 }//end namespace
 341
 342 #endif