CbcSymmetry.hpp

Go to the documentation of this file.

/* $Id: CbcSymmetry.hpp 1033 2013-12-14 19:34:28Z pbelotti $
 *
 * Name:    Hacked from CouenneProblem.hpp
 * Author:  Pietro Belotti, Lehigh University
 *          Andreas Waechter, IBM
 * Purpose: define the class CouenneProblem
 *
 * (C) Carnegie-Mellon University, 2006-11.
 * This file is licensed under the Eclipse Public License (EPL)
 */
/*
  If this is much used then we could improve build experience
  Download nauty - say to /disk/nauty25r9
  In that directory ./configure --enable-tls --enable-wordsize=32
  make
  copy nauty.a to libnauty.a
 
  In Cbc's configure 
  add -DCOIN_HAS_NTY to CXXDEFS
  add -I/disk/nauty25r9 to CXXDEFS or ADD_CXXFLAGS
  add -L/disk/nauty25r9 -lnauty to LDFLAGS
 
  If you wish to use Traces rather than nauty then add -DNTY_TRACES
 
  To use it is -orbit on
 
 */
#ifndef CBC_SYMMETRY_HPP
#define CBC_SYMMETRY_HPP
 
#include "CbcConfig.h"
 
#ifdef COIN_HAS_NTY
extern "C" {
#include "nauty/nauty.h"
#include "nauty/nausparse.h"
#ifdef NTY_TRACES
#include "nauty/traces.h"
#endif
}
#endif
 
#include <vector>
#include <map>
#include <string.h>
 
#include "CbcModel.hpp"
 
class OsiObject;
// when to give up (depth since last success)
#ifndef NTY_BAD_DEPTH
#define NTY_BAD_DEPTH 4
#endif
class CbcNauty;
typedef struct {
  int numberInPerm;
  int numberPerms;
  int * orbits;
} cbc_permute;
 
#define COUENNE_HACKED_EPS 1.e-07
#define COUENNE_HACKED_EPS_SYMM 1e-8
#define COUENNE_HACKED_EXPRGROUP 8
 
class CbcSymmetry {
  class Node {
    int index;
    double coeff;
    double lb;
    double ub;
    int color;
    int code;
    int sign;
 
  public:
    void node(int, double, double, double, int, int);
    inline void color_vertex(register int k) { color = k; }
    inline int get_index() const { return index; }
    inline double get_coeff() const { return coeff; }
    inline double get_lb() const { return lb; }
    inline double get_ub() const { return ub; }
    inline int get_color() const { return color; }
    inline int get_code() const { return code; }
    inline int get_sign() const { return sign; }
    inline void bounds(register double a, register double b)
    {
      lb = a;
      ub = b;
    }
  };
 
  struct myclass0 {
    inline bool operator()(register const Node &a, register const Node &b)
    {
 
      return ((a.get_code() < b.get_code()) || ((a.get_code() == b.get_code() && ((a.get_coeff() < b.get_coeff() - COUENNE_HACKED_EPS_SYMM) || ((fabs(a.get_coeff() - b.get_coeff()) < COUENNE_HACKED_EPS_SYMM) && ((a.get_lb() < b.get_lb() - COUENNE_HACKED_EPS_SYMM) || ((fabs(a.get_lb() - b.get_lb()) < COUENNE_HACKED_EPS_SYMM) && ((a.get_ub() < b.get_ub() - COUENNE_HACKED_EPS_SYMM) || ((fabs(a.get_ub() - b.get_ub()) < COUENNE_HACKED_EPS_SYMM) && ((a.get_index() < b.get_index())))))))))));
    }
  };
 
  struct myclass {
    inline bool operator()(register const Node &a, register const Node &b)
    {
      return (a.get_index() < b.get_index());
    }
  };
 
  struct less_than_str {
    inline bool operator()(register const char *a, register const char *b) const
    {
      return strcmp(a, b) < 0;
    }
  };
 
public:
  CbcSymmetry();
 
