CglClique.hpp

Go to the documentation of this file.

// $Id$
// Copyright (C) 2000, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
 
#ifndef _CglClique_h_
#define _CglClique_h_
 
#include "CglCutGenerator.hpp"
 
//class OsiCuts;
//class OsiSolverInterface;
 
class CglClique : public CglCutGenerator {
 
    friend void CglCliqueUnitTest(const OsiSolverInterface * siP,
                                  const std::string mpdDir );
public:
    CglClique(const CglClique& rhs);
    virtual CglCutGenerator * clone() const;
 
    CglClique& operator=(const CglClique& rhs);
   
public:
    
    virtual void
    generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
                 const CglTreeInfo info = CglTreeInfo());
   
    CglClique(bool setPacking = false, bool justOriginalRows = false);
    virtual ~CglClique() {}
    virtual std::string generateCpp( FILE * fp);
 
    void considerRows(const int numRows, const int* rowInd);
 
public:
    enum scl_next_node_method {
        SCL_MIN_DEGREE,
        SCL_MAX_DEGREE,
        SCL_MAX_XJ_MAX_DEG
    };
 
    void setStarCliqueNextNodeMethod(scl_next_node_method method) {
        scl_next_node_rule = method;
    }
 
    void setStarCliqueCandidateLengthThreshold(int maxlen) {
        scl_candidate_length_threshold = maxlen;
    }
    void setRowCliqueCandidateLengthThreshold(int maxlen) {
        rcl_candidate_length_threshold = maxlen;
    }
 
    void setStarCliqueReport(bool yesno = true) { scl_report_result = yesno; }
    void setRowCliqueReport(bool yesno = true) { rcl_report_result = yesno; }
 
    void setDoStarClique(bool yesno = true) { do_star_clique = yesno; }
    void setDoRowClique(bool yesno = true) { do_row_clique = yesno; }
 
    void setMinViolation(double minviol) { petol = minviol; }
    double getMinViolation() const { return petol; }
    inline void setMaxNumber(int value) { maxNumber_ = value; }
 
private:
 
    struct frac_graph ;
    friend struct frac_graph ;
 
    struct fnode {
        int          *nbrs;
        double       *edgecosts;
        int           degree;
        double        val;
    };
 
    struct frac_graph {
        int    nodenum;
        int    edgenum;
        double density;
        int    min_deg_node;
        int    min_degree;
        int    max_deg_node;
        int    max_degree;
        fnode  *nodes;
        int    *all_nbr;
        double *all_edgecost;
 
        frac_graph() :
            nodenum(0), edgenum(0), density(0),
            min_deg_node(0), min_degree(0), max_deg_node(0), max_degree(0),
            nodes(0), all_nbr(0), all_edgecost(0) {}
    };
 
protected:
    bool setPacking_;
    bool justOriginalRows_;
    int sp_numrows;
    int* sp_orig_row_ind;
    int sp_numcols;
    int* sp_orig_col_ind;
    double* sp_colsol;
    int* sp_col_start;
    int* sp_col_ind;
    int* sp_row_start;
    int* sp_row_ind;
 
    frac_graph fgraph;
    bool* node_node;
 
    double petol;
    int maxNumber_; 
 
    bool do_row_clique;
    bool do_star_clique;
 
    scl_next_node_method scl_next_node_rule;
    int scl_candidate_length_threshold;
    bool scl_report_result;
 
    int rcl_candidate_length_threshold;
    bool rcl_report_result;
    const int* cl_perm_indices;
    int cl_perm_length;
 
    int* cl_indices;
    int cl_length;
 
    int* cl_del_indices;
    int cl_del_length;
 
private:
    void selectFractionalBinaries(const OsiSolverInterface& si);
    void selectFractionals(const OsiSolverInterface& si);
    void selectRowCliques(const OsiSolverInterface& si,int numOriginalRows);
    void createSetPackingSubMatrix(const OsiSolverInterface& si);
    void createFractionalGraph();
    int createNodeNode();
    void deleteSetPackingSubMatrix();
    void deleteFractionalGraph();
    void find_scl(OsiCuts& cs);
    void find_rcl(OsiCuts& cs);
    int scl_choose_next_node(const int current_nodenum,
                             const int *current_indices,
                             const int *current_degrees,
                             const double *current_values);
    void scl_delete_node(const int del_ind, int& current_nodenum,
                         int *current_indices, int *current_degrees,
                         double *current_values);
    int enumerate_maximal_cliques(int& pos, bool* scl_label, OsiCuts& cs);
    int greedy_maximal_clique(OsiCuts& cs);
    void recordClique(const int len, int* indices, OsiCuts& cs);
};
//#############################################################################
void CglCliqueUnitTest(const OsiSolverInterface * siP,
                       const std::string mpdDir);
class CglProbing;
class CglFakeClique : public CglClique {
  
public:
  CglFakeClique(const CglFakeClique& rhs);
  virtual CglCutGenerator * clone() const;
  
  CglFakeClique& operator=(const CglFakeClique& rhs);
  
  virtual void
  generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
               const CglTreeInfo info = CglTreeInfo());
  
  CglFakeClique(OsiSolverInterface * solver=NULL,bool setPacking = false);
  virtual ~CglFakeClique();
  void assignSolver(OsiSolverInterface * fakeSolver);
protected:
  OsiSolverInterface * fakeSolver_;
  CglProbing * probing_;
};
 
#endif