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

  Nauty has this -
*   Permission 
*   is hereby given for use and/or distribution with the exception of        *
*   sale for profit or application with nontrivial military significance.    *
  so you can use it internally even if you are a company.
 */
#ifndef CBC_SYMMETRY_HPP
#define CBC_SYMMETRY_HPP
extern "C" {
#include "nauty.h"
#include "nausparse.h"
#ifdef NTY_TRACES
#include "traces.h"
#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 10
#endif
class CbcNauty;

#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() const;
  void fillOrbits();
  int orbitalFixing(OsiSolverInterface *solver);
  inline int *whichOrbit()
  {
    return numberUsefulOrbits_ ? whichOrbit_ : NULL;
  }
  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;
  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);

private:
  mutable std::vector< Node > node_info_;
  mutable CbcNauty *nauty_info_;
  int numberColumns_;
  int numberUsefulOrbits_;
  int numberUsefulObjects_;
  int *whichOrbit_;
};

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);

  // 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_;
};

#endif

/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
*/