  CbcSymmetry(const CbcSymmetry &);
 
  CbcSymmetry &operator=(const CbcSymmetry &rhs);
 
  ~CbcSymmetry();
 
  // Symmetry Info
 
  std::vector< int > *Find_Orbit(int) const;
 
  myclass0 node_sort;
  myclass index_sort;
 
  void Compute_Symmetry() const;
  int statsOrbits(CbcModel *model, int type) const;
  //double timeNauty () const;
  void Print_Orbits(int type=0) const;
  void fillOrbits();
  int orbitalFixing(OsiSolverInterface *solver);
  int orbitalFixing2(OsiSolverInterface *solver);
  inline int *whichOrbit()
  {
    return numberUsefulOrbits_ ? whichOrbit_ : NULL;
  }
  inline int *fixedToZero() const
  {
    return whichOrbit_+4*numberColumns_;
  }
  inline int numberUsefulOrbits() const
  {
    return numberUsefulOrbits_;
  }
  inline int numberUsefulObjects() const
  {
    return numberUsefulObjects_;
  }
  int largestOrbit(const double *lower, const double *upper) const;
  void ChangeBounds(const double *lower, const double *upper,
    int numberColumns, bool justFixedAtOne) const;
  int changeBounds(int kColumn, double * saveLower,
                    double * saveUpper,
                    OsiSolverInterface * solver,int mode) const;
  int changeBounds(double *saveLower, double *saveUpper,
                   OsiSolverInterface * solver) const;
  int changeBounds2(double *saveLower, double *saveUpper,
                   OsiSolverInterface * solver) const;
  int fixSome(int iColumn, double *columnLower, double *columnUpper) const;
  int worthBranching(const double *saveLower, const double *saveUpper,
                     int iColumn, int & numberCouldFix) const;
  void fixSuccess(int nFixed);
  void adjustStats(const CbcSymmetry * other);
  inline int numberColumns() const
  { return numberColumns_;}
  inline bool compare(register Node &a, register Node &b) const;
  CbcNauty *getNtyInfo() { return nauty_info_; }
 
  // bool node_sort (  Node  a, Node  b);
  // bool index_sort (  Node  a, Node  b);
 
  void setupSymmetry(CbcModel * model);
 
  void addPermutation(cbc_permute permutation);
  inline int numberPermutations() const
  { return numberPermutations_;}
  inline int * permutation(int which) const
  { return permutations_[which].orbits;}
  inline int numberInPermutation(int which) const
  { return permutations_[which].numberInPerm;}
  inline void incrementNautyBranches(int n)
  { nautyOtherBranches_ += n;}
  inline void incrementBranchSucceeded()
  { nautyBranchSucceeded_ ++;}
private:
  mutable std::vector< Node > node_info_;
  mutable CbcNauty *nauty_info_;
  int numberColumns_;
  int numberUsefulOrbits_;
  int numberUsefulObjects_;
  int numberPermutations_;
  cbc_permute * permutations_;
  int *whichOrbit_;
  int stats_[5];
  double nautyTime_;
  double nautyFixes_;
  mutable double nautyOtherBranches_;
  mutable int nautyBranchCalls_;
  mutable int lastNautyBranchSucceeded_;
  int nautyBranchSucceeded_;
  mutable int nautyFixCalls_;
  mutable int lastNautyFixSucceeded_;
  int nautyFixSucceeded_;
};
 
class CbcNauty {
 
public:
  enum VarStatus { FIX_AT_ZERO,
    FIX_AT_ONE,
    FREE };
 
private:
  CbcNauty();
 
public:
  CbcNauty(int n, const size_t *v, const int *d, const int *e);
 
  CbcNauty(const CbcNauty &);
 
  CbcNauty &operator=(const CbcNauty &rhs);
 
  ~CbcNauty();
 
