Cgl trunk
CglClique.hpp
Go to the documentation of this file.
00001 // $Id$
00002 // Copyright (C) 2000, International Business Machines
00003 // Corporation and others.  All Rights Reserved.
00004 // This code is licensed under the terms of the Eclipse Public License (EPL).
00005 
00006 #ifndef _CglClique_h_
00007 #define _CglClique_h_
00008 
00009 #include "CglCutGenerator.hpp"
00010 
00011 //class OsiCuts;
00012 //class OsiSolverInterface;
00013 
00014 class CglClique : public CglCutGenerator {
00015 
00016     friend void CglCliqueUnitTest(const OsiSolverInterface * siP,
00017                                   const std::string mpdDir );
00018 public:
00020     CglClique(const CglClique& rhs);
00022     virtual CglCutGenerator * clone() const;
00023 
00025     CglClique& operator=(const CglClique& rhs);
00026    
00027 public:
00028     
00029     virtual void
00030     generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
00031                  const CglTreeInfo info = CglTreeInfo()) const;
00032    
00053     CglClique(bool setPacking = false, bool justOriginalRows = false);
00055     virtual ~CglClique() {}
00057     virtual std::string generateCpp( FILE * fp);
00058 
00059     void considerRows(const int numRows, const int* rowInd);
00060 
00061 public:
00064     enum scl_next_node_method {
00065         SCL_MIN_DEGREE,
00066         SCL_MAX_DEGREE,
00067         SCL_MAX_XJ_MAX_DEG
00068     };
00069 
00070     void setStarCliqueNextNodeMethod(scl_next_node_method method) {
00071         scl_next_node_rule = method;
00072     }
00073 
00074     void setStarCliqueCandidateLengthThreshold(int maxlen) {
00075         scl_candidate_length_threshold = maxlen;
00076     }
00077     void setRowCliqueCandidateLengthThreshold(int maxlen) {
00078         rcl_candidate_length_threshold = maxlen;
00079     }
00080 
00081     void setStarCliqueReport(bool yesno = true) { scl_report_result = yesno; }
00082     void setRowCliqueReport(bool yesno = true) { rcl_report_result = yesno; }
00083 
00084     void setDoStarClique(bool yesno = true) { do_star_clique = yesno; }
00085     void setDoRowClique(bool yesno = true) { do_row_clique = yesno; }
00086 
00087     void setMinViolation(double minviol) { petol = minviol; }
00088     double getMinViolation() const { return petol; }
00089 
00090 private:
00091 
00092     struct frac_graph ;
00093     friend struct frac_graph ;
00094 
00097     struct fnode {
00099         int          *nbrs;
00102         double       *edgecosts;
00104         int           degree;
00106         double        val;
00107     };
00108 
00111     struct frac_graph {
00113         int    nodenum;
00115         int    edgenum;
00117         double density;
00118         int    min_deg_node;
00119         int    min_degree;
00120         int    max_deg_node;
00121         int    max_degree;
00123         fnode  *nodes;
00126         int    *all_nbr;
00128         double *all_edgecost;
00129 
00130         frac_graph() :
00131             nodenum(0), edgenum(0), density(0),
00132             min_deg_node(0), min_degree(0), max_deg_node(0), max_degree(0),
00133             nodes(0), all_nbr(0), all_edgecost(0) {}
00134     };
00135 
00136 protected:
00139     bool setPacking_;
00141     bool justOriginalRows_;
00143     mutable int sp_numrows;
00144     mutable int* sp_orig_row_ind;
00145     mutable int sp_numcols;
00146     mutable int* sp_orig_col_ind;
00147     mutable double* sp_colsol;
00148     mutable int* sp_col_start;
00149     mutable int* sp_col_ind;
00150     mutable int* sp_row_start;
00151     mutable int* sp_row_ind;
00152 
00154     mutable frac_graph fgraph;
00156     mutable bool* node_node;
00157 
00159     mutable double petol;
00160 
00166     bool do_row_clique;
00168     bool do_star_clique;
00169 
00171     scl_next_node_method scl_next_node_rule;
00176     int scl_candidate_length_threshold;
00178     bool scl_report_result;
00179 
00184     int rcl_candidate_length_threshold;
00186     bool rcl_report_result;
00194     mutable const int* cl_perm_indices;
00196     mutable int cl_perm_length;
00197 
00200     mutable int* cl_indices;
00202     mutable int cl_length;
00203 
00207     mutable int* cl_del_indices;
00209     mutable int cl_del_length;
00210 
00213 private:
00216     void selectFractionalBinaries(const OsiSolverInterface& si) const;
00219     void selectFractionals(const OsiSolverInterface& si) const;
00221     void selectRowCliques(const OsiSolverInterface& si,int numOriginalRows) const;
00223     void createSetPackingSubMatrix(const OsiSolverInterface& si) const;
00225     void createFractionalGraph() const;
00227     int createNodeNode() const;
00229     void deleteSetPackingSubMatrix() const;
00231     void deleteFractionalGraph() const;
00233     void find_scl(OsiCuts& cs) const;
00235     void find_rcl(OsiCuts& cs) const;
00237     int scl_choose_next_node(const int current_nodenum,
00238                              const int *current_indices,
00239                              const int *current_degrees,
00240                              const double *current_values) const;
00242     void scl_delete_node(const int del_ind, int& current_nodenum,
00243                          int *current_indices, int *current_degrees,
00244                          double *current_values) const;
00246     int enumerate_maximal_cliques(int& pos, bool* scl_label, OsiCuts& cs) const;
00248     int greedy_maximal_clique(OsiCuts& cs) const;
00250     void recordClique(const int len, int* indices, OsiCuts& cs) const;
00251 };
00252 //#############################################################################
00258 void CglCliqueUnitTest(const OsiSolverInterface * siP,
00259                        const std::string mpdDir);
00261 class CglProbing;
00262 class CglFakeClique : public CglClique {
00263   
00264 public:
00266   CglFakeClique(const CglFakeClique& rhs);
00268   virtual CglCutGenerator * clone() const;
00269   
00271   CglFakeClique& operator=(const CglFakeClique& rhs);
00272   
00273   virtual void
00274   generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
00275                const CglTreeInfo info = CglTreeInfo()) const;
00276   
00296   CglFakeClique(OsiSolverInterface * solver=NULL,bool setPacking = false);
00298   virtual ~CglFakeClique();
00300   void assignSolver(OsiSolverInterface * fakeSolver);
00301 protected:
00303   mutable OsiSolverInterface * fakeSolver_;
00305   mutable CglProbing * probing_;
00306 };
00307 
00308 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines