/home/coin/SVN-release/Cbc-1.1.1/Cgl/src/CglClique/CglClique.hpp

Go to the documentation of this file.
00001 #ifndef _CglClique_h_
00002 #define _CglClique_h_
00003 
00004 #include "CglCutGenerator.hpp"
00005 
00006 class OsiCuts;
00007 class OsiSolverInterface;
00008 
00009 class CglClique : public CglCutGenerator {
00010     friend void CglCliqueUnitTest(const OsiSolverInterface * siP,
00011                                   const std::string mpdDir );
00012 private:
00014     CglClique(const CglClique& rhs);
00016     virtual CglCutGenerator * clone() const;
00017 
00019     CglClique& operator=(const CglClique& rhs);
00020    
00021 public:
00022     
00023     virtual void
00024     generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
00025                  const CglTreeInfo info = CglTreeInfo()) const;
00026    
00047     CglClique(bool setPacking = false, bool justOriginalRows = false);
00049     virtual ~CglClique() {}
00051     virtual std::string generateCpp( FILE * fp);
00052 
00053     void considerRows(const int numRows, const int* rowInd);
00054 
00055 public:
00058     enum scl_next_node_method {
00059         SCL_MIN_DEGREE,
00060         SCL_MAX_DEGREE,
00061         SCL_MAX_XJ_MAX_DEG
00062     };
00063 
00064     void setStarCliqueNextNodeMethod(scl_next_node_method method) {
00065         scl_next_node_rule = method;
00066     }
00067 
00068     void setStarCliqueCandidateLengthThreshold(int maxlen) {
00069         scl_candidate_length_threshold = maxlen;
00070     }
00071     void setRowCliqueCandidateLengthThreshold(int maxlen) {
00072         rcl_candidate_length_threshold = maxlen;
00073     }
00074 
00075     void setStarCliqueReport(bool yesno = true) { scl_report_result = yesno; }
00076     void setRowCliqueReport(bool yesno = true) { rcl_report_result = yesno; }
00077 
00078     void setDoStarClique(bool yesno = true) { do_star_clique = yesno; }
00079     void setDoRowClique(bool yesno = true) { do_row_clique = yesno; }
00080 
00081     void setMinViolation(double minviol) { petol = minviol; }
00082     double getMinViolation() const { return petol; }
00083 
00084 private:
00085 
00086     struct frac_graph ;
00087     friend struct frac_graph ;
00088 
00091     struct fnode {
00093         int          *nbrs;
00096         double       *edgecosts;
00098         int           degree;
00100         double        val;
00101     };
00102 
00105     struct frac_graph {
00107         int    nodenum;
00109         int    edgenum;
00111         double density;
00112         int    min_deg_node;
00113         int    min_degree;
00114         int    max_deg_node;
00115         int    max_degree;
00117         fnode  *nodes;
00120         int    *all_nbr;
00122         double *all_edgecost;
00123 
00124         frac_graph() :
00125             nodenum(0), edgenum(0), density(0),
00126             min_deg_node(0), min_degree(0), max_deg_node(0), max_degree(0),
00127             nodes(0), all_nbr(0), all_edgecost(0) {}
00128     };
00129 
00130 private:
00133     bool setPacking_;
00135     bool justOriginalRows_;
00137     mutable int sp_numrows;
00138     mutable int* sp_orig_row_ind;
00139     mutable int sp_numcols;
00140     mutable int* sp_orig_col_ind;
00141     mutable double* sp_colsol;
00142     mutable int* sp_col_start;
00143     mutable int* sp_col_ind;
00144     mutable int* sp_row_start;
00145     mutable int* sp_row_ind;
00146 
00148     mutable frac_graph fgraph;
00150     mutable bool* node_node;
00151 
00153     mutable double petol;
00154 
00160     bool do_row_clique;
00162     bool do_star_clique;
00163 
00165     scl_next_node_method scl_next_node_rule;
00170     int scl_candidate_length_threshold;
00172     bool scl_report_result;
00173 
00178     int rcl_candidate_length_threshold;
00180     bool rcl_report_result;
00188     mutable const int* cl_perm_indices;
00190     mutable int cl_perm_length;
00191 
00194     mutable int* cl_indices;
00196     mutable int cl_length;
00197 
00201     mutable int* cl_del_indices;
00203     mutable int cl_del_length;
00204 
00207 private:
00210     void selectFractionalBinaries(const OsiSolverInterface& si) const;
00213     void selectFractionals(const OsiSolverInterface& si) const;
00215     void selectRowCliques(const OsiSolverInterface& si,int numOriginalRows) const;
00217     void createSetPackingSubMatrix(const OsiSolverInterface& si) const;
00219     void createFractionalGraph() const;
00221     int createNodeNode() const;
00223     void deleteSetPackingSubMatrix() const;
00225     void deleteFractionalGraph() const;
00227     void find_scl(OsiCuts& cs) const;
00229     void find_rcl(OsiCuts& cs) const;
00231     int scl_choose_next_node(const int current_nodenum,
00232                              const int *current_indices,
00233                              const int *current_degrees,
00234                              const double *current_values) const;
00236     void scl_delete_node(const int del_ind, int& current_nodenum,
00237                          int *current_indices, int *current_degrees,
00238                          double *current_values) const;
00240     int enumerate_maximal_cliques(int& pos, bool* scl_label, OsiCuts& cs) const;
00242     int greedy_maximal_clique(OsiCuts& cs) const;
00244     void recordClique(const int len, int* indices, OsiCuts& cs) const;
00245 };
00246 
00247 #endif

Generated on Thu May 15 21:59:04 2008 by  doxygen 1.4.7