  void addElement(int ix, int jx);
  void clearPartitions();
  void computeAuto();
  void deleteElement(int ix, int jx);
  void color_node(int ix, int color) { vstat_[ix] = color; }
  void insertRHS(int rhs, int cons) { constr_rhs.insert(std::pair< int, int >(rhs, cons)); }
 
  double getGroupSize() const;
  //int getNautyCalls() const { return nautyCalls_; }
  //double getNautyTime() const { return nautyTime_; }
 
  int getN() const { return n_; }
 
  int getNumGenerators() const;
  int getNumOrbits() const;
 
  std::vector< std::vector< int > > *getOrbits() const;
 
  void getVstat(double *v, int nv);
  inline bool isSparse() const
  {
    return GSparse_ != NULL;
  }
  inline int errorStatus() const
#ifndef NTY_TRACES
  {
    return stats_->errstatus;
  }
#else
  {
    return 0;
  }
#endif
  inline optionblk *options() const
  {
    return options_;
  }
  //  bool isAllFixOneOrbit(const std::vector<int> &orbit) const;
  // bool isAllFreeOrbit(const std::vector<int> &orbit) const;
  //bool isAutoComputed() const { return autoComputed_; }
  //bool isConstraintOrbit(const std::vector<int> &orbit) const;
  //bool isMixedFreeZeroOrbit(const std::vector<int> &orbit) const;
  //void makeFree(int ix) { vstat_[ix] = FREE; }
 
  void setWriteAutoms(const std::string &afilename);
  void unsetWriteAutoms();
 
private:
  // The base nauty stuff
  graph *G_;
  sparsegraph *GSparse_;
  int *lab_;
  int *ptn_;
  set *active_;
  int *orbits_;
#ifndef NTY_TRACES
  optionblk *options_;
  statsblk *stats_;
#else
  TracesOptions *options_;
  TracesStats *stats_;
#endif
  setword *workspace_;
  int worksize_;
  int m_;
  int n_;
  size_t nel_;
  graph *canonG_;
 
  bool autoComputed_;
 
  int *vstat_;
 
  //static int nautyCalls_;
  //static double nautyTime_;
 
  std::multimap< int, int > constr_rhs;
  std::multimap< int, int >::iterator it;
 
  std::pair< std::multimap< int, int >::iterator,
    std::multimap< int, int >::iterator >
    ret;
 
  // File pointer for automorphism group
  FILE *afp_;
};
 
class CbcOrbitalBranchingObject : public CbcBranchingObject {
 
public:
  // Default Constructor
  CbcOrbitalBranchingObject();
 
  // Useful constructor
  CbcOrbitalBranchingObject(CbcModel *model, int column,
    int way,
    int numberExtra, const int *extraToZero);
  // Useful constructor (uses stored list)
  CbcOrbitalBranchingObject(CbcModel *model, int column, int nFixed);
 
  // Copy constructor
  CbcOrbitalBranchingObject(const CbcOrbitalBranchingObject &);
 
  // Assignment operator
  CbcOrbitalBranchingObject &operator=(const CbcOrbitalBranchingObject &rhs);
 
  virtual CbcBranchingObject *clone() const;
 
  // Destructor
  virtual ~CbcOrbitalBranchingObject();
 
  using CbcBranchingObject::branch;
  virtual double branch();
  virtual void fix(OsiSolverInterface *solver,
    double *lower, double *upper,
    int branchState) const;
 
  virtual void previousBranch()
  {
    CbcBranchingObject::previousBranch();
  }
 
  using CbcBranchingObject::print;
  virtual void print();
 
  virtual CbcBranchObjType type() const
  {
    return SoSBranchObj;
  }
 
  virtual int compareOriginalObject(const CbcBranchingObject *brObj) const;
 
  virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap = false);
 
private:
  int column_;
  int numberOther_;
  int numberExtra_;
  int *fixToZero_;
};
//#define PRINT_CBCAUTO
#endif