Cbc  2.9.8
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
CbcSymmetry.hpp
Go to the documentation of this file.
1 /* $Id: CbcSymmetry.hpp 1033 2013-12-14 19:34:28Z pbelotti $
2  *
3  * Name: Hacked from CouenneProblem.hpp
4  * Author: Pietro Belotti, Lehigh University
5  * Andreas Waechter, IBM
6  * Purpose: define the class CouenneProblem
7  *
8  * (C) Carnegie-Mellon University, 2006-11.
9  * This file is licensed under the Eclipse Public License (EPL)
10  */
11 /*
12  If this is much used then we could improve build experience
13  Download nauty - say to /disk/nauty25r9
14  In that directory ./configure --enable-tls --enable-wordsize=32
15  make
16  copy nauty.a to libnauty.a
17 
18  In Cbc's configure
19  add -DCOIN_HAS_NTY to CXXDEFS
20  add -I/disk/nauty25r9 to CXXDEFS or ADD_CXXFLAGS
21  add -L/disk/nauty25r9 -lnauty to LDFLAGS
22 
23  If you wish to use Traces rather than nauty then add -DNTY_TRACES
24 
25  To use it is -orbit on
26 
27  Nauty has this -
28 * Permission
29 * is hereby given for use and/or distribution with the exception of *
30 * sale for profit or application with nontrivial military significance. *
31  so you can use it internally even if you are a company.
32  */
33 #ifndef CBC_SYMMETRY_HPP
34 #define CBC_SYMMETRY_HPP
35 extern "C" {
36 #include "nauty.h"
37 #include "nausparse.h"
38 #ifdef NTY_TRACES
39 #include "traces.h"
40 #endif
41 }
42 
43 #include <vector>
44 #include <map>
45 #include <string.h>
46 
47 #include "CbcModel.hpp"
48 
49 class OsiObject;
50 // when to give up (depth since last success)
51 #ifndef NTY_BAD_DEPTH
52 #define NTY_BAD_DEPTH 10
53 #endif
54 class CbcNauty;
55 
56 
57 
58 #define COUENNE_HACKED_EPS 1.e-07
59 #define COUENNE_HACKED_EPS_SYMM 1e-8
60 #define COUENNE_HACKED_EXPRGROUP 8
61 
62 
69 class CbcSymmetry {
70  class Node{
71  int index;
72  double coeff;
73  double lb;
74  double ub;
75  int color;
76  int code;
77  int sign;
78  public:
79  void node(int, double, double, double, int, int);
80  inline void color_vertex (register int k) {color = k;}
81  inline int get_index () const {return index;}
82  inline double get_coeff () const {return coeff;}
83  inline double get_lb () const {return lb;}
84  inline double get_ub () const {return ub;}
85  inline int get_color () const {return color;}
86  inline int get_code () const {return code;}
87  inline int get_sign () const {return sign;}
88  inline void bounds(register double a, register double b){ lb = a; ub = b;}
89  };
90 
91  struct myclass0 {
92  inline bool operator() (register const Node &a, register const Node &b) {
93 
94  return (( a.get_code () < b.get_code ()) ||
95  (( a.get_code () == b.get_code () &&
96  (( a.get_coeff () < b.get_coeff () - COUENNE_HACKED_EPS_SYMM) ||
97  (( fabs (a.get_coeff () - b.get_coeff ()) < COUENNE_HACKED_EPS_SYMM) &&
98  (( a.get_lb () < b.get_lb () - COUENNE_HACKED_EPS_SYMM) ||
99  (( fabs (a.get_lb () - b.get_lb ()) < COUENNE_HACKED_EPS_SYMM) &&
100  (( a.get_ub () < b.get_ub () - COUENNE_HACKED_EPS_SYMM) ||
101  (( fabs (a.get_ub () - b.get_ub ()) < COUENNE_HACKED_EPS_SYMM) &&
102  (( a.get_index () < b.get_index ())))))))))));
103 
104  }
105  } ;
106 
107 
108  struct myclass {
109  inline bool operator() (register const Node &a, register const Node &b) {
110  return (a.get_index() < b.get_index() );
111  }
112  };
113 
114 struct less_than_str {
115  inline bool operator() (register const char *a, register const char *b) const
116  {return strcmp (a, b) < 0;}
117 };
118 
119  public:
120 
123  CbcSymmetry ();
125 
127  CbcSymmetry (const CbcSymmetry &);
128 
130  CbcSymmetry & operator=(const CbcSymmetry& rhs);
131 
133  ~CbcSymmetry ();
135 
136  // Symmetry Info
137 
138  std::vector<int> *Find_Orbit(int) const;
139 
140  myclass0 node_sort;
141  myclass index_sort;
142 
143  void Compute_Symmetry() const;
144  int statsOrbits(CbcModel * model, int type) const;
145  //double timeNauty () const;
146  void Print_Orbits() const;
147  void fillOrbits();
149  int orbitalFixing(OsiSolverInterface * solver);
150  inline int * whichOrbit()
151  { return numberUsefulOrbits_ ? whichOrbit_ : NULL;}
152  inline int numberUsefulOrbits() const
153  { return numberUsefulOrbits_;}
154  inline int numberUsefulObjects() const
155  { return numberUsefulObjects_;}
156  int largestOrbit(const double * lower, const double * upper) const;
157  void ChangeBounds (const double * lower, const double * upper,
158  int numberColumns,bool justFixedAtOne) const;
159  inline bool compare (register Node &a, register Node &b) const;
160  CbcNauty *getNtyInfo () {return nauty_info_;}
161 
162  // bool node_sort ( Node a, Node b);
163  // bool index_sort ( Node a, Node b);
164 
166  void setupSymmetry (const OsiSolverInterface & solver);
167 private:
168  mutable std::vector<Node> node_info_;
169  mutable CbcNauty *nauty_info_;
170  int numberColumns_;
171  int numberUsefulOrbits_;
172  int numberUsefulObjects_;
173  int * whichOrbit_;
174 };
175 
176 class CbcNauty
177 {
178 
179 public:
181 
184 private:
186  CbcNauty ();
187 public:
189  CbcNauty (int n, const size_t * v, const int * d, const int * e);
190 
192  CbcNauty (const CbcNauty &);
193 
195  CbcNauty & operator=(const CbcNauty& rhs);
196 
198  ~CbcNauty ();
200 
201  void addElement(int ix, int jx);
202  void clearPartitions();
203  void computeAuto();
204  void deleteElement(int ix, int jx);
205  void color_node(int ix, int color) { vstat_[ix] = color; }
206  void insertRHS(int rhs , int cons) {constr_rhs.insert( std::pair<int,int>(rhs,cons));}
207 
208  double getGroupSize() const;
209  //int getNautyCalls() const { return nautyCalls_; }
210  //double getNautyTime() const { return nautyTime_; }
211 
212  int getN() const { return n_; }
213 
214  int getNumGenerators() const;
215  int getNumOrbits() const;
216 
218  std::vector<std::vector<int> > *getOrbits() const;
219 
220  void getVstat(double *v, int nv);
221  inline bool isSparse() const
222  { return GSparse_ != NULL;}
223  inline int errorStatus() const
224  { return stats_->errstatus;}
228  // bool isAllFixOneOrbit(const std::vector<int> &orbit) const;
229  // bool isAllFreeOrbit(const std::vector<int> &orbit) const;
230  //bool isAutoComputed() const { return autoComputed_; }
231  //bool isConstraintOrbit(const std::vector<int> &orbit) const;
232  //bool isMixedFreeZeroOrbit(const std::vector<int> &orbit) const;
233  //void makeFree(int ix) { vstat_[ix] = FREE; }
234 
235  void setWriteAutoms (const std::string &afilename);
236  void unsetWriteAutoms();
237 
238 private:
239 
240  // The base nauty stuff
241  graph *G_;
242  sparsegraph *GSparse_;
243  int *lab_;
244  int *ptn_;
245  set *active_;
246  int *orbits_;
247 #ifndef NTY_TRACES
248  optionblk *options_;
249  statsblk *stats_;
250 #else
251  TracesOptions *options_;
252  TracesStats *stats_;
253 #endif
254  setword *workspace_;
255  int worksize_;
256  int m_;
257  int n_;
258  size_t nel_;
259  graph *canonG_;
260 
261  bool autoComputed_;
262 
263  int *vstat_;
264 
265  //static int nautyCalls_;
266  //static double nautyTime_;
267 
268  std::multimap<int,int> constr_rhs;
269  std::multimap<int,int>::iterator it;
270 
271  std::pair<std::multimap<int,int>::iterator,
272  std::multimap<int,int>::iterator> ret;
273 
274  // File pointer for automorphism group
275  FILE *afp_;
276 
277 };
278 
279 
286 
287 public:
288 
289  // Default Constructor
291 
292  // Useful constructor
294  int way,
295  int numberExtra, const int * extraToZero);
296 
297  // Copy constructor
299 
300  // Assignment operator
302 
304  virtual CbcBranchingObject * clone() const;
305 
306  // Destructor
307  virtual ~CbcOrbitalBranchingObject ();
308 
311  virtual double branch();
314  virtual void fix(OsiSolverInterface * solver,
315  double * lower, double * upper,
316  int branchState) const ;
317 
321  virtual void previousBranch() {
323  }
324 
328  virtual void print();
329 
331  virtual CbcBranchObjType type() const {
332  return SoSBranchObj;
333  }
334 
342  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
343 
353  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
354 
355 private:
357  int column_;
359  int numberOther_;
361  int numberExtra_;
363  int * fixToZero_;
364 };
365 
366 #endif
CbcNauty * getNtyInfo()
void setupSymmetry(const OsiSolverInterface &solver)
empty if no NTY, symmetry data structure setup otherwise
myclass0 node_sort
void color_node(int ix, int color)
virtual ~CbcOrbitalBranchingObject()
void computeAuto()
void addElement(int ix, int jx)
virtual CbcBranchingObject * clone() const
Clone.
int errorStatus() const
int * whichOrbit()
void ChangeBounds(const double *lower, const double *upper, int numberColumns, bool justFixedAtOne) const
int getNumOrbits() const
void fillOrbits()
#define COUENNE_HACKED_EPS_SYMM
Definition: CbcSymmetry.hpp:59
void deleteElement(int ix, int jx)
CbcRangeCompare
std::vector< std::vector< int > > * getOrbits() const
Returns the orbits in a &quot;convenient&quot; form.
void clearPartitions()
virtual double branch()
Does next branch and updates state.
Branching object for Orbital branching.
myclass index_sort
~CbcSymmetry()
Destructor.
void unsetWriteAutoms()
bool isSparse() const
void Compute_Symmetry() const
bool compare(register Node &a, register Node &b) const
Class to deal with symmetry.
Definition: CbcSymmetry.hpp:69
double getGroupSize() const
void setWriteAutoms(const std::string &afilename)
Methods to classify orbits.
int way() const
Get the state of the branching object.
Abstract branching object base class Now just difference with OsiBranchingObject. ...
int numberUsefulOrbits() const
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child...
void getVstat(double *v, int nv)
virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap=false)
Compare the this with brObj.
CbcBranchObjType
void Print_Orbits() const
CbcOrbitalBranchingObject & operator=(const CbcOrbitalBranchingObject &rhs)
CbcModel * model() const
Return model.
virtual double branch()=0
Execute the actions required to branch, as specified by the current state of the branching object...
virtual CbcBranchObjType type() const
Return the type (an integer identifier) of this.
virtual void print() const
Print something about branch - only if log level high.
void insertRHS(int rhs, int cons)
~CbcNauty()
Destructor.
int statsOrbits(CbcModel *model, int type) const
CbcNauty & operator=(const CbcNauty &rhs)
Assignment operator.
virtual int compareOriginalObject(const CbcBranchingObject *brObj) const
Compare the original object of this with the original object of brObj.
virtual void print()
Print something about branch - only if log level high.
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child...
virtual void fix(OsiSolverInterface *solver, double *lower, double *upper, int branchState) const
Update bounds in solver as in &#39;branch&#39; and update given bounds.
CbcSymmetry & operator=(const CbcSymmetry &rhs)
Assignment operator.
int orbitalFixing(OsiSolverInterface *solver)
Fixes variables using orbits (returns number fixed)
int largestOrbit(const double *lower, const double *upper) const
Simple Branch and bound class.
Definition: CbcModel.hpp:101
int getNumGenerators() const
std::vector< int > * Find_Orbit(int) const
int getN() const
CbcSymmetry()
Default constructor.
int numberUsefulObjects() const