- Main Page
- Namespaces
- Classes
- Files
- Directories

- Search for |

- File List
- File Members

# CglClique.hpp

Go to the documentation of this file.

    00001 // $Id: CglClique.hpp 933 2011-01-04 23:16:49Z lou $
    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