00001 #ifndef _CglClique_h_
00002 #define _CglClique_h_
00003
00004 #include "CglCutGenerator.hpp"
00005
00006
00007
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 CglFakeClique : public CglClique {
00257
00258 public:
00260 CglFakeClique(const CglFakeClique& rhs);
00262 virtual CglCutGenerator * clone() const;
00263
00265 CglFakeClique& operator=(const CglFakeClique& rhs);
00266
00267 virtual void
00268 generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
00269 const CglTreeInfo info = CglTreeInfo()) const;
00270
00290 CglFakeClique(OsiSolverInterface * solver=NULL,bool setPacking = false);
00292 virtual ~CglFakeClique();
00294 void assignSolver(OsiSolverInterface * fakeSolver);
00295 protected:
00297 mutable OsiSolverInterface * fakeSolver_;
00298 };
00299
00300 #endif