CglClique.hpp

Go to the documentation of this file.

// $Id: CglClique.hpp 1119 2013-04-06 20:24:18Z stefan $
// 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; }

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;

    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