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