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