- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/Alps-1.2.1/Cgl/src/CglClique/CglClique.hpp

Go to the documentation of this file.

    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