Cgl trunk
|
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