coin-Cgl
|
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 00011 friend void CglCliqueUnitTest(const OsiSolverInterface * siP, 00012 const std::string mpdDir ); 00013 public: 00015 CglClique(const CglClique& rhs); 00017 virtual CglCutGenerator * clone() const; 00018 00020 CglClique& operator=(const CglClique& rhs); 00021 00022 public: 00023 00024 virtual void 00025 generateCuts(const OsiSolverInterface& si, OsiCuts & cs, 00026 const CglTreeInfo info = CglTreeInfo()) const; 00027 00048 CglClique(bool setPacking = false, bool justOriginalRows = false); 00050 virtual ~CglClique() {} 00052 virtual std::string generateCpp( FILE * fp); 00053 00054 void considerRows(const int numRows, const int* rowInd); 00055 00056 public: 00059 enum scl_next_node_method { 00060 SCL_MIN_DEGREE, 00061 SCL_MAX_DEGREE, 00062 SCL_MAX_XJ_MAX_DEG 00063 }; 00064 00065 void setStarCliqueNextNodeMethod(scl_next_node_method method) { 00066 scl_next_node_rule = method; 00067 } 00068 00069 void setStarCliqueCandidateLengthThreshold(int maxlen) { 00070 scl_candidate_length_threshold = maxlen; 00071 } 00072 void setRowCliqueCandidateLengthThreshold(int maxlen) { 00073 rcl_candidate_length_threshold = maxlen; 00074 } 00075 00076 void setStarCliqueReport(bool yesno = true) { scl_report_result = yesno; } 00077 void setRowCliqueReport(bool yesno = true) { rcl_report_result = yesno; } 00078 00079 void setDoStarClique(bool yesno = true) { do_star_clique = yesno; } 00080 void setDoRowClique(bool yesno = true) { do_row_clique = yesno; } 00081 00082 void setMinViolation(double minviol) { petol = minviol; } 00083 double getMinViolation() const { return petol; } 00084 00085 private: 00086 00087 struct frac_graph ; 00088 friend struct frac_graph ; 00089 00092 struct fnode { 00094 int *nbrs; 00097 double *edgecosts; 00099 int degree; 00101 double val; 00102 }; 00103 00106 struct frac_graph { 00108 int nodenum; 00110 int edgenum; 00112 double density; 00113 int min_deg_node; 00114 int min_degree; 00115 int max_deg_node; 00116 int max_degree; 00118 fnode *nodes; 00121 int *all_nbr; 00123 double *all_edgecost; 00124 00125 frac_graph() : 00126 nodenum(0), edgenum(0), density(0), 00127 min_deg_node(0), min_degree(0), max_deg_node(0), max_degree(0), 00128 nodes(0), all_nbr(0), all_edgecost(0) {} 00129 }; 00130 00131 protected: 00134 bool setPacking_; 00136 bool justOriginalRows_; 00138 mutable int sp_numrows; 00139 mutable int* sp_orig_row_ind; 00140 mutable int sp_numcols; 00141 mutable int* sp_orig_col_ind; 00142 mutable double* sp_colsol; 00143 mutable int* sp_col_start; 00144 mutable int* sp_col_ind; 00145 mutable int* sp_row_start; 00146 mutable int* sp_row_ind; 00147 00149 mutable frac_graph fgraph; 00151 mutable bool* node_node; 00152 00154 mutable double petol; 00155 00161 bool do_row_clique; 00163 bool do_star_clique; 00164 00166 scl_next_node_method scl_next_node_rule; 00171 int scl_candidate_length_threshold; 00173 bool scl_report_result; 00174 00179 int rcl_candidate_length_threshold; 00181 bool rcl_report_result; 00189 mutable const int* cl_perm_indices; 00191 mutable int cl_perm_length; 00192 00195 mutable int* cl_indices; 00197 mutable int cl_length; 00198 00202 mutable int* cl_del_indices; 00204 mutable int cl_del_length; 00205 00208 private: 00211 void selectFractionalBinaries(const OsiSolverInterface& si) const; 00214 void selectFractionals(const OsiSolverInterface& si) const; 00216 void selectRowCliques(const OsiSolverInterface& si,int numOriginalRows) const; 00218 void createSetPackingSubMatrix(const OsiSolverInterface& si) const; 00220 void createFractionalGraph() const; 00222 int createNodeNode() const; 00224 void deleteSetPackingSubMatrix() const; 00226 void deleteFractionalGraph() const; 00228 void find_scl(OsiCuts& cs) const; 00230 void find_rcl(OsiCuts& cs) const; 00232 int scl_choose_next_node(const int current_nodenum, 00233 const int *current_indices, 00234 const int *current_degrees, 00235 const double *current_values) const; 00237 void scl_delete_node(const int del_ind, int& current_nodenum, 00238 int *current_indices, int *current_degrees, 00239 double *current_values) const; 00241 int enumerate_maximal_cliques(int& pos, bool* scl_label, OsiCuts& cs) const; 00243 int greedy_maximal_clique(OsiCuts& cs) const; 00245 void recordClique(const int len, int* indices, OsiCuts& cs) const; 00246 }; 00247 //############################################################################# 00253 void CglCliqueUnitTest(const OsiSolverInterface * siP, 00254 const std::string mpdDir); 00256 class CglProbing; 00257 class CglFakeClique : public CglClique { 00258 00259 public: 00261 CglFakeClique(const CglFakeClique& rhs); 00263 virtual CglCutGenerator * clone() const; 00264 00266 CglFakeClique& operator=(const CglFakeClique& rhs); 00267 00268 virtual void 00269 generateCuts(const OsiSolverInterface& si, OsiCuts & cs, 00270 const CglTreeInfo info = CglTreeInfo()) const; 00271 00291 CglFakeClique(OsiSolverInterface * solver=NULL,bool setPacking = false); 00293 virtual ~CglFakeClique(); 00295 void assignSolver(OsiSolverInterface * fakeSolver); 00296 protected: 00298 mutable OsiSolverInterface * fakeSolver_; 00300 mutable CglProbing * probing_; 00301 }; 00302 00303 #endif